20090725, 03:48  #1 
Jul 2009
31 Posts 
Using CUDA to find better SPRP classifiers
Last month I made a quick project to enter into the GECCO Genetic and Evolutionary computing contest. I didn't win, but I did come up with a fun topic to use GPUs to find better SPRP pairs for guaranteed prime number classification.
The papers, including mine, are all online at the GECCO site here. This was pretty straightforward to do in CUDA, mostly because the SPRP pair search only deals with values less than 2^32... no need for higher bigint math libraries. It was still hampered by GPUs very slow divides and modulus operators.. it was better to do those bitwise than use mod. It's not in the paper, but I did find decent results for 3 and 4 SPRP tests as well, but that code is a lot slower and if I ever want to do it efficiently I need to rework my algorithm. The results:
Last fiddled with by SPWorley on 20090725 at 04:28 
20110307, 22:16  #2 
Mar 2011
2·5 Posts 
inspired by your work:
if n < 316349281 and is a 11000544, and 31481107SPRP, then n is prime. 
20110308, 01:47  #3 
Aug 2006
5862_{10} Posts 
Very cool, I'll have to look this over later.

20110310, 14:06  #4 
Jun 2003
7·167 Posts 
The obvious extension to this would be to augment the MillerRabbin test with a lookup table of pseudoprimes.

20110310, 17:03  #5 
Aug 2006
5862_{10} Posts 
I'd like to see how much higher you could go by allowing a small number of counterexamples. This would be a harder search that wouldn't require so much of a rewrite (I would think).
Err, or what Mr. P1 said. 
20110310, 23:42  #6 
Mar 2011
2·5 Posts 
Below are the liars under signed int (2^311) for 11000544, 31481107, using the code in the attached java file.
Having no liars up to a high value is a generally a good indicator that it has few liars beyond that. But I wasn't really searching for "fewest Liars under 2^31". For example, there could be a pair that fails to see that 25 is composite (which my search would filter out immediately), but might have very few liars other than this up to a large value. Since this list is relatively short, it provide a fairly fast way to see if a number < 2^31 is prime: 1) If it is in the list, then it is composite. 2) Else return miller_rabin(value, [11000544, 31481107]) Though certainly not as fast as Worley's http://www.mersenneforum.org/showthread.php?p=182647, which only uses 1 miller rabin and a quick hash of the number. 316349281, 346305403, 368113411, 464305843, 478614067, 545738203, 574870753, 656824033, 659830621, 670567301, 688360333, 807115753, 808562791, 855073301, 903136901, 939369001, 970355431, 970560533, 972471151, 977770531, 1032101461, 1092902533, 1101623381, 1138289041, 1142300503, 1250656621, 1261099531, 1266482017, 1397169091, 1414892161, 1487387611, 1515175087, 1611615151, 1618435171, 1671276601, 1671603667, 1728960133, 1789167931, 1804182257, 1966146451, 1970097001, 1991063449, 2147022749 
20110313, 20:03  #7 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
13×19×23 Posts 
Another thing that might be worth checking looking for groups of bases that don't have any(or very few) liars after a small amount of trial factoring(upto something small like 20 or 50 maybe). The aim is being able to prove prps fast so I would expect a tiny bit of trial factoring in the real world.

20110406, 12:48  #8 
Apr 2011
3_{16} Posts 
Me and my colleague have also found interesting SPRP sets. We have found that:
Could you reveal zerothbase some details about your approach? 
20110414, 04:03  #9 
Mar 2011
2·5 Posts 
To some degree, I feel that finding any pairs above ~190 million is just plain luck. I found many pairs between 150 million and 190 million, but it seems to be very very rare to see anything beyond that, without extensive search power.
I changed my code constantly trying out different things, by restricting different parameters to varying levels. For example, the maximum of each witness, the number of liars for each witness below a certain value, the GCD of the witnesses to each other, the number/type of factors each witness can have. Basically just trying to restrict down the search space a little. I'm not even sure at this point what I used to find the one above. One of the primary things that helped speed up search is expectations. I restricted my searching to below 175 million, expecting that most pairs would never get anywhere close to that (based up on Worley's results). So I'd sieve to 175 million, then pick a random first witness (within whatever range I wanted) and find all the odd composite liars below 175 million. Then search for a second witness that would take me up as high as I could go. If it got above 150 million, I'd save the pair off and later do a quick test with some java code to see how far they actually go. I haven't been looking into triples and higher too much. Just screwing around a little, trying to find some patterns and parameters that seem useful, and got this: if n < 96,695,935,201 is a 2, 95331615, and 13745309SPRP, then n is prime. Which is obviously obsoleted by your result. Attached is a few of the results I got for trying to restrict the maximum of each of the witnesses. Also all the pairs I got over 150 million. I was hoping that some of the witnesses in these pairs would lead to other, better results. But from what I can tell there just seems to be a kind of symmetry with these pairs and they just work well with each other and not necessarily well with any other numbers. I'm sure someone with far better number theory skills than I will eventually come up with some formula to divine a way to find the best pair for a witness, but it is beyond me. 
20110628, 15:24  #10 
Apr 2011
3 Posts 
I made the website summarizing records of SPRP bases sets:
http://millerrabin.appspot.com (URL changed from http://priv.ckp.pl/wizykowski/sprp.php by fivemack at author's request 8/8/11) I encourage everyone to beat these records. Last fiddled with by fivemack on 20110808 at 21:59 
20110629, 16:11  #11 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
1011000110001_{2} Posts 
Has anyone ever written a sprp test for pfgw(a script)? It normally does only a prp test.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Where can I find a Reverse and Add program? I can't find any!  Stargate38  Programming  18  20150710 06:08 
MillerRabin Strong Probable Prime Test (SPRP)  fenderbender  Miscellaneous Math  22  20101111 01:04 
SPRP pseudoprime search.  3.14159  Miscellaneous Math  6  20100714 23:00 
Find the Value  davar55  Puzzles  7  20090702 19:46 
Find the Value  davar55  Puzzles  25  20070715 15:56 