Extending math/big/ProbablyPrime(n) with Baillie-PSW

[jfcg...@gmail.com]

Greetings,

After reading Baillie-PSW primality test, a couple of papers & Go's implementation, I thought we had to have it ;)
I cleaned up & extended basic tests, added sprp(), slprp() & lucasMod() functions & tests. Everything seems to work fine.
Please see the attached patch (against master) & let me know what you think :)

Thanks..

[Keith Randall]

It's an interesting algorithm.

How much faster is it than Miller-Rabin for n=100, say?

I don't think it makes sense to put this in the stdlib. There are two main reasons:

1) having ProbablyPrime(n) for n <= 0 trigger your algorithm is hacky at best.  The name isn't even correct, as your algorithm is deterministic.

2) having no guarantee, even a probabilistic one, makes this algorithm not terribly useful.  Miller-Rabin gives you a strong probability guarantee regardless of the input.  Baillie-PSW only gives you "no one has found a counterexample yet".

It would be just as easy to make this a go-gettable library.

--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[jfcg...@gmail.com]

On Sunday, November 8, 2015 at 7:22:48 PM UTC+2, Keith Randall wrote:

It's an interesting algorithm.

How much faster is it than Miller-Rabin for n=100, say?

8 primes 660..990 bits in size, their pairwise products, totally 8+7*8/2=36 numbers on my core i5 4210m laptop:
MR(n=100) took 827.089748ms
BPSW took 288.061015ms
all results correct of course :)

I don't think it makes sense to put this in the stdlib. There are two main reasons:

1) having ProbablyPrime(n) for n <= 0 trigger your algorithm is hacky at best.  The name isn't even correct, as your algorithm is deterministic.

Sage & Pari/GP api is exactly like this. For n>0 they do n MRs, for n<=0 they do BPSW.

In number theory, probable prime means integers with certain properties. They are not necesarily a result of a stochastic calculation.
Choosing random bases does not improve detectability of MR(n)
 

2) having no guarantee, even a probabilistic one, makes this algorithm not terribly useful.  Miller-Rabin gives you a strong probability guarantee regardless of the input.  Baillie-PSW only gives you "no one has found a counterexample yet".

As far as I have read, BPSW is the state-of-the-art in primality testing, other than maybe Frobenius tests which is a generalization of lucas tests.

Lucas primality testing is a set of tests characterized by parameters P,Q and depends on Lucas sequences.
a^(n-1)-1 is also a Lucas sequence, hence MR is a special case of Lucas primality testing.
Say k is an integer to be tested. MR has (D/k) = 1 (D is the discriminant of the sequence). BPSW "complements" MR with a Lucas test with (D/k) = -1, that's why (among other reasons) it is so successful. Actually:
BPSW = MR(base=2) && Lucas( (D/k)=-1 )

Maple, Mathematica, Pari/GP, Sage, Maxima all have BPSW.

My $.02 :)

[jfcg...@gmail.com]

Hi,
Any other comments/suggestions ?
Should I submit for code-review ?

[alb]

IMHO the fact that "Maple, Mathematica, Pari/GP, Sage, Maxima" implement
BPSW does not say much.

A specialized platform for mathematical computation is one thing, another
thing is the standard library of a programming language.

A more apt comparison would be with the C, C++, D, Java, Python, Ruby, etc..
standard libraries. Do other languages implement primality testing BPSW?
And if not, why not?

[Keith Randall]

Make your own go-gettable library.  See if people use it.  Go packages and imports are designed to make it easy to provide services without putting them in the standard library.

See also https://groups.google.com/forum/#!topic/golang-dev/4XitbJPUa9A

--

[Russ Cox]

On Sun, Nov 8, 2015 at 4:02 PM, <jfcg...@gmail.com> wrote:

8 primes 660..990 bits in size, their pairwise products, totally 8+7*8/2=36 numbers on my core i5 4210m laptop:
MR(n=100) took 827.089748ms
BPSW took 288.061015ms

In addition to what everyone else said, n=100 for Miller-Rabin is way overkill. Using n=5 is just as good. That's a much easier and more significant performance improvement than a new algorithm.

Russ

[Uli Kunitz]

While I agree that n=100 for Miller-Rabin is overkill, don't assume that n=5 is a good value in all cases. The Digital Signature Standard FIPS 186-4 requires n up to 41 for auxiliary primes.

Uli

[jfcg...@gmail.com]

Hi,

Java stdlib has a similar isProbablePrime() that uses the Lucas test as well:
http://hg.openjdk.java.net/jdk7u/jdk7u/jdk/file/12d1f39ed743/src/share/classes/java/math/BigInteger.java

In today's cryptography, 128-bit security is considered solid minimum level of security for any serious application. To achieve that, we need to set n=64, which is conservative I think. Even for n=41 BPSW is much faster than MR(n).

Also there is no loss of functionality, we just extend the api with the current state-of-the-art test, just like many other math/science software/lang & Java.

Everything can be made a go-gettable library, that is not an argument. Why do we have Acosh() in the math package? Is it crucial for GoLang?

Stdlib is supposed to have 'the basics' to get app programmers started. It evolves as a language evolves. It needs to be 'complete'. If you have a stdlib, you must have a math package. If you have math, you need sine/cosine, Acosh just completes them. Riemann zeta function is not basic and it does not complete anything in stdlib, therefore it is excessive to have it there.

Jacobi, ProbablePrime are basics for a big int lib. My patch just improves & actually completes that api, that's it.

Thanks..

[Han-Wen Nienhuys]

On Wed, Nov 11, 2015 at 10:24 AM, <jfcg...@gmail.com> wrote:
>
> Everything can be made a go-gettable library, that is not an argument. Why do we have Acosh() in the math package? Is it crucial for GoLang?
>
> Stdlib is supposed to have 'the basics' to get app programmers started. It evolves as a language evolves. It needs to be 'complete'. If you have a stdlib, you must have a math package. If you have math, you need sine/cosine, Acosh just completes them. Riemann zeta function is not basic and it does not complete anything in stdlib, therefore it is excessive to have it there.
>
> Jacobi, ProbablePrime are basics for a big int lib. My patch just improves & actually completes that api, that's it.

Acosh cannot be removed because of the compatibility promise.

There is a big cost to putting anything in the standard library: they
have to be kept there forever, and no changes to their behavior can
ever be made. This is a big cost, and the cost had better be worth it.

In some cases, there might be an overriding reason to put it there
(eg. if the new functions need access to private data/code of the
library), but that is not the case here, is it?

Why don't you make it a go-gettable library? If it turns out that this
is overwhelmingly popular with everyone, it can always be put in the
std library at a later stage.

--
Han-Wen Nienhuys
Google Munich
han...@google.com

[Serhat Sevki Dincer]

11 Kas 2015 13:13 tarihinde "Han-Wen Nienhuys" <han...@google.com> yazdı:

> Acosh cannot be removed because of the compatibility promise.

It was an example for why it should be there. Do you really think I meant to remove it?
Also, in what way does my proposal break compatibility promise?

> There is a big cost to putting anything in the standard library: they
> have to be kept there forever, and no changes to their behavior can
> ever be made. This is a big cost, and the cost had better be worth it.

There is no change in existing behavior, we just extend the function for n<=0.
I agree with your maintenance concerns but it is not a big patch I think.

> In some cases, there might be an overriding reason to put it there
> (eg. if the new functions need access to private data/code of the
> library), but that is not the case here, is it?

Performance, having current algorithms for primality testing, completeness of a basic function in stdlib. These sound pretty good to me for reasons of inclusion.

> Why don't you make it a go-gettable library? If it turns out that this
> is overwhelmingly popular with everyone, it can always be put in the
> std library at a later stage.

Han, you are missing my point. A lucas test by itself does not justify a go-gettable library. Is this how you added Acosh() to stdlib in the first place? Did it become 'overwhelmingly popular' ?
That just sounds funny.

It is a backwards compatible improvement that is necessary for many number theory, crypto applications.

You sound like I am trying to add my custom lousy algorithm for calculating some absurd thing.
It is a popular established published algorithm for a basic function in math/big.

I'm surprised with the amount of resistance :)

[Manlio Perillo]

Il giorno mercoledì 11 novembre 2015 13:24:12 UTC+1, Serhat Sevki Dincer ha scritto:

11 Kas 2015 13:13 tarihinde "Han-Wen Nienhuys" <han...@google.com> yazdı:

> [...]

 

> Why don't you make it a go-gettable library? If it turns out that this
> is overwhelmingly popular with everyone, it can always be put in the
> std library at a later stage.

Han, you are missing my point. A lucas test by itself does not justify a go-gettable library. Is this how you added Acosh() to stdlib in the first place? Did it become 'overwhelmingly popular' ?

Sorry for the intrusion, but isn't it much more simple to add it to golang.org/x/math?

Regards  Manlio

[Serhat Sevki Dincer]

12 Kas 2015 00:58 tarihinde "Benjamin Measures" <saint....@gmail.com> yazdı:
>
> afaics, your patch adds nothing to the API apart from allowing negative integers to be ProbablePrime. Given the usual definition for a prime number[1], allowing this would be dubious.
> [1] http://mathworld.wolfram.com/PrimeNumber.html

n (of type int) is the number of MR rounds, not the input. Notice that we are talking about a function of the 'big' package.
Thanks to Andrew there is CoC set in place ^_^ cuz you just deserved a good compliment after all this discussion.

[Benjamin Measures]

On Wednesday, 11 November 2015 23:31:48 UTC, Serhat Sevki Dincer wrote:

12 Kas 2015 00:58 tarihinde "Benjamin Measures" <saint....@gmail.com> yazdı:
>
> afaics, your patch adds nothing to the API apart from allowing negative integers to be ProbablePrime. Given the usual definition for a prime number[1], allowing this would be dubious.
> [1] http://mathworld.wolfram.com/PrimeNumber.html

n (of type int) is the number of MR rounds, not the input. Notice that we are talking about a function of the 'big' package.

Yes, I realised and deleted not more than a few minutes after posting.

Still, your patch cannot "complete" an API by adding nothing to it. Interesting algorithm though.

[jfcg...@gmail.com]

Proposal issue with some explanations: https://github.com/golang/go/issues/13229

[jfcg...@gmail.com]

Current state of the patch against master for preview.

[Rob Pike]

We do not accept patches, and the code review tool makes it much easier to review changes compared to reading patches. Please read https://golang.org/doc/contribute.html to see how we do things.

-rob

--

[Russ Cox]

More generally, we don't tend to look at patches when considering proposals. The proposal decisions is about design, not code.

Russ