mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2011-04-20, 14:20   #12
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×3×977 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 View Post
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
CRGreathouse is offline   Reply With Quote
Old 2011-04-20, 15:37   #13
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

7·11·131 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
xilman is online now   Reply With Quote
Old 2011-04-20, 16:56   #14
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25·233 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-04-20, 17:02   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164408 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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)
R.D. Silverman is offline   Reply With Quote
Old 2011-04-20, 17:11   #16
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·1,429 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
ATH is offline   Reply With Quote
Old 2011-04-20, 17:51   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

745610 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-04-20, 18:43   #18
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·1,429 Posts
Default

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
ATH is offline   Reply With Quote
Old 2011-04-20, 18:50   #19
zerothbase
 
Mar 2011

2·5 Posts
Default

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.
zerothbase is offline   Reply With Quote
Old 2011-04-20, 19:59   #20
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by zerothbase View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-04-20, 20:09   #21
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×1,429 Posts
Default

Quote:
Originally Posted by zerothbase View Post
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.
ATH is offline   Reply With Quote
Old 2011-04-20, 23:12   #22
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×3×977 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Do normal adults give themselves an allowance? (...to fast or not to fast - there is no question!) jasong jasong 35 2016-12-11 00:57
How to Check if Non-Mersenne Number isPrime? FloatingPoint Operation Billion Digits 39 2015-10-21 02:15
How fast is the dog? Andi47 Puzzles 20 2009-04-01 02:35
I wonder how fast this is... ixfd64 Hardware 1 2005-11-21 21:28
Fast way to square??? maheshexp Math 2 2004-05-29 01:54

All times are UTC. The time now is 07:27.

Tue Jul 14 07:27:06 UTC 2020 up 111 days, 5 hrs, 0 users, load averages: 1.42, 1.64, 1.72

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.