A probable prime test with very high confidence for \(n \equiv 3\mod4\)
type: Item
instance of: scholarly article
title: A probable prime test with very high confidence for \(n \equiv 3\mod4\)
zbMATH Open document ID: 1041.11083
author: D. Massart
published in: Journal of Cryptology
publication date: 2003-08-27T00:00:00Z
review text: The archetype of the probabilistic primality tests usually used in cryptography is the Miller-Rabin test. This test is extremely fast and guarantees the prime character of an odd number with such a small error probability as wanted. It has the drawback however that a composite number can be accepted as prime by a quarter of all possible bases. It is also possible to construct composite numbers which pass the Miller-Rabin test for any given number of bases. Other alternatives have been proposed in the literature to obtain more reliable prime tests, some of them due to the author of the present paper. In [Advances in Cryptology-Asiacrypt'01, Lect. Notes Comput. Sci. 2248, 87--106 (2001)] she analyzes the case of primes \(n\equiv 1 \bmod 4\). In the present paper, following ideas of \textit{C. Pomerance}, \textit{J. Selfridge} and {S. S. Wagstaff jun.} [Math. Comput. 35, 1003--1026 (1980; Zbl 0444.10007)] and \textit{R. Baillie} and \textit{S. S. Wagstaff jun.} [Math. Comput. 35, 1391--1417 (1980; Zbl 0458.10003)], the author gives a new test such that a composite number \(n\equiv 3 \bmod 4\) will pass the test only with probability at most \(1/331000\), in the worst case. The drawback is a running time of about three times the running time of the Miller-Rabin test. Instead of considering only the extraction of square roots of 1, as the authors mentioned before do, the paper proposes incorporating third and four root testing conditions. It combines properties relative to the residue classes of \(n\) modulo 3 and 8. The \` Combined Test' is stated in Section 2 of the paper. The following sections discuss details and some implementation issues of the proposed test.
Mathematics Subject Classification ID: 11Y11
Mathematics Subject Classification ID: 11A51
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 1971855
zbMATH Keywords: probabilistic primality tests
zbMATH Keywords: combined tests
zbMATH Keywords: quadratic fields
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
full work available at URL: s00145-002-0107-y
OpenAlex ID: W162865231
DOI: 10.1007/S00145-002-0107-Y
Recommended article: Q4474167
Recommended article: Generalized strong pseudoprime tests and applications
Recommended article: Q3786518
Recommended article: Q2708615
Recommended article: The generation of random numbers that are probably prime
Recommended article: Q3828064
Recommended article: The error probability of the Miller-Rabin primality test
Recommended article: On practical aspects of the Miller-Rabin primality test
Recommended article: Four primality testing algorithms
Recommended article: A probable prime test with high confidence
description: scientific article; zbMATH DE number 1971855