[perl6/specs] 5277fe: Add expmod and is-prime as built-ins in Int

[GitHub]

Branch: refs/heads/master
Home: https://github.com/perl6/specs
Commit: 5277fefed694bbdfc3e5da1022ceaf5aacb6d344
https://github.com/perl6/specs/commit/5277fefed694bbdfc3e5da1022ceaf5aacb6d344
Author: Larry Wall <la...@wall.org>
Date: 2012-09-19 (Wed, 19 Sep 2012)

Changed paths:
M S32-setting-library/Numeric.pod

Log Message:
-----------
Add expmod and is-prime as built-ins in Int

[Martin D Kealey]

On Wed, 19 Sep 2012, GitHub wrote:
> Log Message:
> -----------
> Add expmod and is-prime as built-ins in Int

> +Returns True if C<$x> is known to be a prime, or is likely to be a
> +prime based on a probabilistic Miller-Rabin test. (The optional
> +argument tells how many times to iterate the probabilistic test,
> +if such is necessary.)
> +
> +Returns False if C<$x> is known not to be a prime, or is unlikely to
> +be a prime after probabilistic testing.

Isn't Miller-Rabin definitive when it disproves primality? In which case the
probabilistic qualifier in the last paragraph isn't needed.

Or is this just to allow that some better (presumably faster or more probable)
non-deterministic primality test might be used in the future? (Though
Miller-Rabin is already pretty fast, so there seems little reason not to
incorporate it as part of any future test.)

But in that case, we should be saying up front that the test might change.

-Martin

[Stephen Pollei]

On Thu, Sep 20, 2012 at 11:36 AM, Martin D Kealey
<mar...@kurahaupo.gen.nz> wrote:
> On Wed, 19 Sep 2012, GitHub wrote:
>> Log Message:
>> -----------
>> Add expmod and is-prime as built-ins in Int
>
>> +Returns True if C<$x> is known to be a prime, or is likely to be a
>> +prime based on a probabilistic Miller-Rabin test. (The optional
>> +argument tells how many times to iterate the probabilistic test,
>> +if such is necessary.)
>> +
>> +Returns False if C<$x> is known not to be a prime, or is unlikely to
>> +be a prime after probabilistic testing.
>
> Isn't Miller-Rabin definitive when it disproves primality? In which case the
> probabilistic qualifier in the last paragraph isn't needed.

Yes iirc correctly if the Miller-Rabin test determines it is not prime
then it is certainly not prime. If it says it might be prime it's
about a 50% 50% split if it's correct. Each test cycle is suppose to
be fairly independent.
so if it survives 1 round it's 50% prime 50% not-prime
2 75% 25%
3 87.5% 12.5%
4 93.75% 6.25%
so the certainty that it is prime approaches 1
as the number of tests approaches log2 of the number then there should
be less chance of a false positive than there are numbers in that
range.

perhaps it should return a float in the range of 0 to 1 ;-)

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.

>
> Or is this just to allow that some better (presumably faster or more probable)
> non-deterministic primality test might be used in the future? (Though
> Miller-Rabin is already pretty fast, so there seems little reason not to
> incorporate it as part of any future test.)
>
> But in that case, we should be saying up front that the test might change.

maybe multimethod signature should allow you to pass in a test, but
provide one by default?

[Martin Kealey]

On Thu, 20 Sep 2012, Stephen Pollei wrote:
> If it says it might be prime it's
> about a 50% 50% split if it's correct.

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).

> 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!)

If "tries" is negative, which idiom should we follow:
* a range iterator (empty, zero tries, return true)
* arrays etc count-backwards-from-the-end (keep trying until certain)
* a logical ambiguity (return Any(true,false))
* you-get-what-you-ask-for (return "PEBKAC":but(false) )
* a logical contradiction (return an unthrown exception)
* a formal error (throw an exception)

-Martin

[Stephen Pollei]

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.

[Richard Nuttall]

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.

[Solomon Foster]

On Mon, Sep 24, 2012 at 10:09 AM, Richard Nuttall
<richard...@pirum.com> wrote:
> 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.

Niecza's implementation of is-prime already takes advantage of this,
and my understanding of Rakudo's implementation is that it always
tests against the first 256 primes, so it also takes advantage of this
in correctness, if possibly not in speed.

--
Solomon Foster: col...@gmail.com
HarmonyWare, Inc: http://www.harmonyware.com