Probabilistic primality test

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)