#1




A Probable Prime Test with Very High Confidence for n equiv 1 mod 4
https://www.researchgate.net/publica...equiv_1_mod_47
Mueller, Siguna. (2001). A Probable Prime Test with Very High Confidence for n equiv 1 mod 4.. 87106. 10.1007/3540456821_6. Although the MillerRabin 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 MillerRabin test. For the case that n ≡ 1 mod 4, by S. Müller 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 MillerRabin 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 newprobable prime test that is extremely efficient. For the first round, our test has average running time (4 + o(1)) log2 n multiplications or squarings mod n, which is about 4 times as many as for the MillerRabin test. But the failure rate is much smaller than 1/44 = 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 MillerRabin tests. But for each iteration, the error is less than 1/131040. 
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)  
Thread Tools  
Display Modes  

