20190610, 19:11  #1 
Aug 2006
2×2,963 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 7501000 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.

20190610, 19:30  #2  
Sep 2002
Database er0rr
7×491 Posts 
Quote:
Last fiddled with by paulunderwood on 20190610 at 19:36 

20190610, 20:24  #3 
Aug 2006
2×2,963 Posts 

20190610, 20:34  #4 
Sep 2002
Database er0rr
7×491 Posts 
I don't know of an offtheshelf 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 20190610 at 20:36 
20190610, 21:09  #5 
"Robert Gerbicz"
Oct 2005
Hungary
1,409 Posts 
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. 
20190610, 21:14  #6 
"Ben"
Feb 2007
CDF_{16} 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 builtin 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. 
20190610, 21:18  #7 
Sep 2002
Database er0rr
6555_{8} Posts 
I presumed Charles wanted to start with an arbitrary N. If this is not the case, there are offtheshelf 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 3PRP's for k*2371#+1, k in [50000000000, 94000000000] somewhere on a backup DVD.

20190611, 02:02  #8  
Aug 2006
2·2,963 Posts 
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:
Code:
testrange(10^1000,10^1000+10^9,3999999979,1) Last fiddled with by CRGreathouse on 20190611 at 02:07 

20190611, 02:53  #9  
"Ben"
Feb 2007
5·659 Posts 
Quote:


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