International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Martin Seysen

Affiliation: Giesecke & Devrient

Publications

Year
Venue
Title
2005
CHES
2005
EPRINT
A Simplified Quadratic Frobenius Primality Test
Martin Seysen
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\aa rd and Frandsen, 2003, in all cases. Our test SQFT3 avoids the computation of cubic residuosity symbols, as required in the test EQFTwc.