Forgot your password?
typodupeerror
Education Science

42nd Mersenne Prime Probably Discovered 369

Posted by Zonk
from the so-many-digits dept.
RTKfan writes "Chalk up another achievement for distributed computing! MathWorld is reporting that the 42nd, and now-largest, Mersenne Prime has probably been discovered. The number in question is currently being double-checked by George Woltman, organizer of GIMPS (the Great Internet Mersenne Prime Search). If this pans out, GIMPS will have been responsible for the eight current largest Mersenne Primes ever discovered."
This discussion has been archived. No new comments can be posted.

42nd Mersenne Prime Probably Discovered

Comments Filter:
  • Uses? (Score:3, Interesting)

    by UncleJam (786330) on Friday February 18, 2005 @05:22PM (#11716881)
    What uses are there for gignatic prime numbers like this other than showing off computing power?
    Encrypting?
    • Re:Uses? (Score:5, Funny)

      by selectspec (74651) on Friday February 18, 2005 @05:25PM (#11716920)
      Chics dig it.
    • Re:Uses? (Score:5, Funny)

      by Husgaard (858362) on Friday February 18, 2005 @05:27PM (#11716946)
      I don't the any real use for this except finding large primes.

      The theory is that there is an infinite number of these numbers, but they are unlikely to prove the theory by finding them all...

      • Now that I've got that working quantum computer I've proven the theory so it's now a fact...

        There are an infinite number of numbers hence an infinite number of infinite primes from that set of infinite numbers.

        The nice thing was that it only took a billionth of second to figure it all out.
        • Re:Uses? (Score:3, Insightful)

          by uberdave (526529)
          The X axis is infinite. So are the Y and Z axes. Therefore, there must be an infinite number of regular solids. Oh, wait! There's only five. Gee, I guess the mere fact that numbers are infinite doesn't imply that subsets of those numbers are infinite.
          • "OK, I've narrowed the range down to between zero and infinity. The rest is up to you..."
          • Re:Uses? (Score:4, Informative)

            by Seculus (788503) on Friday February 18, 2005 @09:02PM (#11719014)
            That's not actually the argument for why the number of primes is infinite. Rather, assume there are only finitely many prime numbers. Multiply all of them together. Add one to this number. It is easy to show that this number is not divisible by any of the finitely many primes you started with. Hence it must be a prime number as well.
            • Re:Uses? (Score:3, Insightful)

              by Anonymous Coward
              Actually, it doesn't have to be. It only suffices so say, that when you multiply all primes in your list, and add one, you get a number not divisable by any of the number in the list. Hence, one of TWO things can hold true:

              1) The number in question really is prime, as you suggested

              2) The number in question isn't prime. Then it has prime divisors, none of them in your list (because none of the primes in the list divided our new number).

              In both cases, we have derived a way to find at least one new prime fr
    • Re:Uses? (Score:4, Informative)

      by Jeremy Erwin (2054) on Friday February 18, 2005 @05:37PM (#11717063) Journal
      Testing distributed primality algorithms. I should have thought this was obvious.

      And, no, one does not encrypt with Mersenne primes. The rarity of such numbers makes a "brute force" crypto-analysis seem rather plausible. Best to use an ordinary prime number-- there are, after all, many more of them to choose from.
      • No, encryption is out of the question, since it would take enormous computing power to get a new key (see GIMPS). As for the known keys, these are obviously not available for use. A brute force attack would take 21 rounds to complete (on average).

        Using a mersenne prime for the public exponent is no problem though. Both 3 and 7 are used quite a lot for this purpose, though 65537 is used most (and this is not a mersenne prime).
    • Why this got marked troll is beyond me. Us non-mathmaticians are curious about what significance there is for categories of numbers that mathmaticians get excited about.

      If an expert gets excited, there's usually a reason. It's reasonable for non experts to ask what that reason is.

      TW
      • Re:GOOD QUESTION! (Score:4, Informative)

        by Surt (22457) on Friday February 18, 2005 @06:26PM (#11717598) Homepage Journal
        It's one step closer to proving there's an infinite sequence of these numbers. Just infinity - 42 more to go and the proof is complete!

        In all seriousness, they are interesting mainly because they are so simple mathematically that very very early mathematicians got interested in them. But even after hundreds of years of interest among mathematicians, there's no formula for predicting them, and very little successfully proven about them.

        Since they are so rare, each find is a significant advancement for those who might be interested in trying to find a pattern.
        • Re:GOOD QUESTION! (Score:3, Informative)

          by Artifakt (700173)
          What use are they?
          There may or may not be patterns in the way Merseinne primes occur.
          If there are any patterns in Merseinnes, we may need to find more examples than we had before we can find those patterns.
          If we do find patterns, they may or may not help us find other patterns that apply to other types of large primes in more general ways.
          There is no guarenteed use outside of abstract math, but there is at least a small possibility we could crack one of the really big problems in crypto
    • Re:Uses? (Score:3, Informative)

      by rbrito (37104)
      One of the most obvious uses for having tasks like this is to understand better the problems and to develop better algorithms.

      In Computational Complexity's terms, we like to design "efficient" algorithms.

      One of the criteria used to say if an algorithm is efficient or not is to measure the time it takes to execute in terms of the size of its input.

      We are usually concerned with designing faster algorithms (especially when we have to deal with huge inputs --- that's one of the things that people have in min
  • by rackhamh (217889) on Friday February 18, 2005 @05:22PM (#11716887)
    ... the moment they discovered the 42nd prime, the world was immediately destroyed to make way for an intergalactic superhighway.
  • Sheesh (Score:2, Funny)

    by Anonymous Coward
    The number in question is currently being double-checked by George Woltman, organizer of GIMPS

    And while George takes time off to double-check Mersenne primes, GIMP doesn't get any closer to the usability of Photoshop...
  • by NitroWolf (72977) on Friday February 18, 2005 @05:27PM (#11716937)
    Can someone explain what the application/use these primes are for? Not a flame, I'm honestly curious as to what something like this could be used for, as are others, I'm sure.

    • Large primes, of around 75-100 digits, are useful in encryption. Huge primes (i.e. over 7 million digits) are not currently useful in themselves, although we certainly learn more about mathemathics and computers as we try to find them.
    • by robbyjo (315601) on Friday February 18, 2005 @05:42PM (#11717106) Homepage

      From here [haugk.co.uk]:

      Finding new Mersenne primes is not likely to be of any immediate practical value. This search is primarily a recreational pursuit. However, the search for Mersenne primes has proved useful in development of new algorithms, testing computer hardware, and interesting young students in math.

    • by vivin (671928) <<vivin.paliath> <at> <gmail.com>> on Friday February 18, 2005 @05:42PM (#11717109) Homepage Journal
      It's a mathematical curiosity in some cases - just to find it for the sake of finding it, or for the glory of finding it. You know, like being the first to do something cool.

      Also, necessity is the mother of invention. Even if Big Primes aren't really a necessity, it has brought forth some really innovative algorithms and methods to finding prime numbers. Furthermore, it has developed newer and faster ways for multiplying integers.

      In 1968, Strassen figured out how to multiply integers quickly by using Fast Fourier Transforms. Strassen, along with Schönhage improved on the method and published a refined version in 1971. GIMPS now uses an improved version of their algorithm. This improved version was developed by Richard Crandall (a longtime researcher of Mersenne Primes).

      Another application of finding Prime Numbers is to test computer hardware. Since testing Primes involves a thorough excercise of basic mathematical operations, it provides a good test for hardware. Software routines from GIMPS were used by Intel to test the PII and the Pentium Pro chips before they were shipped. The search for prime numbers was also indirectly responsible for the discovery of the infamous FDIV bug on the Pentium, during the calculation of the twin prime constant (by Thomas Nicely).

    • Uncommon and unique numbers of varying types are usually useful for mathematics in general. Usually only mathematicians know why.

      Whatever the case, this must be a more useful application for CPU power than Seti@home, which is a total waste of energy. Literally.

      What we need are more projects that use distributed computing for useful calculations that could further science or solve problems. Universities build giant supercomputers to help their students calculate equations and solve problems. Maybe th
    • by pclminion (145572) on Friday February 18, 2005 @05:49PM (#11717192)
      Can someone explain what the application/use these primes are for?

      Communicating with alien species, perhaps.

      Mersenne primes have two interesting properties that might catch the attention of alien species: when written in binary, they are entirely composed of '1' bits; and, of course, they are prime.

      A sure way to prove to another being that you are intelligent is to spew a bunch of numbers which all happen to be prime. The fact that they can be tranmitted using only '1' bits means the modulation is simple -- just send a series of pulses.

      • by geoffspear (692508) * on Friday February 18, 2005 @05:58PM (#11717287) Homepage
        Transmitting the same binary signal over and over seems unlikely to impress anyone. You're as likely to be sending a really boring all-white image as a really big prime number.

        If anything, anyone receiving the signal will wonder how you managed to build such a powerful transmitter when you haven't discovered binary numbers yet and are apparently using some sort of unary mathematics that really shouldn't work. They're bound to be disappointed when they find out you actually know about "0", but just weren't using it.

        • No, you have to transmit MULTIPLE numbers. You transmit the first Mersenne prime. Then you wait for a while. Then you transmit the next one. Wait again. Etc. It's much more efficient to send them in binary than unary (although this most recent prime would require over 2 million bits).

          And just because aliens receive a signal with a bunch of strong, equally spaced pulses doesn't mean they'll automatically assume it's intelligent. There are plenty of natural cosmic phenomena which produce equally spaced pul

          • If it's all 1's (I'll trust you on this, since I haven't RTFA), then it might make sense to transmit the first 42 Mersenne primes by transmitting the number of digits in them instead of transmitting their binary representation. Now, instead of transmitting 2 million 1's, we can transmit 21 0's and 1's. Of course, this gets back to them understanding what we're transmitting. (I think it would take a lot of patience for them to interpret 2 million (give or take) 1's as being a Mersenne prime. And what happens
  • by vivin (671928) <<vivin.paliath> <at> <gmail.com>> on Friday February 18, 2005 @05:28PM (#11716959) Homepage Journal
    A mersenne Prime is a prime number that is one less than the power of two. Hence:

    Mn = 2^n - 1.

    Mersenne primes have a connection with Perfect Numbers (numbers that are equal to the sum of their proper divisors) where by if M is a Mersenne prime, then M(M+1)/2 is a perfect number.
    • You forgot the wikipedia link [wikipedia.org] though if it's true then the Wikipedia article is now out of date.
    • by tbjw (760188) on Friday February 18, 2005 @06:08PM (#11717409)

      You can say even more. If M can be written as 2^n - 1, then M is said to be a Mersenne number. If M is also prime, then it is a Mersenne prime. For 2^n - 1 to be a Mersenne prime, n must be a prime number, since we have

      2^(ab) - 1 = (2^a-1)(2^(a(b-1)) + 2^(a(b-2)) + ... + 2^(a))

      For instance, 2^6-1 is (in binary) 111111 = 1001 * 111, as predicted by the above factorisation.

      If p is a prime number and if 2^p-1 is a Mersenn prime, then, as was pointed out above, 2^(p-1)(2^p-1), is a perfect number. Moreover, if N is an even perfect number, then N can be written (uniquely) as 2^(p-1)(2^p-1) where p is a prime number and 2^p-1 is a Mersenne prime.

      Wikipedia [wikipedia.org] has a reasonably intelligible introduction to perfect numbers, and MathWorld [wolfram.com] contains a proof of why every even perfect number must have the form claimed above.

      To see why M = 2^(p-1)(2^p-1) is a perfect number when p, 2^p-1 are primes, it suffices to note that s(n), the function that maps an integer to the sum of its divisors (e.g. s(6) = 1 + 2 + 3+6, s(8) = 1 + 2 + 4+8) is multiplicative in the number-theoretic sense, that is to say s(ab) = s(a)s(b) whenever a, b have no prime factors in common. Then evaluating s(M) is simply a case of evaluating it on the factors, which are relatively prime since one is a power of 2, 2^(p-1), and the other is an odd prime, 2^p-1. s(2^p-1) = 2^p-1 + 1 = 2^p (since we have a prime number), and 2^(p-1) = 2^p -1 is an easy formula that is true of all powers of 2. Hence s(M) = 2^p(2^p-1) = 2 ( 2^(p-1) (2^p-1) = 2s(M). That is to say, the sum of all the divisors of M add up to twice M, and if we leave the divisor M itself out of the sum, we see that M is a perfect number.

  • by Guano_Jim (157555) on Friday February 18, 2005 @05:30PM (#11716980)
    Call me when a distributed computing project finds Fruit Fucker Prime. [penny-arcade.com]
  • A Mersenne Prime is where the prime number also fulfills the equation 2^P - 1 2^2 - 1 = 3 ... 3 is a mersenne prime. 2^3 - 1 = 5 ... 5 is a mersenne prime. 2^4 - 1 = 7 ... 7 is a mersenne prime. The next one is 31 and after that 127. From there they get quite rare (only 42 known). They are VERY useful in cryptography and quantum physics...both deal with huge numbers. They are also used in some SETI applications because if you wanted to send primes, you'd probably send mersennes as these would be *very*
  • by serutan (259622) <snoopdougNO@SPAMgeekazon.com> on Friday February 18, 2005 @05:31PM (#11716985) Homepage
    Reminds me of the first BlackAdder episode

    Lord Percy: "The King is dead! L-"
    Prince Harry [interrupting]: "Probably dead."
    Lord Percy: "The King is probably dead!"
  • by Anonymous Coward on Friday February 18, 2005 @05:31PM (#11716995)
    Don't read any farther if you don't like spoilers.






    Seriously, don't reead any farther....






    It only has two factors.
  • Now that we've found the 42nd Mersenne Prime, we can cure cancer, cure AIDs, solve all NP problems in deterministic polynomial time, travel faster than light, and solve world hunger.

    Thank you Great Internet Mersenne Prime Search!
  • by William_Lee (834197) on Friday February 18, 2005 @05:35PM (#11717036)
    I'm not sure what else they're actually good for, but searching for these with Prime95 is a great way of putting the flame to your CPU.

    Prime95 (which searches for these primes) really puts a load on the CPU and raises the temperature in a hurry. It's commonly used to test the stability of overclocking configurations since it stresses the chip and is able to detect if there is an error in the computation.

    Generally, if you can run Prime95 for 24 hours straight, most people will consider the overclocked PC a stable configuration.
  • Yes! (Score:5, Funny)

    by Anonymous Coward on Friday February 18, 2005 @05:37PM (#11717054)

    If this pans out, GIMPS will have been responsible for the eight current largest Mersenne Primes ever discovered.

    In your face, Photoshop!

  • Two unknowns (Score:5, Informative)

    by MaGogue (859961) on Friday February 18, 2005 @05:39PM (#11717076)

    This has not yet been confirmed, therefore there could be less than 42 known Mersenne primes.

    Hovewer, according to MathWorld, there is a chance that it is not the 42nd Mersenne prime at all for another reason :

    "However, note that the region between the 39th and 40th known Mersenne primes has not been completely searched, so it is not known if M20,996,011 is actually the 40th Mersenne prime.."
    Looks like the big math guys don't exactly know how to count at all ;)
  • by Anonymous Coward on Friday February 18, 2005 @05:39PM (#11717077)
    Back in the dark ages when I was in university, I took a class called "Mathematics and Poetry". I thought it would be a useful bird course in my senior year, but it turned out to be both interesting and challenging.

    As part of the course, we studied Mersenne primes. At the time, I was dabbling in x86 assembler, and I decided to write a program to calculate the then largest known Mersenne prime number: 2^31 - 1, which worked out to 65,050 digits.

    The size worked out perfectly, as in 1989 that meant it could fit into one 65KB segment on my blazing-fast 8Mhz 8088. As I recall, the runtime was about two days. The program still works--I can't remember how long it took to run on a 3Ghz P4, but I think it was just a few minutes.

    I'm sure any competent programmer (read--not me) could calculate the result much faster, but at the time I was very proud of my little creation.
  • ...now that weve got this important prime number thing handled..lets get back to folding protiens...

    im a geek...but damn...thats uber-geekish
  • by pmike_bauer (763028) on Friday February 18, 2005 @05:42PM (#11717105)
    The number in question is currently being double-checked by George Woltman

    Ok...lets see here...

    5465875133124687545551258898456556......98034802

    BUMMER!

  • ...waste of time, money and processing power. what kind of use would this have, other than just knowing it? its like winning a eating contest: a completely useless achievement, plus it just turns to poop.
  • OMG! Do you know what this means!?!?!

    .

    .

    No really, please tell me. I haven't a clue...
  • by thesatch (844290) on Friday February 18, 2005 @05:47PM (#11717174)
    http://www.eff.org/awards/coop.html [eff.org]

    Thought it takes my 1.7Ghz 3 months to test a 10mil digit prime.
  • by Anonymous Coward

    These guys should sue each other for trademark infringement.

    With any luck they'd both be forced to change their name to something sensible.

  • So how long would it take this guy [surfeu.fi] to crap out the number they found?
  • While this is a great academic achievement . . .

    Damn it! I have to change my luggage combination again. Darn you, George Woltman!

  • C'mon man, I found the 42nd Mersenne Prime 2 years ago with a pocket calculator. Once you know the trick, it's easy.
  • On a related note (Score:4, Informative)

    by OverlordQ (264228) on Friday February 18, 2005 @06:12PM (#11717443) Journal
    Seventeen or Bust [seventeenorbust.com] (a distributed attack on the Sirpinski Problem), found the fourth largest (well fifth if this one pans out) prime at the beginning of this year, which contains 2,357,207 digits.
    28433 * 2^7830457 + 1
    List of all of the largest primes can be found here [utm.edu]
  • The number in question is currently being double-checked by George Woltman, organizer of GIMPS

    Somehow, I don't think that the world will be threatened by George Woltman and his organized gimps.
  • by utexaspunk (527541) on Friday February 18, 2005 @06:42PM (#11717747)
    72,881,090,798,676,481,947,445,843,876,689,972,113 ,188,382,077,838,576,766,415,271,554,183,554,023,6 81,926,442,357,773,229,141,527,132,801,050,545,169 ,980,023,429,475,382,981,277,026,411,446,450,732,1 20,206,920,761,648,530,323,773,463,358,502,551,340 ,699,145,522,328,264,108,074,466,176,204,798,818,5 91,643,822,008,785,083,299,073,103,153,980,722,122 ,415,403,264,180,661,744,484,810,522,551,289,556,1 61,305,278,379,785,516,809,393,766,311,656,230,448 ,542,351,852,881,090,798,676,481,947,445,843,876,6 89,972,113,188,382,077,838,576,766,415,271,554,183 ,554,023,681,926,442,357,773,229,141,527,132,801,0 50,545,169,980,023,429,475,382,981,277,026,411,446 ,450,732,120,206,920,761,648,530,323,773,463,358,5 02,551,340,699,145,522,328,264,108,074,466,176,204 ,798,818,591,643,822,008,785,083,299,073,103,153,9 80,722,122,415,403,264,180,661,744,484,810,522,551 ,289,556,161,305,278,379,785,516,809,393,766,311,6 56,230,448,542,351,852,881,090,798,676,481,947,445 ,843,876,689,972,113,188,382,077,838,576,766,415,2 71,554,183,554,023,681,926,442,357,773,229,141,527 ,132,801,050,545,169,980,023,429,475,382,981,277,0 26,411,446,450,732,120,206,920,761,648,530,323,773 ,463,358,502,551,340,699,145,522,328,264,108,074,4 66,176,204,798,818,591,643,822,008,785,083,299,073 ,103,153,980,722,122,415,403,264,180,661,744,484,8 10,522,551,289,556,161,305,278,379,785,516,809,393 ,766,311,656,230,448,542,351,852,881,090,798,676,4 81,947,445,843,876,689,972,113,188,382,077,838,576 ,766,415,271,554,183,554,023,681,926,442,357,773,2 29,141,527,132,801,050,545,169,980,023,429,475,382 ,981,277,026,411,446,450,732,120,206,920,761,648,5 30,323,773,463,358,502,551,340,699,145,522,328,264 ,108,074,466,176,204,798,818,591,643,822,008,785,0 83,299,073,103,153,980,722,122,415,403,264,180,661 ,744,484,810,522,551,289,556,161,305,278,379,785,5 16,809,393,766,311,656,230,448,542,351,852,881,090 ,798,676,481,947,445,843,876,689,972,113,188,382,0 77,838,576,766,415,271,554,183,554,023,681,926,442 ,357,773,229,141,527,132,801,050,545,169,980,023,4 29,475,382,981,277,026,411,446,450,732,120,206,920 ,761,648,530,323,773,463,358,502,551,340,699,145,5 22,328,264,108,074,466,176,204,798,818,591,643,822 ,008,785,083,299,073,103,153,980,722,122,415,403,2 64,180,661,744,484,810,522,551,289,556,161,305,278 ,379,785,516,809,393,766,311,656,230,448,542,351,8 52

    • Read the rest of this comment...
  • Small steps (Score:4, Informative)

    by Duncan3 (10537) on Friday February 18, 2005 @06:49PM (#11717809) Homepage
    One small step for mathematics, one giant leap for global warming :)

    Please come join Folding@home [stanford.edu], we're actually doing something worth all that waste heat. :)
  • by zenst (558964) on Friday February 18, 2005 @06:49PM (#11717811) Homepage Journal
    All that distibuted processing power to work out how long to hold the `1` key down :)
  • by sacrilicious (316896) on Saturday February 19, 2005 @09:43AM (#11721797) Homepage
    The study of such numbers has a long and interesting history

    Reminds me of when Bart Simpson's 4th-grade class was forced by Principal Skinner to have their annual field trip take place at a box company (instead of the hoped for chocolate factory / fireworks outlet / circus):

    Tour guide (speaking in monotone nasal voice): The story of how two brothers (and five other men) parlayed a small business loan into a thriving paper-goods concern is a long and interesting one. And, here it is: it all began with the filing of form 637/A, the application for a small business or farm...

It is surely a great calamity for a human being to have no obsessions. - Robert Bly

Working...