## Feature #16468

### Switch to Miller-Rabin for Prime.prime?

**Description**

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**

#### Updated by steveb3210 (Stephen Blackstone) 11 months ago

**File***patch.diff*added

Attached is an implementation against master....

#### Updated by marcandre (Marc-Andre Lafortune) 11 months ago

Interesting. We might as well always return the correct result, i.e. apply the fast algorithm for integers < 318,665,857,834,031,151,167,461 and the slow algorithm for larger ones. Would you care to modify your patch?

#### Updated by steveb3210 (Stephen Blackstone) 11 months ago

marcandre (Marc-Andre Lafortune) wrote:

Interesting. We might as well always return the correct result, i.e. apply the fast algorithm for integers < 318,665,857,834,031,151,167,461 and the slow algorithm for larger ones. Would you care to modify your patch?

If you were to use the existing algorithm on 318,665,857,834,031,151,167,461 you'd need Math.sqrt(318665857834031151167461 ) / 30.0 = 18_816_832_235 loop iterations.. Its not worth falling back given how inefficient the existing function is at that magnitude.

#### Updated by mame (Yusuke Endoh) 11 months ago

It can fall back to APR-CL primality test when Miller-Rabin does not work. In my personal opinion, it would be best to keep prime.rb simple because it is a hobby library.

You may be interested in my gem: https://github.com/mame/faster_prime

#### Updated by steveb3210 (Stephen Blackstone) 11 months ago

On second thought, I think Marc is right, we can't ruin someones day with a composite without a warning that theres a non-zero probability of it being incorrect so I will update......

#### Updated by steveb3210 (Stephen Blackstone) 9 months ago

**File***patch_with_argument_error.diff*added

#### Updated by steveb3210 (Stephen Blackstone) 9 months ago

**File***patch_with_argument_error.diff*added

#### Updated by steveb3210 (Stephen Blackstone) 9 months ago

**File**deleted ()*patch_with_argument_error.diff*

#### Updated by steveb3210 (Stephen Blackstone) 9 months ago

**File***patch_with_argument_error_and_tests.diff*added

#### Updated by steveb3210 (Stephen Blackstone) 9 months ago

**File**deleted ()*patch_with_argument_error.diff*

#### Updated by steveb3210 (Stephen Blackstone) 9 months ago

**File**deleted ()*patch_with_argument_error_and_tests.diff*

#### Updated by steveb3210 (Stephen Blackstone) 9 months ago

**File***patch_with_argument_error_and_tests.diff*added

- Add bounds check
- Add test

#### Updated by Dan0042 (Daniel DeLorme) 9 months ago

I think it would be interesting to expose the algorithm for larger numbers. So you could have `miller_rabin`

which allows any integer, and `prime?`

which checks the value and either call `miller_rabin`

or raise ArgumentError.

#### Updated by steveb3210 (Stephen Blackstone) 9 months ago

Dan0042 (Daniel DeLorme) wrote in #note-15:

I think it would be interesting to expose the algorithm for larger numbers. So you could have

`miller_rabin`

which allows any integer, and`prime?`

which checks the value and either call`miller_rabin`

or raise ArgumentError.

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.

#### Updated by steveb3210 (Stephen Blackstone) 9 months ago

**File**deleted ()*patch_with_argument_error_and_tests.diff*

#### Updated by steveb3210 (Stephen Blackstone) 9 months ago

**File**prime_patch.diff prime_patch.diff added

Attached is the latest diff.

#### Updated by Dan0042 (Daniel DeLorme) 9 months ago

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 bounds check and `miller_rabin(13)`

to produce a deterministic result.

BTW your implementation appears to be off by one. It should be: if self >= 3317044064679887385961981 then raise ArgumentError. You could also slightly reduce the runtime for small numbers by using `return list.include?(self) if self <= list.last`

before the loop, instead of checking inside the loop.