mersenneforum.org Fastest way to generate ranges of large (~1000 digit) primes?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-06-10, 19:11 #1 CRGreathouse     Aug 2006 3·1,993 Posts Fastest way to generate ranges of large (~1000 digit) primes? For wordsize primes, primesieve is probably the fastest program. But if I wanted to generate larger primes, is there fast software available? My current application wants something like 200,000 primes at 750-1000 digits, or higher if feasible. (The larger the primes, the more are needed.) But I feel that there could be many other applications beyond that at hand.
2019-06-10, 19:30   #2
paulunderwood

Sep 2002
Database er0rr

2×7×281 Posts

Quote:
 Originally Posted by CRGreathouse For wordsize primes, primesieve is probably the fastest program. But if I wanted to generate larger primes, is there fast software available? My current application wants something like 200,000 primes at 750-1000 digits, or higher if feasible. (The larger the primes, the more are needed.) But I feel that there could be many other applications beyond that at hand.
Around 1000 digits there is little difference between GWNUM (or PFGW), (maybe) GMP and Dana's Perl Module. At 2000 digits it may be worth a home made GWNUM program. Of course sieving first, if you can, is best (and trial factoring) and then PRP testing.

Last fiddled with by paulunderwood on 2019-06-10 at 19:36

2019-06-10, 20:24   #3
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by paulunderwood Of course sieving first, if you can, is best (and trial factoring) and then PRP testing.
What siever would you recommend?

2019-06-10, 20:34   #4
paulunderwood

Sep 2002
Database er0rr

75368 Posts

Quote:
 Originally Posted by CRGreathouse What siever would you recommend?
I don't know of an off-the-shelf one, but writing your own might be quicker than using PFGW's -f switch for TF. It may be that GMP's mpz_nextprime function uses a sieve, as might a similar function from Dana's NT Perl module.

Last fiddled with by paulunderwood on 2019-06-10 at 20:36

 2019-06-10, 21:09 #5 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 151810 Posts I'd sieve on k*2^n+1 with fixed n and small interval, say 0
 2019-06-10, 21:14 #6 bsquared     "Ben" Feb 2007 3·1,193 Posts The current release of yafu has a function called "testrange" that will first sieve, then run mpz_extrastrongbpsw_prp from wraithX's library on all surviving candidates. It has built-in multithreading for both the sieving and PRP checking. Just now I used it to find 5687 PRP's from the range 10^750 to 10^750+10^7 in just over 3 and a half minutes, using 8 threads. So, you could find 200k prps of size ~10^750 in a couple hours. No idea how that stacks up against other methods.
2019-06-10, 21:18   #7
paulunderwood

Sep 2002
Database er0rr

2·7·281 Posts

Quote:
 Originally Posted by R. Gerbicz I'd sieve on k*2^n+1 with fixed n and small interval, say 0
I presumed Charles wanted to start with an arbitrary N. If this is not the case, there are off-the-shelf sieves that will do b^n+k, k variable e.g. NewPGen. If you just want lots of primes then I have 261,601,878 3-PRP's for k*2371#+1, k in [50000000000, 94000000000] somewhere on a backup DVD.

2019-06-11, 02:02   #8
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by paulunderwood I presumed Charles wanted to start with an arbitrary N.
Right, arbitrary N. I started at 10^500 in an early test but really I should start somewhere away from powers and other strange numbers, lest they display statistically unusual properties.

Quote:
 Originally Posted by bsquared The current release of yafu has a function called "testrange" that will first sieve, then run mpz_extrastrongbpsw_prp from wraithX's library on all surviving candidates. It has built-in multithreading for both the sieving and PRP checking. Just now I used it to find 5687 PRP's from the range 10^750 to 10^750+10^7 in just over 3 and a half minutes, using 8 threads. So, you could find 200k prps of size ~10^750 in a couple hours. No idea how that stacks up against other methods.
Sounds great! Running

Code:
testrange(10^1000,10^1000+10^9,3999999979,1)
now, we'll see how that goes.

Last fiddled with by CRGreathouse on 2019-06-11 at 02:07

2019-06-11, 02:53   #9
bsquared

"Ben"
Feb 2007

3×1,193 Posts

Quote:
 Originally Posted by CRGreathouse Right, arbitrary N. I started at 10^500 in an early test but really I should start somewhere away from powers and other strange numbers, lest they display statistically unusual properties. Sounds great! Running Code: testrange(10^1000,10^1000+10^9,3999999979,1) now, we'll see how that goes.
Oh, wait! I think you will need to add either -pscreen or -pfile as a switch to that, to output to stdout or the (default) file primes.dat. Otherwise it might not output anything... I'm not in front of my computer to test it right now. Sorry... this is one of the lesser used/tested yafu functions.

 Similar Threads Thread Thread Starter Forum Replies Last Post enzocreti enzocreti 6 2019-05-09 12:52 gd_barnes Conjectures 'R Us 13 2009-02-17 08:28 Fusion_power Math 19 2007-11-02 21:37 Carl Fischbach Miscellaneous Math 16 2007-10-10 16:43 9021951 Math 29 2005-03-15 16:26

All times are UTC. The time now is 05:24.

Tue Nov 30 05:24:56 UTC 2021 up 129 days, 23:53, 0 users, load averages: 0.96, 1.26, 1.40