...for the first person to find Optimus Prime...
The largest known prime number, made up over 24 million digits, has been discovered by a lone IT professional quietly crunching numbers with an Intel-powered computer in December. Patrick Laroche, a 35-year-old from Ocala, Florida, chanced upon the goody by running the free Great Internet Mersenne Prime Search (GIMPS) software …
You're generate these every time (with a probability very close to 1) every time you create an RSA keypair. The primes you're likely to generate are probably unknown in the sense there are very many more of these, which are very easily discoverable, than the number of atoms in the observable universe - let's say that's 10**82. Start with 2048 bits of random noise output from /dev/random seeded with a good noise generator , make the last bit 1 so it's odd, then test it a few times with Fermat's Little Theorem and Rabin Miller tests, and if not prime add 2, and retest it until it is prime. There are approximately 2**2037 primes lower than 2**2048, which is a very large number compared to the number of atoms in the universe. So unknown primes are very numerous and easy to find and if useful for crypto are very much smaller than the largest known primes. The latter have millions of bits, while those useful for cryptography are likely to have thousands of bits.
If the number of atoms in the universe is only a few hundred bits long, it follows that the primes you're likely to generate for cryptography couldn't be stored if every atom in the universe were to be turned into a single memory cell which could be used to store one of these.
"correction: 2^(2^n) + 1 3, 5, 17, 257, 65537"
That's not a correction, that's an addendum. You are not correcting what I said, merely adding to it. I didn't feel the need to state that the exponent needed to be a power of 2, because doing the pre-factorization into cyclotomic polynomials isn't necessary to demonstrate the point.
The proof that the exponent of a Fermat prime is a power of 2 is (almost) a one-liner.
If k has an odd factor m (say k = m*n, where m≥3 is odd) then (by an algebraic factorisation) it is trivial to show that 2^n+1 divides 2^k+1 = 2^(m*n)+1 [e.g. 2^2+1 divides 2^10+1]. So if 2^j+1 is prime, then j has no odd factors ≥3, hence j is a power of 2.
"That might just about cover his electricity bill then."
Given it's only a fairly common place CPU, 12 days of crunching on an i5 wouldn't have cost that much.
Might be a lot different if it had been crunched on a 1st or 2nd generation Butterfly Labs Bitcoin miner, which were extremely inefficient...they were pretty good as central heating fans in fact !!
Mersenne primes, when written out in full, equal 2^n - 1 where n is the exponent needed to generate the prime and is used to form the codename.
Can anybody explain what the qualifier phrase "when written out in full" means? Aren't Mersenne primes always equal to 2^n - 1 (for some integer n) regardless of how they're written?
As in, the full prime number, equals (2^n)-1 where n is the exponent that generates the prime. There are two numbers at play here: the prime number, calculated by (2^n)-1, and n, the exponent. 82,589,933 is not the prime number, it is the exponent that produces the final prime, which is what we were trying to drive at.
If you wrote out the full number, all 23 million digits of it.
A dozen = 12
A googol = 10^100. Written in full: 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000.
2^23 million - 1 = 1...............................................1
I just checked, it does not calculate correctly.
OK, devide the exponate by 4 this gives you the number in hex with the fractional part (.25 or .75) determening the leading diget (a 1 or a 7) the rest being the hex diget F.
This one has a fractional part of .3 so it is not a Mersenne.
(I could show the math on that but it is kind of long)
If the number of Mersenne primes is finite, there is a largest Mersenne prime, call this Mlargest. This is a prime number from which the number (2^Mlargest)-1 can be derived. Because this can not be a prime, it should be the product of two or more primes. At least one of its factors is expected to be larger than Mlargest.
Happy computing, or better: Do some hard thinking.
"Mlargest. This is a prime number from which the number (2^Mlargest)-1 can be derived. Because this can not be a prime, it should be the product of two or more primes. At least one of its factors is expected to be larger than Mlargest."
Congratulations, you have proved that large numbers exist.
Problems with your proof:
1) All factors could be smaller than Mlargest.
2) The factors need not be Mersenne primes.
There's a reason that some problems are hard. It's not that mathematicians are bumbling idiots.
"Computing the n-th Mersenne prime "
I'm not certain, but my recollection is that they are not calculating the sequence of Mersenne primes, and that if we had a method for calculating the n-th one then there is a possible inductive proof of the finite/infinite nature of them.
What we have is a method of creating potential Mersenne primes (as described in the article) using existing primes and methods to test if these are in fact prime.
"does not add a iota to the the proof that the set of Mersenne primes is finite, infinite or that this is an undecidable conjecture."
Wasn't your "proof" attempting to show that they are in fact finite? Perhaps I misunderstood.
Being able to compute continually larger Mersenne primes may not prove that they are infinite, but may be close enough for practical purposes. In the same way you can't prove linear optimizations are efficient, but in application they are, the set of Mersenne primes may be large enough to be close enough to infinity for the purpose at hand.
Congratulations, you have proved that large numbers exist.
No, I did not (although they exist), because the proposed large number critically depends on the proposition that the set of Mersenne primes is finite.
BTW, The association of mathematicians with idiots, bumbling or otherwise, is entirely yours.
"This is a prime number from which the number (2^Mlargest)-1 can be derived. Because this can not be a prime"
Please submit some proof of this. If you start with the assumption that Mlargest is the largest, then simply asserting that there are no larger Mersenne primes is a fallacy.
Essentially the argument presented is: Assume p is true: Therefore p is true.
Ignoring this, lets move on to the next part:
"Because this can not be a prime, it should be the product of two or more primes. At least one of its factors is expected to be larger than Mlargest."
I'll just let the bad math slide, and stick with conclusions. Even if one of the factors is prime and larger than Mlargest (note, you've not actually proved that such a factor exists or is in fact prime), then you still need to show the factor is not only prime, but a Mersenne prime.
I'm looking forward to your proof of P = nP
Apparently it just involves some hard thinking :D
This post has been deleted by a moderator
I talk, Hello everyone and good afternoon. The question, do you think, is, it easy to calculate a simple number without a computer, if the total sum of numbers is 10 ^ 32, and the number of prime numbers is only one and a half to two percent. Do you think this can be done on a calculator with a probability of 10%. So one of the numbers = 2 ^ 104 + 25. Please check and write the answer on the site ..
Biting the hand that feeds IT © 1998–2021