back to article Florida man stumbles on biggest prime number after working plucky i5 CPU for 12 days straight

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 …

  1. John 110
    Coat

    waiting patiently...

    ...for the first person to find Optimus Prime...

  2. Pat Att

    Mersenne

    Let's make the most of it. With a name like that they'll be harder to find after Brexit.

    1. Buzzword

      Re: Mersenne

      Godwin's law has been updated. Every online discussion now ends up with a tenuous link to Brexit.

      1. MiguelC Silver badge
        Unhappy

        Re: Mersenne

        Or Trump....

        1. Swarthy Silver badge
          Trollface

          Re: Mersenne

          Nah, that's still covered by the original Godwin.

      2. Andytug

        Re: Mersenne

        No, that should be a separate law...how about "Farage's Law"?

  3. vir Silver badge

    Hold Please

    I am verifying with pen and paper.

  4. JDX Gold badge

    If they're ann 2^n - 1, surely we have a list of which ones are found?

    1. Anonymous Coward
      Anonymous Coward

      We do...

      https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes (though you may want to verify them).

  5. Chris Miller
    Boffin

    I can already recite this number from memory (but only in hexadecimal).

    1. F Seiler

      Well, AFAICT it begins with a 1, but the tricky part ist probably getting the length of the remainder FFFFFF.... right

  6. 2+2=5 Silver badge

    > If they're ann 2^n - 1, surely we have a list of which ones are found?

    I think the author meant to say that there are unknown primes that are smaller than the larger, known Mersenne primes (because some will have been skipped).

    1. Chris Miller

      I think the point is that GIMPS doesn't search strictly sequentially (it can't, with millions of instances being run independently). So it's conceivable (but highly unlikely) that some as yet unchecked number could turn out to be a smaller Mersenne prime.

      1. JDX Gold badge

        Yes but we can have a list of which have been checked and of those which are primes.

        IIRC this one is 8 digits so the list is well under a billion items, quite manageable (if you just want to store flags not the actual number written out longhand)

    2. PyLETS

      Unknown primes

      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.

  7. Ken Shabby

    Obligatory xkcd https://xkcd.com/10/

  8. Inventor of the Marmite Laser Silver badge

    Is that like Amazon Prime but less unpleasant?

  9. Anonymous Coward
    Anonymous Coward

    "{...] and it's unknown if there are a finite or infinite number of Mersenne primes."

    If there are infinite possible numbers - then it seems intuitive that there will be infinite numbers of these primes?

    1. DavCrav Silver badge

      "If there are infinite possible numbers - then it seems intuitive that there will be infinite numbers of these primes?"

      What about primes of the form 2^n+1? These are called Fermat primes, and it is believe that there are only five of these.

      So your intuition is way off.

      1. Dr Paul Taylor

        Fermat primes

        correction: 2^(2^n) + 1 3, 5, 17, 257, 65537

        Gauss showed that regular polygons with this many sides can be constructed with ruler and compasses.

        1. Voyna i Mor Silver badge

          Re: Fermat primes

          "Gauss showed that regular polygons with this many sides can be constructed with ruler and compasses."

          For some value of ruler and compasses.

        2. PhilipN Silver badge

          Re: Ruler and compass

          Someone is going to have to tell me how long this may take.

          I am genuinely intrigued because I learnt just enough maths at school to understand there is a point to such exercises without knowing WTF it is.

        3. DavCrav Silver badge

          Re: Fermat primes

          "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.

          1. Richard Pennington 1

            Re: Fermat primes

            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.

    2. Spikey-Mike

      Intuitive possibly; the trick is to prove it;-)

    3. o p

      There is also an infinite number of even numbers.

      Prime is in P. I do not find it intuitive. Maybe you do?

      1. YetAnotherLocksmith

        Nonsense. The definition of a prime is that it can't be divided by any number other than itself and 1. The definition of an even number is that it ends in a number divisible by 2.

        There is only one even prime. By definition.

  10. jonathan keith
    Joke

    $3k prize?

    That might just about cover his electricity bill then.

    1. Timbo

      Re: $3k prize?

      "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 !!

      https://www.amazon.co.uk/Butterfly-Labs-ASIC-Bitcoiner-Miner/dp/B00I3U99RY

      1. Simon Brady

        Re: $3k prize?

        This raises an interesting question: what does BTC need to trade at before it's more profitable to spend your compute power hunting for primes? (Choosing an appropriate unit of compute to base the comparison on, e.g. general-purpose CPU/GPU throughput or FPGA gate count.)

  11. 89724102172714182892114I7551670349743096734346773478647892349863592355648544996312855148587659264921

    Don't gamble what you can't afford to lose - $3,000 is about two years of electricity

  12. JeffyPoooh Silver badge
    Pint

    There is a much more efficient algorithm to find primes (and factor very large composite numbers)...

    I have a truly marvelous demonstration of this proposition which this comment box is too narrow to contain.

    1. Ken Shabby
      Happy

      NURSE...

      Nurse, Mr Fermat is scribbling in his book again! Can we make sure it is the last time he does that?

  13. GBE

    When written out in full?

    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?

    1. diodesign (Written by Reg staff) Silver badge

      "when written out in full"

      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.

      C.

      1. GrumpenKraut Silver badge
        Pint

        Re: "when written out in full"

        > 82,589,933 is not the prime number, ...

        Actually, it is a prime number. Exponents of Mersenne primes need to be prime.

        Apologies for being a bit of a Klugscheisser. ----->

        1. emmanuel goldstein

          Re: "when written out in full"

          If you're going to be a pedant, at least grasp the point being made. He didn't say 82,589,933 wasn't a prime number, he said it wasn't the prime number (i.e. it is not the prime number we are actually interested in here).

          1. GrumpenKraut Silver badge

            Re: "when written out in full"

            OK, pendant fail on my side.

    2. YetAnotherLocksmith

      Re: When written out in full?

      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

  14. Gene Cash Silver badge

    Ocala

    Interesting. That's the podunk hellhole I was born & raised in. I'm surprised they can do math.

  15. John F***ing Stepp

    Downvote time

    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)

    1. John F***ing Stepp

      Re: Downvote time

      Oh scratch that. Damn calculater was wrong.

      One followed by 2239733 Fs in hex.

      (Goddamned smart phone

  16. skalamanga

    Sounds like Florida man finally got his shit together...

    10chars

    1. Francis Boyle Silver badge

      Don't worry

      He'll be back to doing drugs and trying to eat people's heads in a jiffy.

  17. John Brown (no body) Silver badge

    Oh crap!

    Now I have come up with ANOTHER new password.

    I'd have been ok if not for that meddling kid and his computer!

  18. harmjschoonhoven
    Alert

    Math is hard

    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.

    1. DavCrav Silver badge

      Re: Math is hard

      "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.

      1. harmjschoonhoven

        Re: Math is hard

        Computing the n-th Mersenne 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.

        1. MonkeyCee Silver badge

          Re: Math is hard

          "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.

      2. harmjschoonhoven

        @DavCrav Re: Math is hard

        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.

    2. MonkeyCee Silver badge

      Re: Math is hard

      "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

  19. ATeal

    Serious gripe

    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.

    ...Anyway.

    1. dovinki

      Re: Serious gripe

      You've broken the 'too many parenthesis' rule.

      Go to the end of the line.

  20. Cynic_999 Silver badge

    Pretty sure the answer's 42

    Isn't it?

  21. wayne 8

    "$3,000 GIMPS research discovery award cash prize"

    Should not that prize have increasing value as the difficulty increases?

    That is what makes Bitcoins so valuable, I hear.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Biting the hand that feeds IT © 1998–2019