Slashdot Mirror

← Back to Stories (view on slashdot.org)

Largest Prime Number Discovered – With More Than 23m Digits (mersenne.org)

Posted by msmash on from the breakthrough dept.

chalsall writes: Persistence pays off. Jonathan Pace, a GIMPS volunteer for over 14 years, discovered the 50th known Mersenne prime, 2^77,232,917 -- 1 on December 26, 2017. The prime number is calculated by multiplying together 77,232,917 twos, and then subtracting one. It weighs in at 23,249,425 digits, becoming the largest prime number known to mankind. It bests the previous record prime, also discovered by GIMPS, by 910,807 digits. You can read a little more in the press release.

64 of 117 comments (clear)

  1. I'll fine one right now by Anonymous Coward · · Score: 1, Insightful

    2^98,435,672 -- 1

    This is easy. Where's my fookin medal?

    1. Re:I'll fine one right now by Pseudonym · · Score: 2

      Exercise for the interested maths nerd: Prove that if q is any even number, then 2^q - 1 is divisible by 3.

      --
      sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
    2. Re:I'll fine one right now by Anonymous Coward · · Score: 1

      Fails if q = -2.

    3. Re:I'll fine one right now by Pseudonym · · Score: 1

      +1, appropriately pedantic

      --
      sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
    4. Re:I'll fine one right now by pezpunk · · Score: 1

      wow you were able to check that pretty fast. it took a Radeon Vega GPU over 34 hours to verify the number in the OP.

      --
      i could live a little longer in this prison
    5. Re:I'll fine one right now by RackinFrackin · · Score: 5, Interesting

      Not a rigorous proof, but here's my favorite explanation:

      for any positive integer k, the binary representation of 2^k-1 consists of k 1's. If k is even, this is an even number of 1's lined up together. Since 3 is 11 in binary, you can divide 2^k-1 by 3 and get a quotient of the form 10101..01.

      e.g. 2^10 = 1111111111=11(101010101)

    6. Re:I'll fine one right now by Pseudonym · · Score: 1

      Nice argument!

      That was clearly too easy. Show that 2^98,435,672 - 1 is divisible by 5.

      --
      sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
    7. Re:I'll fine one right now by FeelGood314 · · Score: 1

      2^98,435,672 - 1 is equal to (2^49217836 + 1)(2^49217836 - 1); it's a difference of squares.

    8. Re:I'll fine one right now by ClickOnThis · · Score: 2, Interesting

      Exercise for the interested maths nerd: Prove that if q is any even number, then 2^q - 1 is divisible by 3.

      Because q is even, we can write 2^q - 1 = [2^r -+1] * [2^r - 1], where 2r = q and r is a (positive) integer.

      Now consider the numbers 2^r - 1, 2^r, and 2^r + 1. One of these numbers must be divisible by 3. Clearly it is not 2^r because it only has factors that are powers of 2. Therefore either 2^r - 1 or 2^r + 1 must be divisible by 3. QED.

      --
      If it weren't for deadlines, nothing would be late.
    9. Re:I'll fine one right now by Pseudonym · · Score: 1

      Good stuff!

      --
      sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
    10. Re:I'll fine one right now by Pseudonym · · Score: 1

      Very good. To lay this out formally, you should say up front that you're using proof by truthiness.

      --
      sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
    11. Re:I'll fine one right now by Pseudonym · · Score: 1

      Note that the same argument can be used to show that 2^(4n)-1 is divisible by 15.

      In general, 2^(mn)-1 is divisible by 2^m - 1 (and without loss of generality 2^n - 1). It follows that if p is not prime, 2^p-1 isn't prime either. And that is how I instantly knew that 2^98,435,672-1 couldn't possibly be prime.

      --
      sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
    12. Re:I'll fine one right now by andrewbaldwin · · Score: 1

      As an extension... every prime greater than 3 is of the form 6n+1 or
      6n -1 (wish I knew how to get the plus or minus sign into Slash comments)

      6n is obviously not prime (divisible by 6)

      6n+2, 6n+4 are divisible by 2

      6n+3 is divisible by 3

      which just leaves 6n+1 and 6n+5

      6n+5 is equivalent to 6m-1 (where m=n+1)

      so 6n+1 6n-1 are necessary but not sufficient conditions but do provide a quick & dirty test for primality for small - medium sized numbers [divisibility by 2 is easily checked; divisibility by 3 is sum of digits mod 3 = 0]

    13. Re:I'll fine one right now by tehcyder · · Score: 1

      Nice argument!

      That was clearly too easy. Show that 2^98,435,672 - 1 is divisible by 5.

      It won't calculate on Excel, therefore its truth is unverifiable.

      --
      To have a right to do a thing is not at all the same as to be right in doing it
    14. Re:I'll fine one right now by cellocgw · · Score: 1

      2^98,435,672 - 1 is equal to (2^49217836 + 1)(2^49217836 - 1); it's a difference of squares.

      But we're discussing primes. what's 4^2 - 3^2 ?

      --
      https://app.box.com/WitthoftResume Code: https://github.com/cellocgw
    15. Re:I'll fine one right now by ClickOnThis · · Score: 1

      All primes p are odd, p+1 and p-1 are always even.

      Except for 2, which is prime and even.

      --
      If it weren't for deadlines, nothing would be late.
  2. If GIMPS Can Find Such a Huge Prime by Anonymous Coward · · Score: 5, Funny

    Just think how big a prime PHOTOSHOPS could find!

    1. Re:If GIMPS Can Find Such a Huge Prime by Anubis+IV · · Score: 5, Informative

      Serious reply in response to a decent joke: GIMPS is the Great Internet Mersenne Prime Search, which is more or less like SETI@home or Folding@home, but for Mersenne primes. I wasn't aware what it was, so I figured I'd share. Also, I had forgotten that Prime95, which is oftentimes used to stress cooling solutions in PCs, was actually created for use in finding large prime numbers, and was apparently developed by GIMPS.

  3. Headline Color? by Anonymous Coward · · Score: 1

    Neat, but, what's with the colour of the headline?

  4. Posted by FirehoseFavorites? by 93+Escort+Wagon · · Score: 1

    Is this an indication that we're going to be getting more placed content and less user-voted content?

    I'm not saying that's a good or bad thing - I'm just wondering what this is... or maybe it's already been around a while and I just am not observant.

    --
    #DeleteChrome
    1. Re:Posted by FirehoseFavorites? by 93+Escort+Wagon · · Score: 1

      Note that the story now has changed to say "Posted by msmash", and the banner color from dark blue to the familiar green. Perhaps someone jumped the gun..

      --
      #DeleteChrome
    2. Re:Posted by FirehoseFavorites? by whipslash · · Score: 4, Informative

      FirehoseFavorites is purely user voted content. Something new we are testing. Requires zero editor input to make it to the front page, just user votes from the firehose.

    3. Re:Posted by FirehoseFavorites? by 93+Escort+Wagon · · Score: 2

      FirehoseFavorites is purely user voted content. Something new we are testing. Requires zero editor input to make it to the front page, just user votes from the firehose.

      Ah, that makes sense - thank you for the explanation.

      --
      #DeleteChrome
    4. Re:Posted by FirehoseFavorites? by Anonymous Coward · · Score: 2, Insightful

      Unleash the bots!

    5. Re:Posted by FirehoseFavorites? by whipslash · · Score: 1

      Improving is the aim. This is just something we are testing out to see how it works.

    6. Re:Posted by FirehoseFavorites? by PhunkySchtuff · · Score: 1

      Wouldn't more editor input be the way to improve /. or is improving it not the aim?

      You must be new round here ^_^

      --
      Specialist Mac support for creative pros, Melbourne
    7. Re:Posted by FirehoseFavorites? by tehcyder · · Score: 1

      Wouldn't more editor input be the way to improve /. or is improving it not the aim?

      I think that depends on your opinion of the editors.

      --
      To have a right to do a thing is not at all the same as to be right in doing it
  5. Re:Application by kaoshin · · Score: 4, Informative
    From TFA:

    "At present there are few practical uses for this new large prime, prompting some to ask "why search for these large primes"? Those same doubts existed a few decades ago until important cryptography algorithms were developed based on prime numbers. For seven more good reasons to search for large prime numbers, see here.

  6. Re:Application by semper_statisticum · · Score: 3, Informative

    The more prime numbers that are discovered, the more likely we are to be able to discover a pattern within an arbitrary base number set. The larger numbers are useful because we also want to make sure that the entire range is consistent, or in other words that any pattern, or lack of pattern, is the same across the entire set of numbers. There is always a benefit to trying to find patterns in number theory -- it's one of the coolest and most interesting fields in pure mathematics.

    --
    The Spanish Inquisition of Psychometrics; Burning all the heretics.
  7. Headline writer is a boob by FatRatBastard · · Score: 3, Insightful

    Subject says it all.

    1. Re:Headline writer is a boob by JoshuaZ · · Score: 1

      Yes, they obviously mean largest known prime, not the largest prime there is. Headlines need to be short and frequently need to rely on some minimal context. Yes, the headline is hardly a "Headless body found in topless bar" quality but it was pretty clear from the context what was meant.

    2. Re:Headline writer is a boob by FatRatBastard · · Score: 1

      So 6 extra characters (known_) is apparently a bridge too far? Its not that the posted headline can be interpreted in different ways; it is outright wrong.

    3. Re:Headline writer is a boob by Pseudonym · · Score: 1

      The phrase "largest prime number discovered" refers to the largest prime that has been discovered. I know English is a hard language, but it's not that hard.

      Having said that, pity the Slashdotter who needs "raising a number to the power of two" explained to them.

      --
      sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
    4. Re:Headline writer is a boob by Jeremi · · Score: 1

      The phrase "largest prime number discovered" refers to the largest prime that has been discovered. I know English is a hard language, but it's not that hard.

      The problem is that the phrase is ambiguous.

      It could mean:

            The (largest prime number) has been discovered. -- i.e. there is a largest prime number and we just found it.

      or it could mean:

            The largest prime number [that we have so far] discovered [is two-to-the-whatever-minus-one].

      Presumably the headline writer mean to communicate the latter, but ended up mostly communicating the former. It's true that people familiar with the properties of prime number can probably infer what the headline writer intended, but a good headline avoids ambiguity (unless it's clickbait, in which case ambiguity is considered desirable).

      --


      I don't care if it's 90,000 hectares. That lake was not my doing.
  8. Re:Application by rogoshen1 · · Score: 2

    think of all the dogecoin they could have mined!

  9. Re:Application by JoshuaZ · · Score: 2, Informative

    Primarily for the fun of it. There are some specific uses of large Mersenne primes in the Mersenne twister algorithm for generating pseudorandom numbers https://en.wikipedia.org/wiki/Mersenne_Twister, but in practice much, much smaller Mersenne primes are perfectly fine for that use, and indeed are much more practical. There are people who whenever you talk about large primes will claim they are useful for crypto, but that's not generally the case. The primes are too big for practical Diffie-Hellman (and there are specific reasons one might want to avoid using them for that), and they are not random primes in any sense so using them for any form of RSA would be really silly. That said, there's at least one mildly fun cryptographic algorithm whose proof of correctness relies on there being infinitely many Mersenne primes http://www.di.ens.fr/~vergnaud/algo0910/Locally.pdf, but no one has to my knowledge actually tried to implement the algorithm in that paper.

  10. Off by two by sacrilicious · · Score: 1

    discovered the 50th known Mersenne prime, 2^77,232,917 -- 1 on December 26, 2017.

    I've done the math and 2^77,232,917 -- 1 is not prime. Although decrementing it by 2 to get 2^77,232,917 - 1 is indeed a prime.

    --
    - First they ignore you, then they laugh at you, then ???, then profit.
    1. Re:Off by two by sacrilicious · · Score: 1

      Please write down all numbers from 0 to your prime for proof.

      I've done what you suggested, but the result was slightly too large to include in the margins of this web page.

      --
      - First they ignore you, then they laugh at you, then ???, then profit.
  11. Re:Application by guruevi · · Score: 1

    It's interesting for pure mathematics people. There are some minor applications for this although it's mostly theoretical.

    Once we get bigger computers that can hold these numbers, they may be used to prime a PRNG or a cryptographic constant, especially once quantum computing starts threatening the constants in the lower ranges. Quantum computers can't break cryptography, they just do it faster and for larger primes you still need more q-bits.

    Highly theoretical there may be some constant to the prime numbers. If there is some rhyme or reason to prime numbers, we may be able to predict where the next one may be or how to derive its factors. This is one of the holy grails of mathematics and could also impact cryptography.

    --
    Custom electronics and digital signage for your business: www.evcircuits.com
  12. Thats by JustOK · · Score: 5, Funny

    That's amazing! I've got the same combination on my luggage!

    --
    rewriting history since 2109
    1. Re:Thats by dohzer · · Score: 1

      Never mind, the TSA staff have cut your lock off. They're going through your underwear as we speak.

    2. Re:Thats by JustOK · · Score: 1

      I've saved alot of money since I've realized the TSA would do stuff like that for free.

      --
      rewriting history since 2109
  13. Re:Application by Pseudonym · · Score: 1

    I have to wonder if looking for just Mersenne primes will reveal anything interesting about the primes in general. It seems unlikely to me.

    Having said that, finding a pattern in the Mersenne exponents would be very interesting indeed.

    --
    sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
  14. Found a bigger one by russotto · · Score: 1

    2^77,232,917 + 1

    1. Re:Found a bigger one by pjt33 · · Score: 1

      Number Theory 101 exercise: why is 3 the only Mersenne number to be the smaller half of a prime pair?

    2. Re:Found a bigger one by Anonymous Coward · · Score: 1

      That IS divisible by 3. (M=2^p-1 isn’t, M+1=2^p isn’t, so M+2 is.)

    3. Re:Found a bigger one by wonkey_monkey · · Score: 1

      That's not how prime numbers work.

      --
      systemd is Roko's Basilisk.
    4. Re:Found a bigger one by Opyros · · Score: 1

      For those who don't know the answer: two raised to any odd power then added to one is always divisible by three.

    5. Re:Found a bigger one by pjt33 · · Score: 1

      There's a simpler pigeonhole answer: one of (2^n - 1), 2^n, (2^n + 1) is divisible by 3. Clearly it's not 2^n. Therefore if (2^n - 1) is a prime other than 3, (2^n + 1) is the one which is divisible by 3.

  15. Re:Application by Hal_Porter · · Score: 1

    An entity which could encode a message in the distribution of Mersenne exponents would be very powerful indeed. It'd be even harder than encoding a message into physical constants which a hyper advanced civilisation may be able to do by creating new universes inside black holes.

    --
    echo -e 'global _start\n _start:\n mov eax, 2\n int 80h\n jmp _start' > a.asm; nasm a.asm -f elf; ld a.o -o a;
  16. Re:Finally by dohzer · · Score: 1

    Standard? This is my Bitcoin wallet key. I'm ruined!

  17. Fireho5hin by tepples · · Score: 1

    Is this the second coming of Kuro5hin?

  18. Might be a provable prime, but... by EvilSuggestions · · Score: 1

    Now for the important questions: Is it executable? And is it illegal?
    http://fatphil.org/maths/illeg...

    --
    "There is a thin line between ignorance and arrogance, and only I have managed to erase that line." - Dr. Science
  19. Re:Application by thePsychologist · · Score: 3, Interesting

    To clarify, these types of primes aren't useful for cryptography as they are much too large and not 'typical' primes.

    From a theoretical perspective they are quite interesting: they are in bijective correspondence with perfect numbers and no one knows whether there are infinitely many. For all we know, this one could theoretically be the last.

    --
    "What lies behind us, and what lies before us are tiny matters compared to what lies within us." Ralph Waldo Emerson
  20. Re:Application by burhop · · Score: 4, Interesting

    For all we know, this one could theoretically be the last.

    OK people, we're done here! We found the last prime! Time to shut it down! You don't have to go home, but you can't stay here!

    OK, that was a joke but we can still be clear. He was talking about the last perfect number. There is an infinite number of primes. That proof is pretty simple.

    1. Assume there is a limited number of primes. Given the list of all the prime numbers
    2. Multiply them all together and add 1.

    The new number you get is can not divisible by any of the prime numbers in your list (e.g. if you divide the number by 2, you have a reminder of 1, if you divide the number by 3, you have a remainder of 1, if you divide the number by 5, you have a remainder of 1...)

    So there must be at least one number not on your list which invalidates the given statement.

  21. Re:Finally by slashrio · · Score: 1

    No. You're still protected by obscurity. Now quick, transfer your bitcoins to another address.

    --
    "Trump!!", the new Godwin.
  22. Re:Application by ezdiy · · Score: 2

    IMO, the main practical advantage is that checking for MP is fast, so they're easier to search for. Working with MP number fields is fast too (owing to close-to-pow2 property). so they find use whenever any large prime would do, it's just a nice to have MP in there.

    A typical practical usage is PRNGs of girgantual periods (the period is typically the MP itself, or multiple of thereof) for HPC number crunching. The perfect number property indeed is a nice bonus in there, as it often leads to better k-distribution of the permutation.

    http://maths-people.anu.edu.au...

  23. Primes with prime ordinals by mysticgoat · · Score: 1

    One is prime, and it is the first prime, which is also prime.

    Two is prime, and its ordinal is 2, which is prime.

    3 is prime, its ordinal is 3, also prime

    5 is prime, its ordinal is 4, which is not prime

    7 is prime, its ordinal is 5, which is prime

    11 is prime, its ordinal is 6, not prime

    etc

    So is there a rule that would answer whether any given prime's ordinal in the list of primes is also prime?

    Extra points for a calculator trick to answer this.

    Super extra bonus points: is there a largest prime number whose ordinal is also prime?

    1. Re:Primes with prime ordinals by david_thornley · · Score: 1

      Also, every number has a unique prime factorization. Consider 1 prime and you get the prime factorizations of 10 being 2*5, 1*2*5, 1*1*2*5, etc. Also, if 1 is prime, then 1 = 1 * 1, so 1 is the multiple of two primes. It's much easier to consider 1 neither prime nor composite, just the multiplicative identity.

      --
      "When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
    2. Re:Primes with prime ordinals by mysticgoat · · Score: 1

      The Sieve of Eratosthenes is perhaps the oldest method of identifying prime numbers, BUT it is not the definition of a prime number. It is an algorithm ---not a definition--- that was not developed until a long time after the Greeks (and probably other ancient peoples) had identified the nature of prime numbers.

      The definition of a prime number is any number that is only divisible by itself and by one. Do not mistake an early algorithm for identifying prime numbers with the definition of prime. For one thing, if you believe your definition is correct, then you are strongly implying that any number of professional mathematicians over more than 2,000 years who have sought other algorithms know less about their profession than you do. That is absurd.

      I repeat the problem:

      One is prime, and it is the first prime, which is also prime.

      Two is prime, and its ordinal is 2, which is prime.

      3 is prime, its ordinal is 3, also prime

      5 is prime, its ordinal is 4, which is not prime

      7 is prime, its ordinal is 5, which is prime

      11 is prime, its ordinal is 6, not prime

      etc

      So is there a rule that would answer whether any given prime's ordinal in the list of primes is also prime? Extra points for a calculator trick to answer this. Super extra bonus points: is there a largest prime number whose ordinal is also prime?

      Note that even for those who erroneously believe that one is somehow special with regard to primeness, the problem is there: is there a rule that can be applied to any given prime number to determine if its ordinal value in a listing of primes was also a prime number?

    3. Re:Primes with prime ordinals by david_thornley · · Score: 1

      I studied mathematics for some time. I know what I'm talking about. Under your definition, one of the fundamental theorems of arithmetic (that each number has a unique prime factorization) is false. This has nothing to do with the Sieve, which as you point out is an algorithm. It has to do with making useful mathematical definitions.

      Mathematics doesn't depend on the physical world. It's a collection of deductions from axioms and definitions, and we tailor the axioms and definitions to be useful. Defining 1 to be prime screws things up, so 1 is not prime. This is the standard definition, and has been for a long, long time. If you were to check with any of the mathematicians you wave at, that's what you'd be told.

      There is no largest prime number, and primes are a subset of integers. Therefore, we can have a one-to-one correspondence with primes and the integers 1 and greater, giving the ordinal. Given a prime number, therefore, there's a prime that's the ordinal for. Since there is no largest prime number, there's no largest prime whose ordinal is also prime.

      You can check whether numbers are prime, and therefore you can check whether any particular ordinal is prime. There's no quick way to do so as far as I know (primality testing isn't even known to be in NP).

      --
      "When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
    4. Re:Primes with prime ordinals by mysticgoat · · Score: 1

      A prime number (or prime integer, often simply called a "prime" for short) is a positive integer p>1 that has no positive integer divisors other than 1 and p itself. More concisely, a prime number p is a positive integer having exactly one positive divisor other than 1, meaning it is a number that cannot be factored. [see Wolfram MathWorld]

      Note that when p is set to 1, the test is also true: its only positive integer divisors are itself, p, and 1. (1/1=1 which is both 1 and the current value of p). Wolfram simply ignores this edge case, since for all but esoteric levels of advanced mathematics it is not necessary to go there.

      From a historical perspective this makes sense. When at the end of the day's harvest it was time to evenly divide up the bags of grain that had been gathered in, it turned out that it was always the case that if there were certain numbers of bags, there was no way to evenly divide them, no matter how many persons were to receive a portion. Finding a way to fairly dispose of prime numbers of objects was one of the earliest problems in social engineering.

      Similarly, the problem of zero is generally ignored except in the rarefied heights where mathematics no longer has value in engineering, finances, and any other applied mathematics that I am aware of. I am of course referring to the fact that division by zero is undefined. In this manner zero does not qualify as a rational number, and since the integers are a subset of rational numbers, zero is not an integer. Nor is it a counting number. At best, zero is an irrational real number, like pi, the sqrt(2), e, etc. But it might actually be better to define it as a hole in the number line ---that's something for the Wolframs out there to noodle over.

      Circling back to the original problem, you said:

      There is no largest prime number, and primes are a subset of integers. Therefore, we can have a one-to-one correspondence with primes and the integers 1 and greater, giving the ordinal. Given a prime number, therefore, there's a prime that's the ordinal for. Since there is no largest prime number, there's no largest prime whose ordinal is also prime. There is no largest prime number, and primes are a subset of integers. Therefore, we can have a one-to-one correspondence with primes and the integers 1 and greater, giving the ordinal. Given a prime number, therefore, there's a prime that's the ordinal for. Since there is no largest prime number, there's no largest prime whose ordinal is also prime.

      This seems to be tightly reasoned. I think it would have been better to say that "primes are a subset of the counting numbers" rather than integers, but that's a mere quibble. Of course you could also call the set of primes a subset of the rational numbers, or the real numbers ---whatever.

      However as this thread has been having problems with word usage intended to dazzle with brilliance or possibly baffle with ... . well, I can't immediately accept it what you propose, and I've got other things to think about than puzzling over something that may not have been intended to be meaningful. I will read it over a time or two and let my subconscious play with it. But I also ask whether you can rephrase whatever you may be saying in a more mathematically formal statement.

  24. Re:CPU by ConceptJunkie · · Score: 1

    Did they check it on Intel or AMD CPU?

    Both.

    https://www.mersenne.org/prime...

    The results were checked with several different pieces of software on multiple platforms.

    --
    You are in a maze of twisty little passages, all alike.
  25. Here's part of it... by ConceptJunkie · · Score: 1

    I evaluated the full number using the mpmath Python library. It starts with:

    46733318335923109998833558556111...

    and ends with: ...1136582730618069762179071

    It took over an hour, but there are likely better ways to do it than I did, even with mpmath.

    --
    You are in a maze of twisty little passages, all alike.