A quick search throws up http://primes.utm.edu/prove/prove2_3.html
Which says that for/n/< 341,550,071,728,321 it is enough to test 2, 3,
5, 7, 11, 13 and 17 to be definitive (and fewer specific tries for
smaller n)
That also verifies the 75/25 figures mentioned below.
So, depending on the implementation, the documentation should be able to
be explicit about how accurate it is.
R.
On 21/09/2012 06:32, Stephen Pollei wrote:
On Thu, Sep 20, 2012 at 9:22 PM, Martin Kealey <mar...@kurahaupo.gen.nz> wrote:
On Thu, 20 Sep 2012, Stephen Pollei wrote:
According to Wolfram, it's 75/25; so a positive result after 10 iterations
leaves about a one-in-a-million chance of being composite (more precisely,
one in 1048576).
I'd believe wolfram over me, it's been a while since I've read Applied
Cryptography by Schneier .
multi method is-prime ( Int $x: Int $tries = 100) is export
should also at least document that tries is never a negative number,
or if it is that it has same behaviour as zero.
Logically if "tries" is zero, is-prime shouldn't do any testing at all, and
should always return "true". (There's a chance it might be prime!)
A good built in test before you try Miller-Rabin is at least test
against some of the small prime numbers 2,3,5,7,11,13 otherwise even
if if tries is zero saying 42 is prime is too wrong . However if only
a miller-rabin style tests are used then a value of tries being zero
should always return true.
If "tries" is negative, which idiom should we follow:
multi method is-prime ( Int $x: UInt $tries = 100) is export
I think I read somewhere that perl6 has both Int and UInt , just
change the prototype
multi method is-prime ( Int $x: UInt $tries = 100 where { $^n > 0 } ) is export
I think I even read you can constrain it so if zero tries is
completely useless you can outlaw it
so document at least or change prototype to account for negative and
zero values.
