mersenneforum.org Fast isPrime() for n < 2^32
 Register FAQ Search Today's Posts Mark Forums Read

2011-04-20, 14:20   #12
CRGreathouse

Aug 2006

5,807 Posts

Quote:
 Originally Posted by R.D. Silverman You really should consider just a SINGLE MR test followed by either a Lucas test or a Frobenius-Grantham. There is no known pseudoprime for a single MR followed by a single Lucas test. (Preda Mihailescu and I looked for one without success).
That's what I already use for day-to-day probable-prime testing.

Quote:
 Originally Posted by R.D. Silverman If the objective is proved primes, one can just trial divide N-1 and N+1 to N^(1/6), and apply the Selfridge-Lehmer-Brillhart test that allows one to prove primality if enough factors of N-1 and N+1 are known.
Do you think this would be faster than three MR tests for 64-bit numbers? Either way you'd start with an MR test to weed out composites, and the combined test (given the factorization) should be slower than a single MR test, so it would be close. Fortunately not much trial division should be needed -- though don't you need factored part at least N^(1/6), not factoring up to N^(1/6)? That matters when you have a prime between two fairly rough numbers (e.g., members of A106639).

Last fiddled with by CRGreathouse on 2011-04-20 at 15:09

2011-04-20, 15:37   #13
xilman
Bamboozled!

May 2003
Down not across

100101110111112 Posts

Quote:
 Originally Posted by R.D. Silverman You really should consider just a SINGLE MR test followed by either a Lucas test or a Frobenius-Grantham. There is no known pseudoprime for a single MR followed by a single Lucas test. (Preda Mihailescu and I looked for one without success).
An innocent question: are the MR pseudoprimes to a particular base recorded anywhere? According to Feitsma's page there are only 32 million or so base-2 MR pseudoprimes under 2^64 --- though this is a preliminary result.

It seems to me that it should be easy enough to test them all with a Lucas test and settle the question completely.

Paul

P.S. Subsequent searching effectively answered my question in the affirmative but the expected completion date has now passed without any obvious updates to the publicly available information.

Last fiddled with by xilman on 2011-04-20 at 15:41 Reason: Add P.S.

2011-04-20, 16:56   #14
R.D. Silverman

Nov 2003

730910 Posts

Quote:
 Originally Posted by CRGreathouse That's what I already use for day-to-day probable-prime testing. Do you think this would be faster than three MR tests for 64-bit numbers? Either way you'd start with an MR test to weed out composites, and the combined test (given the factorization) should be slower than a single MR test, so it would be close. Fortunately not much trial division should be needed -- though don't you need factored part at least N^(1/6), not factoring up to N^(1/6)? That matters when you have a prime between two fairly rough numbers (e.g., members of A106639).
You are correct. Poor choice of words on my part. One needs factored
part up to N^1/6 for both (or N^1/3 for either N-1 or N+1). Of course,
if you just factor up to N^1/6 and the cofactor is prp, one can do a
descent to prove the latter prime.

Frobenius-Grantham is indeed about 3x slower than M-R.

What's fastest in practice? I don't know. I strongly suspect it would
be platform and implementation dependent. I would ask:

Does it really matter? Any reasonable technique will only take a few
microseconds for 32-bit N anyway.

2011-04-20, 17:02   #15
R.D. Silverman

Nov 2003

7,309 Posts

Quote:
 Originally Posted by R.D. Silverman You are correct. Poor choice of words on my part. One needs factored part up to N^1/6 for both (or N^1/3 for either N-1 or N+1). Of course, if you just factor up to N^1/6 and the cofactor is prp, one can do a descent to prove the latter prime. Frobenius-Grantham is indeed about 3x slower than M-R. What's fastest in practice? I don't know. I strongly suspect it would be platform and implementation dependent. I would ask: Does it really matter? Any reasonable technique will only take a few microseconds for 32-bit N anyway.
A further note: The N+1 and N-1 factorizations just disguise what is going on.

What is really needed is to have enough KNOWN FACTORS of N-1, N+1,
N^2 + 1, N^2 + N + 1, N^2 - N + 1, etc. (any other low degree
cyclotomic polynomial in N) so that the product of those factors
exceeds N^1/3.

The APR-CL algorithm is, in a sense, an extension of this. It uses
partial factorizations of many cyclotomic polynomials in N, to
complete the proof. 'Many' basically means all such polynomials up to degree
(log N)^(logloglog N)

2011-04-20, 17:11   #16
ATH
Einyen

Dec 2003
Denmark

53218 Posts

Quote:
 Originally Posted by xilman An innocent question: are the MR pseudoprimes to a particular base recorded anywhere? According to Feitsma's page there are only 32 million or so base-2 MR pseudoprimes under 2^64 --- though this is a preliminary result. It seems to me that it should be easy enough to test them all with a Lucas test and settle the question completely..
This has already been done: http://www.trnicely.net/misc/bpsw.html
"Furthermore, preliminary analysis by Gilchrist of Feitsma's database, further extended, indicates that no Baillie-PSW pseudoprime (standard or strong) exists below 2^64 (24 October 2009; double checking of this result is in progress), approximately 1.8446744e19."

But I just took the list of the 31,894,014 SPRP base2 < 2^64 and did a Lucas-Selfridge test on them, it took around 15min, and none of them are lucas PRP. So assuming doublechecking proves that the SPRP list is complete there is BPSW pseudoprime below 2^64.

2011-04-20, 17:51   #17
R.D. Silverman

Nov 2003

7,309 Posts

Quote:
 Originally Posted by ATH This has already been done: http://www.trnicely.net/misc/bpsw.html "Furthermore, preliminary analysis by Gilchrist of Feitsma's database, further extended, indicates that no Baillie-PSW pseudoprime (standard or strong) exists below 2^64 (24 October 2009; double checking of this result is in progress), approximately 1.8446744e19." But I just took the list of the 31,894,014 SPRP base2 < 2^64 and did a Lucas-Selfridge test on them, it took around 15min, and none of them are lucas PRP. So assuming doublechecking proves that the SPRP list is complete there is (no? (sic)) BPSW pseudoprime below 2^64.
A nice piece of work.

 2011-04-20, 18:43 #18 ATH Einyen     Dec 2003 Denmark 3·13·71 Posts In fact none of the 118,968,378 prps on the list: http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html (statistics: http://www.janfeitsma.nl/math/psp2/statistics ) are a Lucas-Selfridge prp including all the Fermat base2 prps. Took abit over 1 hour for the list. Last fiddled with by ATH on 2011-04-20 at 18:44
2011-04-20, 18:50   #19
zerothbase

Mar 2011

2×5 Posts

I believe the original intent of the thread was to find fast ways to prove primality up to a given limit.

It takes <3 minutes for my code to chew through the 2-SPRP list, and I've been told:

Quote:
 Originally Posted by geoff There are much faster methods than the mul/div asm version
So there has been an improvement from 15 minutes for BPSW to <3 minutes for my 4-MR tests (assuming the 15 minutes was done on modern HW).

The question wasn't "is there a way to prove 64-bit primality?", it was "how fast can we do it?". Offering BPSW is equally valid to offering factoring up to the square root - yes it works, but it doesn't tell me how fast it is.

2011-04-20, 19:59   #20
R.D. Silverman

Nov 2003

730910 Posts

Quote:
 Originally Posted by zerothbase I believe the original intent of the thread was to find fast ways to prove primality up to a given limit. It takes <3 minutes for my code to chew through the 2-SPRP list, and I've been told: So there has been an improvement from 15 minutes for BPSW to <3 minutes for my 4-MR tests (assuming the 15 minutes was done on modern HW). The question wasn't "is there a way to prove 64-bit primality?", it was "how fast can we do it?". Offering BPSW is equally valid to offering factoring up to the square root - yes it works, but it doesn't tell me how fast it is.
It takes as long as TWO Miller-Rabin tests. --> a few milliseconds at worst for
64 bits.

2011-04-20, 20:09   #21
ATH
Einyen

Dec 2003
Denmark

3·13·71 Posts

Quote:
 Originally Posted by zerothbase So there has been an improvement from 15 minutes for BPSW to <3 minutes for my 4-MR tests (assuming the 15 minutes was done on modern HW).
I didn't time it at all, I was only interested in the result, so the 15min was just a hunch, it could be anywhere from 10 to 20min. Also the code is purely GMP so could get a big improvement with the mulmod64 assembly code.

http://www.trnicely.net/misc/bpsw.html
"However, a Baillie-PSW test typically requires roughly three to seven times as many bit operations as a single Miller-Rabin test."

and R.D. Silverman says it takes 2 x SPRP. So it might compete with 4 bases SPRP test with proper coding.

2011-04-20, 23:12   #22
CRGreathouse

Aug 2006

132578 Posts

Quote:
 Originally Posted by R.D. Silverman What's fastest in practice? I don't know. I strongly suspect it would be platform and implementation dependent. I would ask: Does it really matter? Any reasonable technique will only take a few microseconds for 32-bit N anyway.
Of course it matters for this thread, since that's the whole topic. But I would say that it matters to me personally: I frequently find myself in the position of needing to test the primality of many (trillions) of small numbers, usually below 64 bits. At the moment I use PARI which takes about 3 microseconds. (Well, if you abuse it enough you can get to that speed anyway; the current version doesn't yet know about Jan's result and so if you ask it to prove primality it takes more like a millisecond.)

At those speeds even just a billion numbers take an hour. Reducing that to 15 or 20 minutes would be great.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 35 2016-12-11 00:57 FloatingPoint Operation Billion Digits 39 2015-10-21 02:15 Andi47 Puzzles 20 2009-04-01 02:35 ixfd64 Hardware 1 2005-11-21 21:28 maheshexp Math 2 2004-05-29 01:54

All times are UTC. The time now is 19:41.

Tue Feb 25 19:41:07 UTC 2020 up 25 days, 14:12, 2 users, load averages: 2.91, 2.74, 2.72