Communicated by A. Granville
Monier and Rabin proved that an odd composite can pass the Strong Probable Prime Test for at most 1Γ4 of the possible bases. In this paper, a probable prime test is developed using quadratic polynomials and the Frobenius automorphism. The test, along with a fixed number of trial divisions, ensures that a composite n will pass for less than 1Γ7710 of the polynomials x 2 &bx&c with (b 2 +4c | n)=&1 and (&c | n)=1. The running time of the test is asymptotically 3 times that of the Strong Probable Prime Test.
1998 Academic Press
1. BACKGROUND
Perhaps the most common method for determining whether or not a number is prime is the Strong Probable Prime Test. Given an odd integer n, let n=2 r s+1 with s odd. Choose a random integer a with 1 a n&1. If a s #1 mod n or a 2 j s #&1 mod n for some 0 j r&1, then n passes the test. An odd prime will pass the test for all a.
The test is very fast; it requires no more than (1+o(1)) log 2 n multiplications mod n, where log 2 n denotes the base 2 logarithm. The catch is that a number which passes the test is not necessarily prime. Monier [9] and Rabin [13], however, showed that a composite n passes for at most 1Γ4 of the possible bases a. Thus, if the bases a are chosen at random, composite n will pass k iterations of the Strong Probable Prime Test with probability at most 1Γ4 k .
Recently, Arnault [2] has shown that any composite n passes the Strong Lucas Probable Prime Test for at most 4Γ15 of the bases (b, c), unless n is the product of twin primes having certain properties (these composites are easy to detect). Also, Jones and Mo [8] have introduced an Extra Strong Lucas Probable Prime Test. Composite n will pass this test with probability at most 1Γ8 for a random choice of the parameter b. These authors did not concern themselves with the issue of running time. The methods of [10], however, show each test can be performed in twice the Article No. NT982247