Probabilistic primality testing - who cares?
by
Siguna Mueller
University of Calgary

Almost two years ago the new results by Agrawal, Kayal, and Saxena revolutionized the theory of primality proving. Unfortunately, their ideas have so far not led to a practial application. Practically, it seems that the strong probable prime test is still the primary algorithm used for primality testing. As is widely known, it may, however unlikely, return a wrong result. This was the motivation for probabilistic routines which in addition require some quadratic field based routine. These are provably much stronger but require knowledge of some c which looks like a quadratic nonresidue modulo n. The other disadvantage is that computations need to be performed in a quadratic extension, instead of Z_n only.

We enhance the current probabilistic tests. New results are proposed which are based on ideas of Grantham, Damgård and Frandsen, Berrizbeitia, and the author.

As an example of these results we mention the following. Suppose we have an element that looks like a noncube modulo n \equiv 1 mod 3. The test runs in Z_n with running time comparable to Miller-Rabin. However, instead of failure 1/4 we get a failure of 1/9. This can be generalized to (reasonably small) r dividing n-1. (For r large enought the test is known to be deterministic anyay). Again, using arithmetic in Z_n only, the failure rate becomes 1/r². Further generalizations can be obtained when working in an extension of Z_n.

Date received: May 3, 2004