...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
BOINC has become a leader-board of burnt CPU time, when I last checked (November, it's not a regular thing) the famed posterchild for it, SETI@HOME had a broken science page with a big PHP error at the top and no content.
It saddens me that MAYBE some articles out there will link to a text file of it - and maybe some of those will have a scroll and go "it's indeed a big one" - but that'll be it.
Now I'm a mathematician technically, so I *love* abstract crap right.... I'd love to see "another BOINC" that rather than tying your computer to a project instead pooled it with "missions" (that you can opt out of if you *really* don't want whomever getting your cycles!) where the criteria for inclusion is the project must have some ending criteria even of the weak form "and if this *doesn't suck and actually works* we then refine the result until we've got a decent map of the thing we want to simulate's behavior for various initial conditions" - OR SOMETHING. At least:
1) It defines failure - so a big feasibility study that fails will still die
2) There are some criteria (if it does work) for completion - even if it is "and any finer and approximations at this scale are useless" - which is a very high bar to meet indeed.
I'd also like to add some notion of priority. That is "this long term sponge of ARSE@CRACK has had a good chunk for many months - this one project that's new would take 0.5% of daily capacity for 10 days - or we could just do it in like an hour and then give time back to ARSE"
If I may reach for the stars (I'm debating doing this) - I'd really like to lower the barrier to brute-forcing stuff that'd take more than like an hour on my computers - I'd love to "bank time" for myself (say I get 0.5 "work units" for every "work unit" I give to the system) as a lot of colleagues and me often have some numeric integral we need to evaluate once very accurately for the problem at hand. Or to test something other a large range.
The only problem with that last bit is the reduced trust barrier. I have a compiler fetish (it's weird. If this could make me a sex offender, totally guilty) which helps (a language to express the parallelism via work units and the problem, I've done something similar to exploit SIMD before - it'd be *something* that didn't require trust to run) - but even that is a possible solution - it'd also deal with different arches (I am always hoping to have something else I can buy instead of x86-64 - and I'm a little bit afraid of the 12 AVX-512 variations there are - not to mention permutations and the way they're just bolted on outside what is basically a Skylake core still.... we have GPUs too; I love talking about this and there's no reason it can't be iterated)
I digress, I've been seriously thinking about doing it for a while, but I'm not a "build it and they will come" - I've also worked out that with Intel chips (not got my hands on a Ryzen one yet) post Sandybridge (possibly Nealharm - core series) you can use "a bit above idle" without using much more power (intel_rapl is the kernel module, find it from there, you can measure power in real time) - that is to say if idling (with a web-browser, firefox always seems to be doing something even when the tabs are not according to about:performance) - for a little while the power increase with work is less than linear; and for small increases even with a huge sample none of my ("statistical" - I'm fit to do these. I didn't do all that measure theory crap for nothing!) tests lost to noise. So say you idle at 5-10% usage (ignore the fuzz of hyper threading for now) You can run at a "steady 12-14%" basically for free power wise. It gets more weird if you start bringing in AVX rather than sticking with XMM registers entirely or just SSE up to whatever version - BUT it can be done.
Biting the hand that feeds IT © 1998–2019