System Experiments Laboratory  

Go Back   System Experiments Laboratory > Mathematics > Prime Numbers

Thread Tools Display Modes
Old 08-26-2019
selroc selroc is offline
Join Date: Aug 2019
Location: ROME
Posts: 128
Default A Probable Prime Test with Very High Confidence for n equiv 1 mod 4

Mueller, Siguna. (2001). A Probable Prime Test with Very High Confidence for n equiv 1 mod 4.. 87-106. 10.1007/3-540-45682-1_6. 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. 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 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 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 Miller-Rabin 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 Miller-Rabin tests. But for each iteration, the error is less than 1/131040.
Reply With Quote

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

All times are GMT +2. The time now is 09:05 AM.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, vBulletin Solutions Inc.
(c) 2020 System Experiments Laboratory