mersenneforum.org Finding VERY large primes
 Register FAQ Search Today's Posts Mark Forums Read

 2012-05-31, 16:51 #1 c10ck3r     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 (10-15 GHz-Days/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
 2012-05-31, 17:00 #2 firejuggler     Apr 2010 Over the rainbow 2×1,217 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 2012-05-31 at 17:01
 2012-05-31, 18:24 #3 Puzzle-Peter     Jun 2009 29E16 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 fixed-k 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
 2012-05-31, 21:28 #4 rogue     "Mark" Apr 2003 Between here and the 19×313 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.
 2012-06-01, 00:54 #5 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 7×29×43 Posts 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 2012-06-01 at 00:54
2012-06-01, 01:42   #6
R.D. Silverman

Nov 2003

1C4016 Posts

Quote:
 Originally Posted by rogue 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?
Why restrict the form this way? Try numbers of the form

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 N-1 is fully factored.

Or you could use Maurer's algorithm. Or my improvement to Maurer's
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]

2012-06-01, 01:46   #7
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by R.D. Silverman Why restrict the form this way? Try numbers of the form 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 N-1 is fully factored. Or you could use Maurer's algorithm. Or my improvement to Maurer's algorithm. --> start with a known (say) 32-bit 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]
One question: What's the point of doing this???? What purpose does
it serve?

2012-06-01, 01:52   #8
LaurV
Romulan Interpreter

Jun 2011
Thailand

22·3·739 Posts

Quote:
 Originally Posted by c10ck3r I have a question for the smarties on the forum :) (Bob, david, chalsall, JH, et al.)
Me! Me! Me! Me! Pick me! Pick me!

2012-06-01, 12:40   #9
rogue

"Mark"
Apr 2003
Between here and the

19×313 Posts

Quote:
 Originally Posted by R.D. Silverman Why restrict the form this way?
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.

2012-06-01, 16:27   #10
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by rogue 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.
I assume the latter.

2012-06-01, 19:09   #11
c10ck3r

Aug 2010
Kansas

547 Posts
Assu-me

Quote:
 Originally Posted by R.D. Silverman I assume the latter.
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 2012-06-01 at 19:17 Reason: Only kidding...

 Similar Threads Thread Thread Starter Forum Replies Last Post Unregistered Information & Answers 9 2012-06-24 13:50 georgelouis@mac Math 41 2011-01-25 21:06 Fusion_power Math 29 2010-10-14 17:05 NeoGen Math 7 2007-03-13 00:04 rogue Lounge 4 2005-07-12 12:31

All times are UTC. The time now is 20:42.

Sat Oct 24 20:42:32 UTC 2020 up 44 days, 17:53, 0 users, load averages: 1.76, 1.69, 1.68