Prime numbers

shelanachium

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?

CRGreathouse

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.

Howers

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.

mgb_phys

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.

shelanachium

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?

mgb_phys

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.

CRGreathouse

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 be" other primes between Mersenne primes? Between the largest two Mersenne primes known, there are approximately 5.5 x 10^9808349 other primes. That's a lot of primes!

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.

CRGreathouse

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.

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.

Werg22

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

CRGreathouse

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.

Werg22

I was speaking a little too fast. Sorry.

mgb_phys

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.

CRGreathouse

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