Finding small primes (fast determanistic tests)

[CRGreathouse]

I'm looking for an algorithm or three to use in testing for prime numbers. I'm most concerned about those representable as ints or longs (that is, less than 2^63). In that range, what tests are efficient?

At the moment, I'm using a combination of:

* The naive division algorithm with a precomputed list of primes (the empyrically-derived cutoff is 5,500,000, checking primes up to 2341).
* Strong n-probable prime tests, plus bounds due to Jaeschke that turn this into a determanistic test. (2- and 3- SPrPs below 1,373,653 are prime; 2-, 3-, and 5- SPrPs below 25,326,001 are prime; 2-, 3-, 5- and 7- SPrPs below 118,670,087,467 are either 3,215,031,751 or prime; etc.)

The problem is that I don't know how to extend the latter test beyond 341,550,071,728,321 (testing all the primes up to 17), and I don't know if there's a faster method at some cutoff. Any help here?

Edit: Bleichenbacher has numbers that extend this test to 10^16, but I'd still like to go higher. Any thoughts?

 

[mathwonk]

about 25 years ago, Adelman, Pomerance and Rumely gave an enhancement of the fermat test to recognize primes, that got a lot of attention.

In the interim it has been further enhanced and there must be many of them out there. some more sophisticated using elliptic curves, have you searched on primality testing?

 

[mathwonk]

look here:
http://mathworld.wolfram.com/PrimalityTest.html

 

[CRGreathouse]

I'm quite familiar with the MathWorld primality testing page; I've read it over many times, and finished my most recent read though just a few minutes before posting here. It didn't seem to address my issue, which is why I posted here.

I'm also familliar with APR, though I'm a little confused about implementing it. Regardless, it doesn't seem relevant here; Cohen and Lenstra 1987 mentions testing numbrs "up to 213 decimal digits", and surely with the thousandfold increase in computing power since, not to mention theoretical improvements, its reach is further. I'm looking to test small integers -- less than 20 decimal digits (in particular, odd integers less than 2^63).

The elliptic curve algorithms seem to take a long time for small numbers, relatively speaking. I'm looking for something that will be fast for these sizes.

Since testing numbers in this range could take as many as about $$\text{Ri}(\sqrt{2^{63}-1})\approx 146,144,918$$ primes with the naive division algorithm, I'm looking for a faster way. I've been told that a good implementation of the naive algorithm is best for small numbers; in my testing, 5 million is the practical limit when other algorithms take over.

At the moment I'm using the test mentioned in my first post; between that and the division test, it calculates the primes under 50 million in about 29 seconds (~48 billion cycles, including idles). This is just for testing; if I really wanted to find that, I'd look into the wheel sieve.

 

[CRGreathouse]

In addition to
http://mathworld.wolfram.com/PrimalityTest.html
I would recommend Daniel Bernstein's
http://cr.yp.to/primetests.html
as a 'survey' of primality testing methods. I had hoped Chris Caldwell's page
http://primes.utm.edu/prove/prove2_3.html
would be relevant here, but it doesn't contain recent information (nothing since Jaeschke's 1993 paper). I also read these over carefully before posting, but saw no methods that struck me immediately as useful for my purpose (except the one I was already using).

I'd look at commercial or free math programs, but most of the ones I know use probable-prime methods internally rather than EXP, P or ZPP methods. PARI and Mathematica come to mind, for example.

 

[mathwonk]

you might ask carl pomerance: he is a nice guy.

carl.pomerance@dartmouth.edu

 

[CRGreathouse]

you might ask carl pomerance: he is a nice guy.

carl.pomerance@dartmouth.edu

That's... a great idea. Does he actually respond to mortals? I've sent him a quick note; I suppose I'll find out now.

 

[shmoe]

I'd look at commercial or free math programs, but most of the ones I know use probable-prime methods internally rather than EXP, P or ZPP methods. PARI and Mathematica come to mind, for example.

pari has deterministic tests, apcrl and Selfridge-Pocklington-Lehmer's p-1 test. (It has pseudoprime tests as well of course).

 

[CRGreathouse]

The good news is that Pomerance responded (rather rapidly and quite politely); the bad news is that he doesn't know of any more recent work in the area. He recommended n-1 tests for small primes, so I guess I'll look into whatever's fast for smallish numbers. Any recommendations?

pari has deterministic tests, apcrl and Selfridge-Pocklington-Lehmer's p-1 test. (It has pseudoprime tests as well of course).

Oh yes, I use PARI regularly. I meant in the basic isprime or equivilent. PARI's isprime uses Baillie-PSW by default, as I recall. There are a ton of methods it has built in, though, as you rightly mention.

 

[shmoe]

Oh yes, I use PARI regularly. I meant in the basic isprime or equivilent. PARI's isprime uses Baillie-PSW by default, as I recall. There are a ton of methods it has built in, though, as you rightly mention.

isprime runs the Baille-PSW test if it's guaranteed to work on the given input, which was something like up to 10^13 at the time of the last version, otherwise it uses spl or apcrl, whichever is appropriate (or you can force their use with flags in isprime).

In any case isprime only returns true for proven prime numbers (barring bugs of course).

 

[CRGreathouse]

isprime runs the Baille-PSW test if it's guaranteed to work on the given input, which was something like up to 10^13 at the time of the last version, otherwise it uses spl or apcrl, whichever is appropriate (or you can force their use with flags in isprime).

In any case isprime only returns true for proven prime numbers (barring bugs of course).

Ah, I was mistaken then. Still, it's not uncommon to use nondetermanistic/nonproven methods in such software, and PARI is no exception in general (though it is in this case): quadclassunit uses the GRH, and I think some of the bnf functons do too.

 

[shmoe]

pari does have an "ispseudoprime" function as well that's faster, but of course no guarantee you get a prime.