Prime numbers

  • #1

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?
 

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
It's hard to answer that in a reasonable way, since no one really keeps a record of each sequential prime -- that would take up too much room. But surely every prime up to a trillion or quadrillion has been examined by a computer individually.
 
  • #3
445
3
I think they have software that constantly looks for the largest prime. If you run it on your computer and it finds a larger prime, you can get a cash reward.
 
  • #4
mgb_phys
Science Advisor
Homework Helper
7,774
12
The primes found by computer search such as GIMPS are almost always "Mersenne primes". These are of the form (2^N) -1, not all N are prime and so computers are used to check which are.
There may also be other primes between Mersenne primes that have been missed.
 
  • #5
That's my point. Mersenne primes must be a tiny subset of all 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?
 
  • #6
mgb_phys
Science Advisor
Homework Helper
7,774
12
It's just as hard to check if any given number is prime wether it is Mersenne or not.
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
I think they have software that constantly looks for the largest prime. If you run it on your computer and it finds a larger prime, you can get a cash reward.
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.

The primes found by computer search such as GIMPS are almost always "Mersenne primes". These are of the form (2^N) -1, not all N are prime and so computers are used to check which are.
There may also be other primes between Mersenne primes that have been missed.
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 be" other primes between Mersenne primes? Between the largest two Mersenne primes known, there are approximately 5.5 x 109808349 other primes. That's a lot of primes!

That's my point. Mersenne primes must be a tiny subset of all 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?
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.

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
It's just as hard to check if any given number is prime wether it is Mersenne or not.
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.

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.
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.
 
  • #9
1,425
1
That's my point. Mersenne primes must be a tiny subset of all 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?
What do you mean tiny subset? There are infinitely many Mersenne primes and infinitely many non-Mersenne primes, and both sets are well-ordered.
 
  • #10
CRGreathouse
Science Advisor
Homework Helper
2,820
0
What do you mean tiny subset? There are infinitely many Mersenne primes and infinitely many non-Mersenne primes, and both sets are well-ordered.
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).

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
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.
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.
 
  • #13
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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.
It only becomes O(1) if there are finitely many Mersenne primes and we find all of them. :)

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
 

Related Threads for: Prime numbers

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
Replies
19
Views
1K
Top