Finding VERY large primes - Page 3

dann corbit · 2012-08-15, 07:07

Quote:

Originally Posted by Dubslow

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).

According to this link (possibly old):
http://en.wikipedia.org/wiki/Riesel_Sieve
only a single million+ digit prime has been found by that method.

I am very glad you pointed me to that method. I think I will give it a good perusal to see if I can understand the math behind it.

dann corbit · 2012-08-15, 07:16

Quote:

Originally Posted by LaurV

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.

In 2009 there were only 2 known Cullen numbers (which are 2 larger than their pair Woodall numbers) larger than a million digits:
http://primes.utm.edu/top20/page.php?id=6

Have a lot more been discovered now?

kar_bon · 2012-08-15, 09:11

Quote:

Originally Posted by dann corbit

According to this link (possibly old):
http://en.wikipedia.org/wiki/Riesel_Sieve
only a single million+ digit prime has been found by that method.

The Riesel-Problem searches for special cases of primes of the form k*2^n-1 with low Nash weights, so they are very hard to find.

Before searching for a million-digit prime, you should try several types of numbers to search for, to get a feeling (and understanding) what's going on.
Patience is a must-have and some luck, too.

If it would be easy to find 1M-digit primes, there should be more than 54 (as mentioned) in math history:
all of them are special types: Mersenne, Cullen, Woodall, Riesel, Proth (all Base 2) and Generalized Fermat.

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

Thanks to all for the excellent explanations and new topics to examine. I appreciate the informative, helpful replies and the friendly atmosphere here.

Brian-E · 2012-08-15, 11:40

Quote:

Originally Posted by Dubslow

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).

Just to be clear: GIMPS has in fact found 10 primes with more than a million decimal digits (and 3 smaller ones).

Apologies if I've misunderstood what you were saying ... but if I'm confused, then others might be too.

Dubslow · 2012-08-15, 20:01

Quote:

Originally Posted by Brian-E

Just to be clear: GIMPS has in fact found 10 primes with more than a million decimal digits (and 3 smaller ones).

Apologies if I've misunderstood what you were saying ... but if I'm confused, then others might be too.

1M != 10M

c10ck3r · 2012-08-28, 18:42

Sorry for beating the dead horse, but I hate new threads for every little question. This one is two-pronged. 1) How much space to save 3^2E for B1=10,000 using standard storage method (ie .bu file)? No "P" included...
And 2) If you take 3^2E mod 2^P-1, then take to the P power, mod 2^P-1, does this give the same result for B1=10,000 as doing it normally? How much longer/shorter would this be compared to the basic method for (largest exponent it could work for with 8 GB RAM)?
Thanks!

cheesehead · 2012-08-28, 19:59

Quote:

Originally Posted by c10ck3r

Sorry for beating the dead horse, but I hate new threads for every little question. This one is two-pronged. 1) How much space to save 3^2E for B1=10,000 using standard storage method (ie .bu file)? No "P" included...

(We're talking about the P-1 factoring method here.) 3^2E quickly becomes larger than 2^p-1. All the computation is done modulo 2^p-1, and the stored values are always residues modulo 2^p-1. Thus the storage space could be just the space needed to hold a p-bit-long value.

However, that value, as used in computation, is represented by an array of floating-point numbers, each mantissa of which holds some m bits of the p-bit number plus guard bits to protect against roundoff error. So, the space required for storage of this form of the number is the space needed to hold ceil(p/m) floating-point numbers.

Quote:

And 2) If you take 3^2E mod 2^P-1, then take to the P power, mod 2^P-1, does this give the same result for B1=10,000 as doing it normally?

Can you specify what is "normally"?

Since all the computations are done with modular arithmetic, the result should be the same in any case for which the formal result should be the same and for which the modular arithmetic is performed correctly.

Quote:

How much longer/shorter would this be compared to the basic method for (largest exponent it could work for with 8 GB RAM)?
Thanks!

I'm not sure what you are comparing. Can you be more specific?

c10ck3r · 2012-08-28, 20:40

Quote:

Originally Posted by cheesehead

(We're talking about the P-1 factoring method here.) 3^2E quickly becomes larger than 2^p-1. All the computation is done modulo 2^p-1, and the stored values are always residues modulo 2^p-1. Thus the storage space could be just the space needed to hold a p-bit-long value.

However, that value, as used in computation, is represented by an array of floating-point numbers, each mantissa of which holds some m bits of the p-bit number plus guard bits to protect against roundoff error. So, the space required for storage of this form of the number is the space needed to hold ceil(p/m) floating-point numbers.

Can you specify what is "normally"?

Since all the computations are done with modular arithmetic, the result should be the same in any case for which the formal result should be the same and for which the modular arithmetic is performed correctly.

I'm not sure what you are comparing. Can you be more specific?

Okay, let me clarify. I am wondering how much space would be needed to store the number 3^2E w/o mod arith. Normal is mentally (by me) defined as what Prime95 would do. I'm wondering to see whether a broad swath of B1=10k P-1's over all exponents less than 1B would be possible, not necessarily feasible.

fivemack · 2012-08-28, 20:47

Quote:

Originally Posted by c10ck3r

Okay, let me clarify. I am wondering how much space would be needed to store the number 3^2E w/o mod arith. Normal is mentally (by me) defined as what Prime95 would do. I'm wondering to see whether a broad swath of B1=10k P-1's over all exponents less than 1B would be possible, not necessarily feasible.

Suppose you have sixteen terabytes of disc array to devote to the problem - this is quite a lot of disc but not completely unreasonable, the hobbyists who computed pi to unprecedented numbers of digits used more.

Then you can store the digits of 3^{88 trillion} ( 2^47 * log(2)/log(3) ); but 88 trillion is substantially smaller than 2*3*5*7*11*13*17*19*23*29*31*37*41.

LaurV · 2012-08-29, 15:49

Well, now if you would have so much space, why to store the "3^" and not to store the exponent only? I mean the product. The reason we need the "3^" and generally "b^" part is because the product is not reducible mod Mp (it is however reducible mod (f-1)(g-1) where f, g are the factors of Mp, which we don't know). So, if we have so much memory, we can store the product of all the powers to a high B1, and then take only a single exponentiation of 3 (or b) for each p, mod Mp and a single GCD at the end.

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-08-15, 09:33	#26
dann corbit Dec 2008 2²·3 Posts	Thanks to all for the excellent explanations and new topics to examine. I appreciate the informative, helpful replies and the friendly atmosphere here.

2012-08-28, 18:42	#29
c10ck3r Aug 2010 Kansas 547 Posts	Sorry for beating the dead horse, but I hate new threads for every little question. This one is two-pronged. 1) How much space to save 3^2E for B1=10,000 using standard storage method (ie .bu file)? No "P" included... And 2) If you take 3^2E mod 2^P-1, then take to the P power, mod 2^P-1, does this give the same result for B1=10,000 as doing it normally? How much longer/shorter would this be compared to the basic method for (largest exponent it could work for with 8 GB RAM)? Thanks!

2012-08-29, 15:49	#33
LaurV Romulan Interpreter Jun 2011 Thailand 3²·29·37 Posts	Well, now if you would have so much space, why to store the "3^" and not to store the exponent only? I mean the product. The reason we need the "3^" and generally "b^" part is because the product is not reducible mod Mp (it is however reducible mod (f-1)(g-1) where f, g are the factors of Mp, which we don't know). So, if we have so much memory, we can store the product of all the powers to a high B1, and then take only a single exponentiation of 3 (or b) for each p, mod Mp and a single GCD at the end.