**A Simplified Quadratic Frobenius Primality Test**

*Martin Seysen*

**Abstract: **The publication of the quadratic Frobenius primality test by
Grantham, 1998 has stimulated a lot of researchin this area. In this test as well as in the Miller-Rabin test a composite number may be
declared as probably prime. Repeating several tests decreases that
error probability. While most research papers in this subject focus on minimising the error probability as a function of the number of
tests (or, more generally, of the computational effort)
asymptotically, we present a simplified variant SQFT of the
quadratic Frobenius test. This test is so simple that it can easily
be implemented on a smart card.

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å 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 format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20051231:145944 (All versions of this report)

**Short URL: **ia.cr/2005/462

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]