20120531, 16:51  #1 
Aug 2010
Kansas
547 Posts 
Finding VERY large primes
I have a question for the smarties on the forum :)
(Bob, david, chalsall, JH, et al.) I am interested in finding a million digit (base 10) prime, but have access only to a somewhat limited cluster I've compiled (1015 GHzDays/day). I was wondering, what form of number should be "easiest" to find a prime for? Also, how far/long should these be sieved? As a side, could someone explain the weight system for Riesel numbers in layman's terms? Thanks! Johann 
20120531, 17:00  #2 
"Vincent"
Apr 2010
Over the rainbow
3^{2}×11×29 Posts 
weight system:
number of term remaining after sieving to 1e9(not sure about 1e9) a range of 10k n value Last fiddled with by firejuggler on 20120531 at 17:01 
20120531, 18:24  #3 
Jun 2009
1010111100_{2} Posts 
Please allow me to ask for clarification what exactly you want. Is it important that you do it all from scratch i.e. find a number that is your find exclusively? Or would it be OK to do LLR tests on candidates that someone else has sieved?
At CRUS there are several bases in the Megadigit range or close to it, like R6. But these are fixedk with growing n, so the tests get longer rather fast. If you want to go from scratch, here's what I would do: 1) Pick a base and exponent. Riesel or Sierpinski should not matter. I remember Riesel being faster to LLR but I think this is outdated. Base 2 is fastest, so you need n>3321928. Now n=3333333 looks nice, but these nice numbers are usually already being worked on. So better pick something unpopular. 2) Calculate how many candidates you need. For a million digits the probability of a random number being prime is ~ one in a million. I like to start with a good deal more so the probability of finding something is higher. Sieving time does not grow linearly with the number of candidates, so it's not too bad. You might decide to use 1<k<5000000, using odd k's only. 3) Use NewPGen to start the sieve. 4) I am just now realizing that I do either fixedk searches or twins, triples etc. So I am not sure what is the fastest sieving software for what you are doing. PPSieve probably. But I'll leave that for others to answer. Use [suggested software] to continue sieving. 5) LLR time depends a lot on the size of n (which is fixed for you), but also a bit on k. So LLR test a candidate with an average k value. Continue sieving until finding a factor takes as long as LLR testing a candidate. 6) LLR test all remaining candidates until you find a prime. Good luck! 
20120531, 21:28  #4 
"Mark"
Apr 2003
Between here and the
6849_{10} Posts 
Did you mean a number in the form k*10^n+/1 (with small k and n > 1e6) or any base as long as the number has more than 1 million decimal digits?
You can only use ppsieve for a range of k and base 2. It won't work on other bases. Note that PrimeGrid and NPLB are already sieving/testing k < 10000. I don't recall if ppsieve can use any range of k or if the range of k must start with 3. If you want to bypass sieving (which would save you a lot of time), I recommend the Mega Prime search on PRPNet over at PrimeGrid. If you want to do it alone and not on base 2, you need to use srsieve and sr1sieve. Choose a k with a high weight, i.e. a k that will sieve poorly. The reasoning is that as n gets larger tests take longer and if k has a low weight, the gaps between n to be tested will be higher. The Proth/Nash weight can be computed in a couple of different ways. IIRC, the way it is normally computed is by sieving for p < 512 from n=1 to n=10000. The difficulty of computing with that method is that if k is larger than 512, then the weight will be adversely affected as fewer n are removed. For CRUS, I use the range of n from 100001 to 110000 (the same size as the classical definition), but sieve for p < 1e6. When comparing a number of k across different bases, I found this to be a much more accurate computation for the number of n one would have to test in a given range. It isn't perfect, but it works much better than the classical definition. To compute the weight, d/l the latest version of srsieve (v1.0.4, a link can be found in the CRUS forum). Depending upon the k used, srsieve can eliminate candidates with algebraic factorizations thus reducing the weight for that k. 
20120601, 00:54  #5 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
3^{2}·11·109 Posts 
<pseudocode>
Code:
num = 1 count = 1 do while log10(num)<1000000 num = num * prime(count) wend num = num +1 print num you are welcome Last fiddled with by Uncwilly on 20120601 at 00:54 
20120601, 01:42  #6  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×937 Posts 
Quote:
N = 2^a 3^b 5^c 7^d 11^e ... + 1; There are MANY candidates. They are easy to sieve. Once you find a prp, exhibiting a primitive root is then easy because N1 is fully factored. Or you could use Maurer's algorithm. Or my improvement to Maurer's algorithm. > start with a known (say) 32bit prime x0. Compute x1 = x0 * a + 1 with a any random integer slightly smaller than x0^2. a can run thru an A.P. in order to sieve. Now testing x1 for primality is easy because the factorization of x1  1 is known up to x1^(1/3) . Use the combined theorem [in the Cunningham book] of Brillhart, Lehmer, Selfridge. REPEAT. This triples the size of the prime at each iteration. [Maurer's algorithm doubles the size at each iteration by choosing a slightly smaller than x0 rather than x0^2] 

20120601, 01:46  #7  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×937 Posts 
Quote:
it serve? 

20120601, 01:52  #8 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·47·109 Posts 

20120601, 12:40  #9 
"Mark"
Apr 2003
Between here and the
3^{2}×761 Posts 
The question from the OP wasn't clear. He stated "megadigit (base 10) prime". I didn't know if he meant that the number would be a mega binary digit prime or a mega decimal digit prime. Was "base 10" stated to differentiate between binary and decimal digits or is he looking for a number of the form k*10^n+/1 that can be PRP tested with llr or pfgw faster than a generic form?
Regarding the rest of your post, I think that would be beyond many forum members capabilities. 
20120601, 16:27  #10 
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 

20120601, 19:09  #11 
Aug 2010
Kansas
547 Posts 
Assume
I meant the former :P
So, if I'm going to do this separate of CRUS or Riesel drives, I should pick a ~3.4M n with variable k's (2=exponent), and scan about a 5M range for k values? Also, since Bob brought up the 2^a*3^b...n^x+1 topic, I have another question...Is there a program/program combo that would allow me to calculate and store 3^2E for b1=1,000,000? How long/ much storage would it take? Last fiddled with by c10ck3r on 20120601 at 19:17 Reason: Only kidding... 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Best Work for Finding Primes  Unregistered  Information & Answers  9  20120624 13:50 
New method of finding large prime numbers  georgelouis@mac  Math  41  20110125 21:06 
Finding the square root of a large mersenne number  Fusion_power  Math  29  20101014 17:05 
newbie question  finding small factors of very large numbers  NeoGen  Math  7  20070313 00:04 
Finding primes with a PowerPC  rogue  Lounge  4  20050712 12:31 