mersenneforum.org Using CUDA to find better SPRP classifiers
 Register FAQ Search Today's Posts Mark Forums Read

2009-07-25, 03:48   #1
SPWorley

Jul 2009

378 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:

• If n < 170,584,961 is a 350 and 3958281543-SPRP, then n is prime.
• If n < 75,792,980,677 is a 2, 379215, and 457083754-SPRP, then n is prime.
• If n < 21,652,684,502,221 is a 2, 1215, 34862, and 574237825-SPRP, then n is prime.
Attached Files
 worley-SPRPsearch.pdf (47.2 KB, 455 views)

Last fiddled with by SPWorley on 2009-07-25 at 04:28

 2011-03-07, 22:16 #2 zerothbase   Mar 2011 2·5 Posts inspired by your work: if n < 316349281 and is a 11000544, and 31481107-SPRP, then n is prime.
 2011-03-08, 01:47 #3 CRGreathouse     Aug 2006 3×1,993 Posts Very cool, I'll have to look this over later.
 2011-03-10, 14:06 #4 Mr. P-1     Jun 2003 7×167 Posts The obvious extension to this would be to augment the Miller-Rabbin test with a lookup table of pseudoprimes.
 2011-03-10, 17:03 #5 CRGreathouse     Aug 2006 10111010110112 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. P-1 said.
2011-03-10, 23:42   #6
zerothbase

Mar 2011

2·5 Posts

Below are the liars under signed int (2^31-1) 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
Attached Files
 sprpLiars.java.txt (1.7 KB, 312 views)

 2011-03-13, 20:03 #7 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 595810 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.
 2011-04-06, 12:48 #8 wizykowski   Apr 2011 3 Posts Me and my colleague have also found interesting SPRP sets. We have found that: if n < 49,141 is a 921211727-SPRP, then n is prime (best 32-bit witness). if n < 132,239 is a 814494960528-SPRP, then n is prime. if n < 227,132,641 is a 660 and 56928287-SPRP, then n is prime. if n < 105,936,894,253 is a 2, 1005905886, and 1340600841-SPRP, then n is prime. if n < 31,858,317,218,647 is a 2, 642735, 553174392 and 3046413974-SPRP, then n is prime. if n < 3,071,837,692,357,849 is a 2, 75088, 642735, 203659041 and 3613982119-SPRP, then n is prime We described our results and the computational approach at http://priv.ckp.pl/wizykowski/sprp.pdf Could you reveal zerothbase some details about your approach?
2011-04-14, 04:03   #9
zerothbase

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 13745309-SPRP, 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.
Attached Files
 SPRP-Pairs.zip (3.0 KB, 271 views)

 2011-06-28, 15:24 #10 wizykowski   Apr 2011 38 Posts I made the website summarizing records of SPRP bases sets: http://miller-rabin.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 2011-08-08 at 21:59
 2011-06-29, 16:11 #11 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 2×32×331 Posts Has anyone ever written a sprp test for pfgw(a script)? It normally does only a prp test.

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Programming 18 2015-07-10 06:08 fenderbender Miscellaneous Math 22 2010-11-11 01:04 3.14159 Miscellaneous Math 6 2010-07-14 23:00 davar55 Puzzles 7 2009-07-02 19:46 davar55 Puzzles 25 2007-07-15 15:56

All times are UTC. The time now is 18:56.

Fri Jan 28 18:56:12 UTC 2022 up 189 days, 13:25, 1 user, load averages: 1.76, 1.58, 1.51