From: daniel@...42.com Date: 2020-02-20T20:37:27+00:00 Subject: [ruby-core:97223] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime? Issue #16468 has been updated by Dan0042 (Daniel DeLorme). steveb3210 (Stephen Blackstone) wrote in #note-16: > Unforunately Miller-Rabin is not a deterministic test for arbitrarily large n - its only the work in the paper https://arxiv.org/pdf/1509.00864.pdf that allows us to provide functionality up to a bound. Yes, I know, that was my point. Maybe I want to know if arbitrarily large N is prime _while accepting a probability of error_ of 4**(-k); then I could use `miller_rabin(k)`. And the `prime?` method uses a boundary check and `miller_rabin(12)` to produce a deterministic result. Or is it `miller_rabin(13)`? The description above says primes up to 37 but your patch uses primes up to 41. ---------------------------------------- Feature #16468: Switch to Miller-Rabin for Prime.prime? https://bugs.ruby-lang.org/issues/16468#change-84333 * Author: steveb3210 (Stephen Blackstone) * Status: Open * Priority: Normal ---------------------------------------- The miller-rabin algorithm is a non-deterministic 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: 2-10000 0.030000 0.000000 0.030000 ( 0.035752) Prime.prime? 2-10000 0.020000 0.000000 0.020000 ( 0.022948) ---Files-------------------------------- prime_patch.diff (2.5 KB) -- https://bugs.ruby-lang.org/ Unsubscribe: