Welcome to the resource topic for 2005/462
Title:
A Simplified Quadratic Frobenius Primality Test
Authors: 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\aa rd and Frandsen, 2003, in all cases. Our test SQFT3 avoids the computation of cubic residuosity symbols, as required in the test EQFTwc.
ePrint: https://eprint.iacr.org/2005/462
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .