An Extended Quadratic Frobenius Primality Test with
Average- and Worst-Case Error Estimate |
| |
Authors: | Ivan Bjerre Damgard Gudmund Skovbjerg Frandsen |
| |
Affiliation: | (1) BRICS, Department of Computer Science, University of Aarhus, IT-parken, Aabogade 34, DK-8200, Aarhus N, Denmark |
| |
Abstract: | We present an Extended Quadratic Frobenius Primality Test (EQFT), which is related to the Miller-Rabin test and to several
other known probabilistic tests. EQFT takes time equivalent to about two or three Miller-Rabin tests, but has a much smaller
error probability, namely 256/331776t for t iterations of the test in the worst case. We also give bounds on the average-case behaviour of the test: consider
the algorithm that repeatedly chooses random odd k bit numbers, subjects them to t iterations of our test and outputs the
first one found that passes all tests. We obtain numeric upper bounds for the error probability of this algorithm as well
as a general closed expression bounding the error. For instance, it is at most 2-155 for k = 500, t = 2. Compared with earlier similar results for the Miller-Rabin test, the results indicate that our test in
the average case has the effect of nine Miller-Rabin tests. We also give bounds for the error in case a prime is sought by
incremental search from a random starting point. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|