Using CUDA to find better SPRP classifiers

[SPWorley]

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.

[zerothbase]

inspired by your work:
if n < 316349281 and is a 11000544, and 31481107-SPRP, then n is prime.

[CRGreathouse]

Very cool, I'll have to look this over later.

[Mr. P-1]

The obvious extension to this would be to augment the Miller-Rabbin test with a lookup table of pseudoprimes.

[CRGreathouse]

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.

[zerothbase]

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

[henryzz]

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.

[wizykowski]

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?

[zerothbase]

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.

[wizykowski]

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.

[henryzz]

Has anyone ever written a sprp test for pfgw(a script)? It normally does only a prp test.