During prime number generation, a large number of composite numbers must be tested before a (probable) prime is found. Therefore we need a fast test, such as the Miller-Rabin test with a small basis, to rule out most prime candidates quickly before a promising candidate will be tested with a more sophisticated variant of the QFT. Our test SQFT makes optimum use of the information gathered by a previous Miller-Rabin test. It has run time equivalent to two Miller-Rabin tests; and it achieves a worst-case error probability of $2^{-12t}$ with $t$ tests.
Most cryptographic standards require an average-case error probability of at most $2^{-80}$ or $2^{-100}$, when prime numbers are generated in public key systems. Our test SQFT achieves an average-case error probability of $2^{-134}$ with two test rounds for $500-$bit primes. We also present a more sophisticated version SQFT3 of our test that has run time and worst-case error probability comparable to the test EQFTwc by Damg\aa rd and Frandsen, 2003, in all cases. Our test SQFT3 avoids the computation of cubic residuosity symbols, as required in the test EQFTwc.
Category / Keywords: implementation / primality testing, quadratic Frobenius test Date: received 20 Dec 2005 Contact author: martin seysen at gi-de com Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20051231:145944 (All versions of this report) Discussion forum: Show discussion | Start new discussion