A PROBABLE PRIME TEST WITH HIGH CONFIDENCE

Jon Grantham

Abstract. Monier and Rabin proved that an odd composite can pass the Strong Probable Prime Test for at most \frac{1}{4} of the possible bases. In this paper, a probable prime test is developed using quadratic polynomials and the Frobenius automor- phism. The test, along with a fixed number of trial divisions, ensures that a compos- ite n will pass for less than \frac{1}{7710} of the polynomials x^{2} − bx − c with ( \frac{b^{2}+4c}{n} ) = −1 and _{( \frac{−c}{n} )} = 1. The running time of the test is asymptotically 3 times that of the Strong Probable Prime Test.

§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^{2passesthetest. Anoddprimewill 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 \frac{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 \frac{1}{4�} . Recently, Arnault [2] has shown that any composite n passes the Strong Lucas Probable Prime Test for at most \frac{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 \frac{1}{8} for a random choice of the parameter b. hese 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 time it takes to perform the Strong Probable Prime Test. By contrast, two iterations of the Strong Probable Prime Test take the same amount of time and are passed by a composite with probability at most \frac{1}{16} . Pomerance, Selfridge and Wagstaff have proposed a test, based on a combination of he Strong Probable Prime Test and the Lucas Probable Prime Test, that seems very powerful [12]. Indeed, nobody has yet claimed the $620 that they offer for a composite that passes it [6], even though they have relaxed the conditions of the 1991 Mathematics Subject Classification. 11Y11. This paper appeared in Journal of Number Theory 72, 32–47 (1998). Copyright c 1998 by Academic Press. Typeset by AMS-TEX}_{1} offer so that the Probable Prime Test no longer need be “Strong”. Adams and Shanks proposed a test based on Perrin’s sequence [1]. The Q and I cases of their test also have no known pseudoprimes. The success of both of these tests suggests that it is possible to construct a test that is, in some sense, stronger than the Strong Probable Prime Test. My goal is to provide a test which is always passed by primes, but passed by composites with probability less than \frac{1}{7710}. This test has running time bounded by (3 + o(1)) log_{2} n multiplications mod n. By comparison, 3 iterations of the Strong Probable Prime Test have a running time bounded by (3 + o(1)) log_{2} n multiplications and have a probability of error at most \frac{1}{64} . The number \frac{1}{7710} is slightly greater than \frac{17}{2^{17}} + ϵ, and \frac{17}{2^{17}} is the limit of the analysis in this paper. The lack of counterexamples to the PSW and Perrin tests indicates that the true probability of error may be much lower. See Section 4 for possible improved versions of the test. I would like to thank Carl Pomerance for his comments on this paper, including the suggestion of the technique described in Proposition 3.3. §2 The Quadratic Frobenius Test The following test is based on the concepts of Frobenius probable primes and strong Frobenius probable primes, which I introduced in another paper [5]. These tests involve computations in the ring ℤ[x]/(n, f(x)), where f(x) ∈ ℤ[x] and n is an dd positive integer. We will be considering the special case f(x) = x^{2} − bx − c. For convenience of notation, we introduce the integer B, which we later show can be taken to be 50000. Definition. Suppose n > 1 is odd, (\frac{b^{2}+4c}{n}) = −1, and (\frac{−c}{n}) = 1. The Quadratic Frobenius Test (QFT) with parameters (b, c) consists of the following. 1) Test n for divisibility by primes less than or equal to min\{B, \sqrt{n}\}. If it is divisible by one of these primes, declare n to be composite and stop. 2) Test whether \sqrt{n} ∈ ℤ. If it is, declare n to be composite and stop. 3) Compute x^{\frac{�+1}{2}} mod (n, x^{2}−bx−c). If x^{\frac{�+1}{2}} ∉ ℤ/nℤ, declare n to be composite

and stop.

4) Compute x^{n+1} mod (n, x^{2} − ⌊§ − c). If x^{n+1} ≢ −c, declare n to be composite and stop.

5) Let n^{2} − 1 = 2^{r}s, where s is odd. If x^{s} ≢ 1 mod (n, x^{2} − bx − c), and x^{2� s} ≢ −1 mod (n, x^{2} − bx − c) for all 0 ≤ j ≤ r − 2, declare n to be composite and stop.

If n is not declared composite in Steps 1–5, declare n to be a probable prime. Definition. Suppose n, b, c are as above. We say n passes the QFT with parameters (b, c) if the test declares n to be a probable prime.

The requirement that (\frac{−c}{n}) = 1 complicates the test somewhat. Without it and Step 3, an accuracy of only \frac{1}{495} can be proven.

Steps 4 and 5 of the QFT are equivalent to the Strong Frobenius Probable Prime Test described in [5] for the polynomial x^{2} − bx − c. As is stated there, the test is not entirely new, but rather a combination of ideas contained in earlier probable prime tests. The stricter condition j ≤ r − 2 is possible because the restriction (\frac{−c}{n}) = 1 forces x to be a square in the finite field ℤ[x]/(n, x^{2} − bx − c), if n is a prime.