An Extended Quadratic Frobenius Primality Test with Average Case Error
Estimates
Ivan Bjerre Damgård
November 2001 |
Abstract:
We present an Extended Quadratic Frobenius Primality Test
(EQFT), which is related to the Miller-Rabin test and the Quadratic Frobenius
test (QFT) by Grantham. EQFT is well-suited for generating large, random
prime numbers since on a random input number, it takes time about equivalent
to 2 Miller-Rabin tests, but has much smaller error probability. EQFT extends
QFT by verifying additional algebraic properties related to the existence of
elements of order 3 and 4. We obtain a simple closed expression that upper
bounds the probability of acceptance for any input number. This in turn
allows us to give strong bounds on the average-case behaviour of the test:
consider the algorithm that repeatedly chooses random odd
![]() ![]() ![]() ![]() Available as PostScript, PDF. |