mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2012-05-31, 16:51   #1
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

547 Posts
Default 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
c10ck3r is offline   Reply With Quote
Old 2012-05-31, 17:00   #2
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

2×17×73 Posts
Default

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
firejuggler is online now   Reply With Quote
Old 2012-05-31, 18:24   #3
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22·132 Posts
Default

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<k<5000000, using odd k's only.

3) Use NewPGen to start the sieve.

4) I am just now realizing that I do either fixed-k 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!
Puzzle-Peter is online now   Reply With Quote
Old 2012-05-31, 21:28   #4
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

603510 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2012-06-01, 00:54   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

3×13×229 Posts
Default

<pseudocode>
Code:
num = 1
count = 1
do while log10(num)<1000000
num = num * prime(count)
wend
num = num +1
print num
</pseudocode>
you are welcome

Last fiddled with by Uncwilly on 2012-06-01 at 00:54
Uncwilly is offline   Reply With Quote
Old 2012-06-01, 01:42   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by rogue View Post
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
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]
R.D. Silverman is offline   Reply With Quote
Old 2012-06-01, 01:46   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2012-06-01, 01:52   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

7×1,279 Posts
Default

Quote:
Originally Posted by c10ck3r View Post
I have a question for the smarties on the forum :)
(Bob, david, chalsall, JH, et al.)
Me! Me! Me! Me! Pick me! Pick me!
LaurV is offline   Reply With Quote
Old 2012-06-01, 12:40   #9
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5·17·71 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
rogue is offline   Reply With Quote
Old 2012-06-01, 16:27   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by rogue View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2012-06-01, 19:09   #11
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

547 Posts
Default Assu-me

Quote:
Originally Posted by R.D. Silverman View Post
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...
c10ck3r is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Best Work for Finding Primes Unregistered Information & Answers 9 2012-06-24 13:50
New method of finding large prime numbers georgelouis@mac Math 41 2011-01-25 21:06
Finding the square root of a large mersenne number Fusion_power Math 29 2010-10-14 17:05
newbie question - finding small factors of very large numbers NeoGen Math 7 2007-03-13 00:04
Finding primes with a PowerPC rogue Lounge 4 2005-07-12 12:31

All times are UTC. The time now is 18:38.

Tue Dec 1 18:38:46 UTC 2020 up 82 days, 15:49, 2 users, load averages: 1.84, 2.50, 2.29

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.