20110420, 14:20  #12  
Aug 2006
5,807 Posts 
Quote:
Do you think this would be faster than three MR tests for 64bit 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 20110420 at 15:09 

20110420, 15:37  #13  
Bamboozled!
May 2003
Down not across
10010111011111_{2} Posts 
Quote:
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 20110420 at 15:41 Reason: Add P.S. 

20110420, 16:56  #14  
Nov 2003
7309_{10} Posts 
Quote:
part up to N^1/6 for both (or N^1/3 for either N1 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. FrobeniusGrantham is indeed about 3x slower than MR. 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 32bit N anyway. 

20110420, 17:02  #15  
Nov 2003
7,309 Posts 
Quote:
What is really needed is to have enough KNOWN FACTORS of N1, 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 APRCL 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) 

20110420, 17:11  #16  
Einyen
Dec 2003
Denmark
5321_{8} Posts 
Quote:
"Furthermore, preliminary analysis by Gilchrist of Feitsma's database, further extended, indicates that no BailliePSW 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 LucasSelfridge 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. 

20110420, 17:51  #17  
Nov 2003
7,309 Posts 
Quote:


20110420, 18:43  #18 
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/index2to64.html (statistics: http://www.janfeitsma.nl/math/psp2/statistics )
are a LucasSelfridge prp including all the Fermat base2 prps. Took abit over 1 hour for the list. Last fiddled with by ATH on 20110420 at 18:44 
20110420, 18:50  #19  
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 2SPRP list, and I've been told: Quote:
The question wasn't "is there a way to prove 64bit 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. 

20110420, 19:59  #20  
Nov 2003
7309_{10} Posts 
Quote:
64 bits. 

20110420, 20:09  #21  
Einyen
Dec 2003
Denmark
3·13·71 Posts 
Quote:
http://www.trnicely.net/misc/bpsw.html "However, a BailliePSW test typically requires roughly three to seven times as many bit operations as a single MillerRabin test." and R.D. Silverman says it takes 2 x SPRP. So it might compete with 4 bases SPRP test with proper coding. 

20110420, 23:12  #22  
Aug 2006
13257_{8} Posts 
Quote:
At those speeds even just a billion numbers take an hour. Reducing that to 15 or 20 minutes would be great. 

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  20161211 00:57 
How to Check if NonMersenne Number isPrime?  FloatingPoint  Operation Billion Digits  39  20151021 02:15 
How fast is the dog?  Andi47  Puzzles  20  20090401 02:35 
I wonder how fast this is...  ixfd64  Hardware  1  20051121 21:28 
Fast way to square???  maheshexp  Math  2  20040529 01:54 