mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2009-07-25, 03:48   #1
SPWorley
 
Jul 2009

31 Posts
Default 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
File Type: pdf worley-SPRPsearch.pdf (47.2 KB, 319 views)

Last fiddled with by SPWorley on 2009-07-25 at 04:28
SPWorley is offline   Reply With Quote
Old 2011-03-07, 22:16   #2
zerothbase
 
Mar 2011

2·5 Posts
Default

inspired by your work:
if n < 316349281 and is a 11000544, and 31481107-SPRP, then n is prime.
zerothbase is offline   Reply With Quote
Old 2011-03-08, 01:47   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

586210 Posts
Default

Very cool, I'll have to look this over later.
CRGreathouse is offline   Reply With Quote
Old 2011-03-10, 14:06   #4
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

The obvious extension to this would be to augment the Miller-Rabbin test with a lookup table of pseudoprimes.
Mr. P-1 is offline   Reply With Quote
Old 2011-03-10, 17:03   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

586210 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2011-03-10, 23:42   #6
zerothbase
 
Mar 2011

2·5 Posts
Default

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
File Type: txt sprpLiars.java.txt (1.7 KB, 192 views)
zerothbase is offline   Reply With Quote
Old 2011-03-13, 20:03   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

13×19×23 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2011-04-06, 12:48   #8
wizykowski
 
Apr 2011

316 Posts
Default

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?
wizykowski is offline   Reply With Quote
Old 2011-04-14, 04:03   #9
zerothbase
 
Mar 2011

2·5 Posts
Default

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
File Type: zip SPRP-Pairs.zip (3.0 KB, 150 views)
zerothbase is offline   Reply With Quote
Old 2011-06-28, 15:24   #10
wizykowski
 
Apr 2011

3 Posts
Default

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
wizykowski is offline   Reply With Quote
Old 2011-06-29, 16:11   #11
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

10110001100012 Posts
Default

Has anyone ever written a sprp test for pfgw(a script)? It normally does only a prp test.
henryzz is offline   Reply With Quote
Reply

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 2015-07-10 06:08
Miller-Rabin Strong Probable Prime Test (SPRP) fenderbender Miscellaneous Math 22 2010-11-11 01:04
SPRP pseudoprime search. 3.14159 Miscellaneous Math 6 2010-07-14 23:00
Find the Value davar55 Puzzles 7 2009-07-02 19:46
Find the Value davar55 Puzzles 25 2007-07-15 15:56

All times are UTC. The time now is 12:51.

Tue Jul 14 12:51:10 UTC 2020 up 111 days, 10:24, 1 user, load averages: 1.37, 1.60, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.