- #1

- 41

- 0

## Main Question or Discussion Point

Absolutely enormous primes are known these days. It is not possible that all primes are known up to the largest ones one sees mentioned. So how far up is EVERY prime known?

- Thread starter shelanachium
- Start date

- #1

- 41

- 0

Absolutely enormous primes are known these days. It is not possible that all primes are known up to the largest ones one sees mentioned. So how far up is EVERY prime known?

- #2

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

- #3

- 445

- 3

- #4

mgb_phys

Science Advisor

Homework Helper

- 7,774

- 12

There may also be other primes between Mersenne primes that have been missed.

- #5

- 41

- 0

Many cryptographical systems depend on the use of multiples of vast primes. It is not computationally feasible to factorise such numbers, which keeps these systems secure.

Yet if the known vast primes are a minute subset of all primes, and are found by such methods as those used to find Mersenne primes, does this not mean these systems are easier to crack than if all lower primes were known?

- #6

mgb_phys

Science Advisor

Homework Helper

- 7,774

- 12

The exta interest in Mersennes is that it gives you a starting point that is more likely to be prime - if all you are interested in is finding a very large number.

Crypto doesn't need such large primes, ussually a 100 digits is enough.

For eg. RSA you just find a couple of 100 digit prime numbers ( there a few tricks to guess if a number is less likely to be prime to save time checking it).

Then multiply the two numbers together.

The encryption is based on it being difficult to find which two numbers you used - since the cracker doesn't get to pick probable primes - they have to check all possible factors of the 200 digit multiple.

You wouldn't use mersenne primes as your factors simply because there are very few the correct size and they are well known.

- #7

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

The software you're thinking of is GIMPS' version of p95, which finds only Mersenne primes.

There's a reward for the first person who finds a 10 million digit prime, regardless of whether it's Mersenne or not. If you find a new Mersenne prime below 10 million digits (unlikely!) there's no prize.

GIMPS finds only Mersenne primes. Other projects focus on other things, of course, since GIMPS is best at Mersenne primes Seventeen or bust, for example, tries to prove the Seirpinski conjecture.

There may also be other primes between Mersenne primes that have been missed.

There "may be" other primes between Mersenne primes? Between the largest two Mersenne primes known, there are approximately 5.5 x 10

It's obvious by their form that Mersenne primes are of density [itex]O(\log n)[/itex], so that they are a tiny fraction of primes.

Many cryptographical systems depend on the use of multiples of vast primes. It is not computationally feasible to factorise such numbers, which keeps these systems secure.

Yet if the known vast primes are a minute subset of all primes, and are found by such methods as those used to find Mersenne primes, does this not mean these systems are easier to crack than if all lower primes were known?

Proving primes and factoring numbers are entirely different tasks, and the complexity of the two are quite different. Finding Mersenne primes is done with the Lucas-Lehmer algorithm; proving general primes is best done with (multiprocessor) ECPP; factoring general numbers is best with GNFS. Proving numbers to be prime can be done in polynomial time (and so is in P, the class of "easy" problems), while factoring numbers is not believed to be possible in classical polynomial time.

Factoring can be done in quantum polynomial time thanks to Shor's algorithm, but I'm not aware of any numbers larger than 15 (!) which have been factored with this method.

Last edited:

- #8

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

No! It's much easier to prove that a number is a Mersenne prime than to prove the primality of a number of similar size. LL is a fast special-purpose algorithm.It's just as hard to check if any given number is prime wether it is Mersenne or not.

Check all possible factors? Not nearly... there are much faster methods than that. But factoring is significantly harder than proving primality, as you correctly point out.The encryption is based on it being difficult to find which two numbers you used - since the cracker doesn't get to pick probable primes - they have to check all possible factors of the 200 digit multiple.

- #9

- 1,425

- 1

What do you mean tiny subset? There are infinitely many Mersenne primes and infinitely many non-Mersenne primes, and both sets are well-ordered.

Many cryptographical systems depend on the use of multiples of vast primes. It is not computationally feasible to factorise such numbers, which keeps these systems secure.

Yet if the known vast primes are a minute subset of all primes, and are found by such methods as those used to find Mersenne primes, does this not mean these systems are easier to crack than if all lower primes were known?

- #10

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

1. Mersenne primes have not, as far as I know, been proven to be infinite. If you know of a proof, I'd love a reference (or link).What do you mean tiny subset? There are infinitely many Mersenne primes and infinitely many non-Mersenne primes, and both sets are well-ordered.

2. I imagine "tiny subset" refers to the natural density of the Mersenne primes in the primes, which is 0. The primes equal to 1 mod 4 have natural density 0.5 in the primes, the titanic primes have natural density 1 in the primes, etc.

- #11

- 1,425

- 1

I was speaking a little too fast. Sorry.

- #12

mgb_phys

Science Advisor

Homework Helper

- 7,774

- 12

Yes it's O(1) to check if a number is a mersenne prime - there are only 44 of them!No! It's much easier to prove that a number is a Mersenne prime than to prove the primality of a number of similar size.

I mean't that mersenne primes have no real relevance to ayn fast factoring algorithms that would effect crypto.

- #13

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

It only becomes O(1) if there are finitely many Mersenne primes and we find all of them. :)Yes it's O(1) to check if a number is a mersenne prime - there are only 44 of them!

I mean't that mersenne primes have no real relevance to ayn fast factoring algorithms that would effect crypto.

Yes, you're right that Mersenne primes have no apparent application to factoring in crypto. Apparently, though, there's a cool 'new' application for locally decodable codes using Mersenne primes. Now that seems like information theory rather than crypto, but if that is possible, who knows? Mersenne primes might just end up being used there somehow. Certainly I could imagine it, especially if the hypothetical method requires fast multiplications (since Mersennes are often used in FFT methods) or decent random generators (Mersenne Twister).

http://www.math.ias.edu/~yekhanin/Papers/phdthesis.pdf

- Replies
- 10

- Views
- 18K

- Last Post

- Replies
- 5

- Views
- 2K

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 8

- Views
- 1K

- Last Post

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 15

- Views
- 7K

- Last Post

- Replies
- 1

- Views
- 566

- Last Post

- Replies
- 19

- Views
- 1K