Feature #16468
Switch to MillerRabin for Prime.prime?
Status:
Open
Priority:
Normal
Assignee:

Target version:

Description
The millerrabin algorithm is a nondeterministic primality test, however it is known that below 2**64, you can always get a deterministic answer by only checking a=[2,3,5,7,11,13,17,19,23, 29, 31, 37]
Given that Prime.prime? would never respond in a reasonable amount of time for larger numbers, we can gain much more utility and performance by switching..
user system total real miller_rabin: random set 0.150000 0.000000 0.150000 ( 0.152212) Prime.prime?: random set 0.270000 0.000000 0.270000 ( 0.281257) user system total real miller_rabin: 16 digits 0.010000 0.000000 0.010000 ( 0.000300) Prime.prime? 16 digits 2.200000 0.020000 2.220000 ( 2.368247) user system total real miller_rabin: 210000 0.030000 0.000000 0.030000 ( 0.035752) Prime.prime? 210000 0.020000 0.000000 0.020000 ( 0.022948)
Files