Why is there no IsPrime function for package big?

[PJOX]

Maybe this is not the time and place to ask for such feature, but given that Go is a opensource language; I thought it is worth at least to have the discussion.

First I have to make clear that I'm not what one would call a real programmer, I'm just a mathematics student who had previous experience with C and C++. This semester I took a "Scientific-Programming" class which was taught in Python, and I took the time to "translate" all my Python code to Go. In the end I found Go more appealing and even more appropriate for some tasks than Python; which was actually quiet impressive given that there is a lot of stuff for Scientific Programming written in Python.

Anyway, for one of the assignments I had to determine if a large number was prime. So I found that there is a function ProbablyPrime in the "math/big" package which was actually useful given that one can control its accuracy, but it is an implementation of the Miller-Rabin test which, as the name of the function suggest, is a probabilistic test.

So I thought, it would be really nice to see an implementation of something like the AKS test (which is a deterministic test that runs in polynomial time) in the "math/big" package.

Yes, I know that the Miller-Rabin test is good enough for most of the cases, but maybe, being a mathematics student makes me wish to have that feature for a language that I now like a lot.

[Jan Mercl]

On Sat, Apr 5, 2014 at 9:16 AM, PJOX <ortiz...@gmail.com> wrote:

For example: https://github.com/akalin/aks-go

For n <= math.MaxUint64 there's also:
http://godoc.org/github.com/cznic/mathutil#IsPrimeUint64 (MR with
deterministic base set for the given limit).

-j

[Rémy Oudompheng]

On 2014-04-05 9:26 GMT+02:00 Jan Mercl <0xj...@gmail.com>:

The problem with AKS is there is no known implementation or variation
which is useful in practice. I tried running this program with a
21-digit number (first prime after 1e20) and it didn't finish after 20
minutes of CPU, which makes it about a billion times slower than
Miller-Rabin which can be deterministic for numbers of that size using
appropriate bases. It is also slower than the naive algorithm of
dividing by all numbers up to the square root (which would need a few
billion divisions and run in several seconds).

I also tried a 100-digit number and it couldn't even get past the
first iteration and started eating more than 1GB of memory, which
indicates that the algorithm would not even be able to run with a
1000-bit number (due to RAM constraint, and the CPU time would be a
polynomial amount of years).

Using a FFT-based multiplication algorithm for the involved
polynomials may help a bit but not solve the memory requirement which
grows very rapidly.

The API would thus have very few practical purposes. An elliptic curve
test which produces a proof of primality would be more useful.

Rémy.

[Jan Mercl]

On Sat, Apr 5, 2014 at 10:14 AM, Rémy Oudompheng
<remyoud...@gmail.com> wrote:
> The API would thus have very few practical purposes. An elliptic curve
> test which produces a proof of primality would be more useful.

True. From [0]:

The following certification running times were obtained with Primo
using an Intel i7-2600 3.4GHz processor. (v4.0.4)

N = 10^999 + 7, running time 51.44s

[0]: http://www.ellipsa.eu/public/primo/primo.html

-j

[PJOX]

On Saturday, April 5, 2014 3:14:21 AM UTC-5, Rémy Oudompheng wrote:

The problem with AKS is there is no known implementation or variation
which is useful in practice. I tried running this program with a
21-digit number (first prime after 1e20) and it didn't finish after 20
minutes of CPU, which makes it about a billion times slower than
Miller-Rabin which can be deterministic for numbers of that size using
appropriate bases. It is also slower than the naive algorithm of
dividing by all numbers up to the square root (which would need a few
billion divisions and run in several seconds).

I was not aware of that; I mean, one would expect AKS to be slower than Miller Rabin, also knowing the size of the polynomials that the algorithm has to handle, one would also expect it to use a lot of memory, yet I find rather troublesome that it is slower than dividing by all primes up to the square root... but it seems that is the case. In fact I've found a paper which concludes AKS is not an effective test in practice: http://teal.gmu.edu/courses/ECE746/project/F06_Project_resources/Salembier_Southerington_AKS.pdf

On the other hand ECPP seems like a much better candidate for a fast deterministic test, and so it would be nice to have an implementation of that in Go :-)

There is also a "deterministic" version of Miller-Rabin test which relies on the Generalized Riemann Hypothesis, so I might try that as well.

Thank you for the information.

-PJ