Paper 2001/102
An Extended Quadratic Frobenius Primality Test with Average Case Error Estimates
Ivan Damgård and Gudmund Frandsen
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
Metadata
- Available format(s)
-
PDF PS
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Primality testnumber theory
- Contact author(s)
- ivan @ daimi au dk
- History
- 2001-11-25: received
- Short URL
- https://ia.cr/2001/102
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2001/102, author = {Ivan Damgård and Gudmund Frandsen}, title = {An Extended Quadratic Frobenius Primality Test with Average Case Error Estimates}, howpublished = {Cryptology {ePrint} Archive, Paper 2001/102}, year = {2001}, url = {https://eprint.iacr.org/2001/102} }