mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2019-06-10, 19:11   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

173416 Posts
Default 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.
CRGreathouse is offline   Reply With Quote
Old 2019-06-10, 19:30   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101101100012 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
paulunderwood is offline   Reply With Quote
Old 2019-06-10, 20:24   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111001101002 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Of course sieving first, if you can, is best (and trial factoring) and then PRP testing.
What siever would you recommend?
CRGreathouse is offline   Reply With Quote
Old 2019-06-10, 20:34   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·701 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
paulunderwood is offline   Reply With Quote
Old 2019-06-10, 21:09   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

3·11·43 Posts
Default

I'd sieve on k*2^n+1 with fixed n and small interval, say 0<k<2^32.
Then feed the survivors with openpfgw.
R. Gerbicz is offline   Reply With Quote
Old 2019-06-10, 21:14   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

23·419 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2019-06-10, 21:18   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101101100012 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
I'd sieve on k*2^n+1 with fixed n and small interval, say 0<k<2^32.
Then feed the survivors with openpfgw.
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.
paulunderwood is offline   Reply With Quote
Old 2019-06-11, 02:02   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

594010 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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 View Post
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
CRGreathouse is offline   Reply With Quote
Old 2019-06-11, 02:53   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

335210 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
primes : 270*(1000^1-1)/999+1 enzocreti enzocreti 6 2019-05-09 12:52
Optimal sieving of large n-ranges gd_barnes Conjectures 'R Us 13 2009-02-17 08:28
Fastest possible algorithm to calculate the square root of a 10,000,000 digit number Fusion_power Math 19 2007-11-02 21:37
An equation to generate all primes that uses 2 & 3 Carl Fischbach Miscellaneous Math 16 2007-10-10 16:43
Statistical Investigation of Large Digit Mersenne Primes . . . (please don't bite me) 9021951 Math 29 2005-03-15 16:26

All times are UTC. The time now is 15:32.

Sat Dec 5 15:32:53 UTC 2020 up 2 days, 11:44, 0 users, load averages: 2.17, 2.50, 2.40

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.