20110525, 08:07  #34  
May 2011
France
161_{10} Posts 
speed
Quote:
2 hours to compute the first 200 000 000 of primes so 7200 secondes 7200/200000000= 0,000036 sec by prime ang 1 000 000 000 of values are tested 7200 / 1000000000= 0,0000072 I don't find It's slow. You can go faster with a stieve (not ErashotÃ¨ne) but it more hard to programme I give the time for DIVISION methoid:This method is slow and like you I use an other(Fermat) It seems that you make a small mistake If the value has 20 digits and is a primes product necessary on of the factor is smaller than 2^32 So if you have all the primes smaller 2^32 you are sur th find the other Liike you have 200 000 000 of primes soif uin fact the value is prime you will make 200 000 000 of divisions. Let Primes be an array with the 200M of primes for i:=1 to nb_Primes do If A mod Primes[ I]=0 then trouve John 

20130818, 07:19  #35  
"Dana Jacobsen"
Feb 2011
Portland, OR
2^{2}·3^{2}·5^{2} Posts 
I realize this is an old thread, but thought it wouldn't hurt to add a little.
Quote:
Using my C code on an x86_64 that takes advantage of asm mulmod (ty WraithX!), doing a SPSP2 + AESLSP test on a prime takes as long as ~ 2.7 MR tests. A strong LucasSelfridge test takes longer, but since the range is fixed and none have counterexamples, we can use whichever one of the above is fastest for us. For 32bit, the hash with single test seems like the winner. Albeit only two MR tests are needed up to 1050M now, but still if we're after the best possible performance, a hash plus 1 test is better than 13 (three tests is the most needed for 32bits). For 64bit, at least on x86_64 and probably gcc+Power7, I think BPSW is faster than MR tests. Your actual results may vary depending on implementation details. A hash to 3 tests vs. 4 would be murkier. I like the simplicity of testing the Lucas test vs. the hash, but some may disagree. Note that using the SPSP2 database as a test sample is misleading for benchmarks. By definition these are all composites that pass the SPSP2 test. The BPSW test will have to run its full test (SPSP2 which of course will pass, then the Lucas test which will fail). For the particular set of bases in zerothbase's code, it also will run a SPSP2 test, but then most numbers will fail the next base. Swap the two initial bases and it will run almost twice as fast on this data set since almost everything will be weeded out on the first MR test. While I suppose it is application specific, in general one would want to test on random inputs that have made it through the initial smallfactor checks (Steve checks to 7, Jim to 2, I found improvements on random inputs using up to 7 followed by up to 53). Interestingly, with GMP on a 200bit prime I found my ESLSP test to run about the same speed as 6 MR tests, and the SLSP test about the same as 8 MR tests. I assume this is due to GMP greatly optimizing the mpz_powm internals. The two other GMP Lucas implementations I've compared run slower than mine, and it's faster than Pari's implementation on large numbers, so this isn't just poor coding of the Lucas test. This might be useful to know for someone looking at using GMP on a 32bit machine for 64bit results. Once past 64 bits, some form of BPSW is a better choice than MR tests for most purposes. (quoting from over 2 years ago). Using BPSW below 2^64 would seem to give one a proven prime based on the computerassisted proof of FeitsmaGalway (exhaustive list of PSP2's under 2^64) plus verification of the particular Lucas test used. The BLS75 proofs (even just theorem 5 for factors of N1) are awfully fast for most small (< 128bit) numbers, but you still have to verify the primality of each factor found, which means more tests. 

20180728, 13:02  #36 
Jul 2018
1 Posts 
This table of hashes can be used to test a 64 bit number for primality. For 49 bit numbers it requires 1 or 2 sprp tests depending on the number. 64 bit numbers can be tested with 1, 2, or 3 sprp tests.
https://techneon.com/download/is.prime.64.base.data This next table is for testing 32 bit numbers. It uses a single sprp test. https://techneon.com/download/is.prime.32.base.data It would be helpful if anyone could independently verify the tables. 
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 