Finding VERY large primes - Page 2

Batalov · 2012-06-01, 19:23

Finding megabit primes is fairly easy.

e.g. I have found nine. Therefore it must be easy.

Finding million-digit primes is not for the IGG. There's only 48 of them known ATM. Commit a CPU-decade and then maybe you will get something.

R.D. Silverman · 2012-06-01, 21:06

Quote:

Originally Posted by Batalov

Finding megabit primes is fairly easy.

e.g. I have found nine. Therefore it must be easy.

Finding million-digit primes is not for the IGG. There's only 48 of them known ATM. Commit a CPU-decade and then maybe you will get something.

It is an O(log(N)^(3 + o(1))) algorithm if FFT multiplies are used.
(i.e. to find a prime near N)

One must search, on average log(N) candidates. If one restricts to
numbers N such that the full factorization of N-1 is known (or even the
factorization of N-1 up to N^(1/3)) testing each candidate takes
O(log(N)) multiplies mod N. Each multiply takes O(log(N)^(1+o(1)))
using FFT's.

The implied constants are implementation and machine dependent.

davieddy · 2012-06-01, 23:58

Quote:

Originally Posted by c10ck3r

I have a question for the smarties on the forum :)
(Bob, david, chalsall, JH, et al.)

John Cooper Clarke

David

Puzzle-Peter · 2012-06-02, 06:14

Quote:

Originally Posted by R.D. Silverman

One must search, on average log(N) candidates. If one restricts to
numbers N such that the full factorization of N-1 is known (or even the
factorization of N-1 up to N^(1/3)) testing each candidate takes
O(log(N)) multiplies mod N. Each multiply takes O(log(N)^(1+o(1)))
using FFT's.

Just to make sure: this also applies when the factorization of N+1 is known up to N^(1/3), right?

Batalov · 2012-06-02, 06:33

3/10 of N+/-1 will do with Konyagin-Pomerance.

R.D. Silverman · 2012-06-02, 08:10

Quote:

Originally Posted by Puzzle-Peter

Just to make sure: this also applies when the factorization of N+1 is known up to N^(1/3), right?

Yes.

R.D. Silverman · 2012-06-02, 08:12

Quote:

Originally Posted by Batalov

3/10 of N+/-1 will do with Konyagin-Pomerance.

Yes, but K-P is very complicated.

Puzzle-Peter · 2012-06-02, 15:23

OK, back to the fastest way of finding a megadigit prime. What about using TPSieve? It does fixed-n which gives rather consistent LLR testing times. It's fast and it sieves +1 and -1 in one go.

Two ideas come to mind:

1) Do a "real" twin sieve. The remaining candidates are sieved for +/- 1 so you can duplicate the remaining candidate file and edit the two instances to be a +1 and a -1 input file respectively.

2) Start a +1 and a -1 sieve up to a rather small sieving limit. Combine the files (keep the originals), sort and edit to make a TPS input file. Sieve. Split the factor file into + and - and reduce the candidate files accordingly.

This is just an idea that came to mind while lawnmowing. I have not done any testing or benchmarking. What do you think of it?

dann corbit · 2012-08-15, 01:09

The fastest way to find a megadigit prime is to search for a Mersenne Prime. It might be possible to use APR-CL on numbers in the million digit range to test for primality, but I suspect that there are any known APR-CL implementations that even work on values of that size: http://primes.utm.edu/prove/prove4_1.html (~3000 digits is the max mentioned in the link above). Similarly, for the elliptical curve method the current record mentioned is 15,267 decimal digits at this site: http://www.ellipsa.eu/ AKS, while polynomial time, is not yet as fast for numbers of reasonable size as ecpp and apr-cl, according to this link: http://primes.utm.edu/prove/prove4_3.html The probabilistic methods while fast (e.g Miller-Rabin) can be fooled by Carmichael numbers: http://en.wikipedia.org/wiki/Primality_test So the answer to the OP's question, "What is the fastest way to find a million digit prime" has only one sensible answer: Join the GIMPS project. The smart-alec answer is to locate M38, or any of his big brothers (M39, M40...).

Dubslow · 2012-08-15, 01:22

With GIMPS it would not be easy to find a megadigit prime. Only three such primes have been found, and considering the large user base, being the next one to find the prime is incredibly unlikely. As mentioned above, there are 48 such primes known, many more than found by GIMPS.

What you're looking for is the LLR test (and the program named as such).

LaurV · 2012-08-15, 03:40

You don't do Mersenne if you want an "over megadigit prime", that would be stupid. There are better methods, you go for a Cullen, Woodall, GF number, etc.

And by the way, they are not 48 anymore, they are 54 now.

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

2012-06-01, 19:23	#12
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·47·101 Posts	Finding megabit primes is fairly easy. e.g. I have found nine. Therefore it must be easy. Finding million-digit primes is not for the IGG. There's only 48 of them known ATM. Commit a CPU-decade and then maybe you will get something.

2012-06-02, 06:33	#16
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·47·101 Posts	3/10 of N+/-1 will do with Konyagin-Pomerance.

2012-06-02, 15:23	#19
Puzzle-Peter Jun 2009 2²×3²×19 Posts	OK, back to the fastest way of finding a megadigit prime. What about using TPSieve? It does fixed-n which gives rather consistent LLR testing times. It's fast and it sieves +1 and -1 in one go. Two ideas come to mind: 1) Do a "real" twin sieve. The remaining candidates are sieved for +/- 1 so you can duplicate the remaining candidate file and edit the two instances to be a +1 and a -1 input file respectively. 2) Start a +1 and a -1 sieve up to a rather small sieving limit. Combine the files (keep the originals), sort and edit to make a TPS input file. Sieve. Split the factor file into + and - and reduce the candidate files accordingly. This is just an idea that came to mind while lawnmowing. I have not done any testing or benchmarking. What do you think of it?

2012-08-15, 01:09	#20
dann corbit Dec 2008 2²×3 Posts	The fastest way to find a megadigit prime is to search for a Mersenne Prime. It might be possible to use APR-CL on numbers in the million digit range to test for primality, but I suspect that there are any known APR-CL implementations that even work on values of that size: http://primes.utm.edu/prove/prove4_1.html (~3000 digits is the max mentioned in the link above). Similarly, for the elliptical curve method the current record mentioned is 15,267 decimal digits at this site: http://www.ellipsa.eu/ AKS, while polynomial time, is not yet as fast for numbers of reasonable size as ecpp and apr-cl, according to this link: http://primes.utm.edu/prove/prove4_3.html The probabilistic methods while fast (e.g Miller-Rabin) can be fooled by Carmichael numbers: http://en.wikipedia.org/wiki/Primality_test So the answer to the OP's question, "What is the fastest way to find a million digit prime" has only one sensible answer: Join the GIMPS project. The smart-alec answer is to locate M38, or any of his big brothers (M39, M40...).

2012-08-15, 01:22	#21
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3·29·83 Posts	With GIMPS it would not be easy to find a megadigit prime. Only three such primes have been found, and considering the large user base, being the next one to find the prime is incredibly unlikely. As mentioned above, there are 48 such primes known, many more than found by GIMPS. What you're looking for is the LLR test (and the program named as such).

2012-08-15, 03:40	#22
LaurV Romulan Interpreter Jun 2011 Thailand 3²×29×37 Posts	You don't do Mersenne if you want an "over megadigit prime", that would be stupid. There are better methods, you go for a Cullen, Woodall, GF number, etc. And by the way, they are not 48 anymore, they are 54 now.