A Probable Prime Test with Very High Confidence for

摘要

Although the Miller-Rabin test is very fast in practice, there exist composite integers n for which this test fails for 1/4 of all bases coprime to n. In 1998 Grantham developed a probable prime test with failure probability of only 1/7710 and asymptotic running time 3 times that of the Miller-Rabin test. For the case that n≡1 mod 4, by S. Muller a test with failure rate of 1/8190 and comparable running time as for the Grantham test was established. Very recently, with running time always at most 3 Miller-Rabin tests, this was improved to 1/131040, for the other case, n≡3 mod 4. Unfortunately the underlying techniques cannot be generalized to n≡1 mod 4. Also, the main ideas for proving this result do not extend to n≡1 mod 4. Here, we explicitly deal with n≡1 mod 4 and propose a new probable prime test that is extremely efficient. For the first round, our test has average running time (4 + o(1))log{sub}2 n multiplications or squarings mod n, which is about 4 times as many as for the Miller-Rabin test. But the failure rate is much smaller than 1/4{sup}4 = 1/256. Indeed, for our test we prove a worst case failure probability less than 1/1048350. Moreover, each iteration of the test runs in time equivalent to only 3 Miller-Rabin tests. But for each iteration, the error is less than 1/131040.