- #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?
The software you're thinking of is GIMPS' version of p95, which finds only Mersenne primes.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.
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.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.
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.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?
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.
What do you mean tiny subset? There are infinitely many Mersenne primes and infinitely many non-Mersenne primes, and both sets are well-ordered.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?
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.
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.
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.