Namespaces
Variants
Actions

Difference between revisions of "Probabilistic primality test"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(converting to LaTeX)
Line 1: Line 1:
 
A randomized procedure that takes a natural number as input and attempts to determine whether that number is prime or composite (cf. [[Prime number|Prime number]]). The output of the procedure should be correct with high probability, independently of the number being tested.
 
A randomized procedure that takes a natural number as input and attempts to determine whether that number is prime or composite (cf. [[Prime number|Prime number]]). The output of the procedure should be correct with high probability, independently of the number being tested.
  
It is desirable that such a test run in polynomial time; that is, the number of bit operations used to test <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p1102401.png" /> for primality should be no more than a power of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p1102402.png" />. One distinguishes between Las Vegas primality tests, which prove primality, and Monte-Carlo primality tests, which only provide statistical evidence.
+
It is desirable that such a test run in polynomial time; that is, the number of bit operations used to test $ n $ for primality should be no more than a power of $ \log n $. One distinguishes between Las Vegas primality tests, which prove primality, and Monte-Carlo primality tests, which only provide statistical evidence.
  
 
Aside from [[Number theory|number theory]], these tests are of interest in computer science because it is not known whether there is a deterministic polynomial-time algorithm for primality (cf. [[Complexity theory|Complexity theory]]). In addition, they can be used to select keys for public-key cryptographic systems (cf. [[Cryptography|Cryptography]]; [[Cryptology|Cryptology]]).
 
Aside from [[Number theory|number theory]], these tests are of interest in computer science because it is not known whether there is a deterministic polynomial-time algorithm for primality (cf. [[Complexity theory|Complexity theory]]). In addition, they can be used to select keys for public-key cryptographic systems (cf. [[Cryptography|Cryptography]]; [[Cryptology|Cryptology]]).
  
One popular Monte-Carlo test is the strong prime test, studied by several authors. To test an odd <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p1102403.png" /> for primality, one first partially factors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p1102404.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p1102405.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p1102406.png" /> is odd. Then, one chooses a random integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p1102407.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p1102408.png" />, and computes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p1102409.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p11024010.png" />. If the sequence is either all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p11024011.png" />'s, or contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p11024012.png" />, the algorithm says  "prime" . In all other cases, the algorithm says  "composite" . In the first case, the statement is correct with probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p11024013.png" />, independently of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p11024014.png" />; in the second case, the assertion is always correct. The computation can be done using <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p11024015.png" /> multiplications modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p11024016.png" />. For the history and more examples of Monte-Carlo tests, see [[#References|[a3]]], [[#References|[a4]]].
+
One popular Monte-Carlo test is the strong prime test, studied by several authors. To test an odd $ n > 1 $ for primality, one first partially factors $ n-1 $ as $ 2 ^\nu m $, where $ m $ is odd. Then, one chooses a random integer $ b $ with $ 1 < b < n-1 $, and computes $ b^m, b^{2m}, \ldots, b^{n-1} $ modulo $ n $. If the sequence is either all $ 1 $'s, or contains $ -1 $, the algorithm says  "prime" . In all other cases, the algorithm says  "composite" . In the first case, the statement is correct with probability $ \ge 3/4 $, independently of $ n $; in the second case, the assertion is always correct. The computation can be done using $ \le 2\log_2 n $ multiplications modulo $ n $. For the history and more examples of Monte-Carlo tests, see [[#References|[a3]]], [[#References|[a4]]].
  
L.M. Adleman and M.-D. Huang have shown, using the Jacobian group of an [[Abelian variety|Abelian variety]], that there is a polynomial-time Las Vegas algorithm for primality. They do not consider their algorithm practical. A related heuristic method, based on elliptic curves (cf. [[Elliptic curve|Elliptic curve]]), was designed by A.O.L. Atkin and F. Morain (building on work of S. Goldwasser and J. Kilian), and has been used to find primality proofs for numbers of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110240/p11024017.png" /> decimal digits. For these algorithms, see the overview in [[#References|[a4]]] and the original references [[#References|[a1]]], [[#References|[a2]]].
+
L.M. Adleman and M.-D. Huang have shown, using the Jacobian group of an [[Abelian variety|Abelian variety]], that there is a polynomial-time Las Vegas algorithm for primality. They do not consider their algorithm practical. A related heuristic method, based on elliptic curves (cf. [[Elliptic curve|Elliptic curve]]), was designed by A.O.L. Atkin and F. Morain (building on work of S. Goldwasser and J. Kilian), and has been used to find primality proofs for numbers of $ 1000 $ decimal digits. For these algorithms, see the overview in [[#References|[a4]]] and the original references [[#References|[a1]]], [[#References|[a2]]].
  
 
See also [[Pseudo-prime|Pseudo-prime]]; [[Carmichael number|Carmichael number]].
 
See also [[Pseudo-prime|Pseudo-prime]]; [[Carmichael number|Carmichael number]].

Revision as of 19:33, 1 May 2013

A randomized procedure that takes a natural number as input and attempts to determine whether that number is prime or composite (cf. Prime number). The output of the procedure should be correct with high probability, independently of the number being tested.

It is desirable that such a test run in polynomial time; that is, the number of bit operations used to test $ n $ for primality should be no more than a power of $ \log n $. One distinguishes between Las Vegas primality tests, which prove primality, and Monte-Carlo primality tests, which only provide statistical evidence.

Aside from number theory, these tests are of interest in computer science because it is not known whether there is a deterministic polynomial-time algorithm for primality (cf. Complexity theory). In addition, they can be used to select keys for public-key cryptographic systems (cf. Cryptography; Cryptology).

One popular Monte-Carlo test is the strong prime test, studied by several authors. To test an odd $ n > 1 $ for primality, one first partially factors $ n-1 $ as $ 2 ^\nu m $, where $ m $ is odd. Then, one chooses a random integer $ b $ with $ 1 < b < n-1 $, and computes $ b^m, b^{2m}, \ldots, b^{n-1} $ modulo $ n $. If the sequence is either all $ 1 $'s, or contains $ -1 $, the algorithm says "prime" . In all other cases, the algorithm says "composite" . In the first case, the statement is correct with probability $ \ge 3/4 $, independently of $ n $; in the second case, the assertion is always correct. The computation can be done using $ \le 2\log_2 n $ multiplications modulo $ n $. For the history and more examples of Monte-Carlo tests, see [a3], [a4].

L.M. Adleman and M.-D. Huang have shown, using the Jacobian group of an Abelian variety, that there is a polynomial-time Las Vegas algorithm for primality. They do not consider their algorithm practical. A related heuristic method, based on elliptic curves (cf. Elliptic curve), was designed by A.O.L. Atkin and F. Morain (building on work of S. Goldwasser and J. Kilian), and has been used to find primality proofs for numbers of $ 1000 $ decimal digits. For these algorithms, see the overview in [a4] and the original references [a1], [a2].

See also Pseudo-prime; Carmichael number.

References

[a1] L.M. Adleman, M.-D. Huang, "Primality testing and Abelian varieties over finite fields" , Lecture Notes in Mathematics , 1512 , Springer (1992)
[a2] A.O.L. Atkin, F. Morain, "Elliptic curves and primality proving" Math. Comp. , 61 (1993) pp. 29–68
[a3] E. Bach, J. Shallit, "Algorithmic number theory" , 1: Efficient Algorithms , MIT (1996)
[a4] A.K. Lenstra, H.W. Lenstra, Jr., "Algorithms in number theory" J. van Leeuwen (ed.) , Handbook of Theoretical Computer Science , A , MIT (1990)
How to Cite This Entry:
Probabilistic primality test. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Probabilistic_primality_test&oldid=29713
This article was adapted from an original article by E. Bach (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article