Issue #16468 has been reported by steveb3210 (Stephen Blackstone).

----------------------------------------
Feature #16468: Switch to Miller-Rabin for Prime.prime?
https://bugs.ruby-lang.org/issues/16468

* Author: steveb3210 (Stephen Blackstone)
* Status: Open
* Priority: Normal
* Assignee: 
* Target version: 
----------------------------------------
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)
```


```
require 'benchmark'
require 'prime'

def modpow(base, power, mod)
  result = 1
  while power > 0
    result = (result * base) % mod if power & 1 == 1
    base = (base * base) % mod
    power >>= 1;
  end
  result
end

def miller_rabin(n)
  return false if n < 2 # 0, 1
  return true  if n < 4 # 2, 3
  return false if n % 2 == 0 # 4, 6, 8, 10
  d = (n-1)
  s = 0
  while (d % 2 == 0)
    s +=1
    d /= 2
  end
  
  
  # https://arxiv.org/pdf/1509.00864.pdf
  #
  # if n < 18,446,744,073,709,551,616 = 2**64, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37.
  #
  [2,3,5,7,11,13,17,19,23, 29, 31, 37].each do |a|
    x = modpow(a,d,n)
    next if x == 1 or x == (n - 1) or n == a
    skip = false
    1.upto(s-1) do |k|
      x = x*x % n
      if x == 1
        return false
      elsif x == (n - 1)
        skip = true
        break
      end
    end
    next if skip
    return false
  end
  return true
end



test_set = []

while test_set.length < 50_000
  test_set << rand(1_000_000)
end


c = 1

Benchmark.bm(40) do |bm|  
  bm.report("miller_rabin: random set") do 
    test_set.each do |x|
      miller_rabin(x)
    end    
  end

  bm.report("Prime.prime?: random set") do
    test_set.each do |x|
      Prime.prime?(x)
    end
  end
end

puts


Benchmark.bm(40) do |bm|  
  bm.report("miller_rabin: 16 digits") do 
    miller_rabin(1000000000100011)
  end

  bm.report("Prime.prime? 16 digits") do
    Prime.prime?(1000000000100011)
  end
end

puts


Benchmark.bm(40) do |bm|  
  bm.report("miller_rabin: 2-10000") do 
    (2..10000).each do |x|
      miller_rabin(x)
    end
    
  end

  bm.report("Prime.prime? 2-10000") do
    (2..10000).each do |x|
      Prime.prime?(x)
    end
  end
end

```



-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>