New Possible Record Prime Number Found

An anonymous reader writes "The Great Internet Mersenne Prime Search (GIMPS), a distributed computing project, has probably found a new record prime number. Two verification runs have started; no errors were found in the initial calculation. The number of primes found lately, four in just over two years, is higher than previously expected. This prime is just under 10 million digits, which means that one of the participants in the project makes a good chance to obtain his or her part of the EFF prize of $100,000 for the first prime of over 10 million digits in the coming months. In 2000, one of the Gimps participants collected the $50,000 reward offered."

Comments

/.ed

[dascandy]

Their computers can calculate a prime number with 10,000,000 digits, but they can't even serve a webpage? Jeez... where are your priorities?

Re:/.ed

[meringuoid]

Their computers can calculate a prime number with 10,000,000 digits, but they can't even serve a webpage?

Ah, but... a number of ten million digits? That has to take up ~ 10MB of disk space. And now the link's been posted to /., where every lunatic is now clicking on it and thinking that by some bizarre geek savant superpower they're going to somehow look at it and go 'yup, that's prime all right' or something...

No wonder the server's a smoking crater now :)

Re:/.ed

[tie_guy_matt]

10MB of disk space? No problem just gzip the file ... oh no wait never mind!

Re:/.ed

[dascandy]

Well... the server is at mersenne.org. I somehow expect them to have found a mersenne prime, which with 10 million digits takes about 15 bytes to store in plain-text, and only 4 if you store it efficiently:

2^35000000-1 => that's in normal form. You only have to store the exponent, the rest is constant. Since it's smaller than 4294967296 you can store it in a normal int (4 bytes), and since it's larger than 16777216 you can't store it in 3 bytes.

Re:/.ed

[meringuoid]

Aha 10 million digits may be easy to store, but deviding that number by other number lower than half that number to prove it is actually a prime number isn't really that easy.

When you're brute-forcing your way to a test for primality of n, you needn't go all the way to n / 2, only up to sqrt(n). If xy = n, and x > sqrt(n), then you should have found the factor y already.

I think there are also more efficient tests that can determine whether a number is prime to arbitrary probability without trying every possible divisor; not my field of expertise, though. Inquire of Google for isprime algorithms.

Re:/.ed

[moro_666]

Their computers can calculate a prime number with 10,000,000 digits, but they can't even serve a webpage? Jeez... where are your priorities?


  Next slashdot news will be how slashdotters managed to wreck the hard disk in the server that contained the 10 million digit prime :p
Now that would be real ./ing power.

  I think it's kindof annoying to install that distributed computing software everywhere where you'd like to use the spare cpu time. My homies mess up their windows machine so often that i've stopped trying to keep anything running there (a machine online 24/7 that shows a web browser and msn for 3-4 hours a day, what a waste).

  Can't they put it in applets that i can run from their webpages ? Surely Java is a bit slower than C in algebra (not really as much as you think, on very simple math tests the difference was about 10-20% last time i measured), so a C client should be available, but a web based client which i can just run in any java enabled browser would definitely increase the userbase.

Re:/.ed

[shippo]

Indeed. The test performed to check that a Mersenne number is prime consists of repeated squaring, followed by the addition of an offset, using modular arithmetic. The number of iterations of the algorithm is equal to the value of the exponent of 2. If the final result is zero, the number is prime.

This only works due to the Mersenne prime being one less than a number with many known factors.

Re:/.ed

[dascandy]

The point behind a mersenne prime is that, in binary, it's always like this:

111111111111111111.................111111111111111 1

They differ only in the number of ones. The point why they are mersenne primes is BECAUSE they have this property. Since these numbers are relatively often prime, it's a lame (*cough*, ok, cheap) way to get to very large prime numbers.

So, all you have to store to know the number is the number of binary digits. Conveniently, that's the exponent in power-of-2 notation.

You can write down the exponent in 4 bytes, I sure hope. If you want to type it out in notepad, try using the notation I provided. It fits in 15 bytes with ease.

Re:/.ed

[vidarh]

You can certainly reduce the number of tests quite dramatically. Someone else pointed out that you only need to check up to the square root.

Of course, if you do know all preceeding primes, then it's just a matter of restricting your test to just that sequence, as everything else by definition have smaller prime factors you'll test against.

If not there's a bit more work, but you can still save a lot over brute forcing it.

If you start at 2 and work your way upward, and for as long as you know the next prime up, you'd only need to test with the next prime.

After that, you can still discard tests with any numbers that can trivially easily be shown to have small prime factors without even trying a division, like all even numbers, all numbers ending in 5 etc.. There are quite a few rules that can be added to just immediately skip a lot of numbers as you're iterating upwards with quite cheap logic.

You can also test the number you will use to test your potential prime by first testing that against a set of small primes (apart from the ones you've already discounted by not generating the test numbers), to quickly discard those test numbers before you attempt a huge expensive division. It's also possible to derive relatively simple rules to check for divisibility of many small primes that may be far cheaper than trying an actual division once you start getting up to reasonably large numbers.

The method of discaring tests against numbers divisible by a set of small primes is known as the Sieve of Eratosthenes... I think there are a few alternative methods - the main benefit of the sieve of Eratosthenes is that the basic algorithm extremely simple and still a vast improvement over brute forcing.

Re:/.ed

[PhraudulentOne]

Indeed. The test performed to check that a Mersenne number is prime consists of repeated squaring, followed by the addition of an offset, using modular arithmetic. The number of iterations of the algorithm is equal to the value of the exponent of 2. If the final result is zero, the number is prime.

This only works due to the Mersenne prime being one less than a number with many known factors.

Lemme guess, your a real hit with the ladies, eh?

Re:/.ed

[dascandy]

You just get more when rooting with a larger prime... Formulae like big primes...

(cleverly avoiding girl jokes by completely forgetting about them)

Re:/.ed

[Anonymous Monkey]

My wife is currently teaching prime numbers at school, so we talk a lot about them over the dinner table.(geek maries geek and talks about math over candle light, weird.) Anyway, the Eratosthenes method you discuss would take a lot of useless calculations out of the mix. The following links will explain it better than I can.

http://www.math.utah.edu/~alfeld/Eratosthenes.html

and http://mathforum.org/dr.math/faq/faq.divisibleto50 .html

Re:/.ed

[AaronCampbell]

It gets better than that. A Mersenne Prime is a prime number that is one less than a power of 2 (like 3=4-1=2^2-1 and 7=81=2^31). Given this: M_n=2^n-1, you also know that for M_n to be a Mersenne Prime, n must be prime. So you don't even do calculations for the rest of the numbers. Read the whole snippet for more info.

Re:/.ed

[rolandog]

you've just increased some geek's hope that he'll find a prime by about 7.7 times

Re:/.ed

[dascandy]

That's not prime. Its an even number of ones, which is trivially breakable into:

111111111.................11111111 (5*10^299 ones) * 100000......00000001 (with 5*10^299 - 1 zeroes).

Do I get a nobel prize now?

Re:/.ed

[dascandy]

Want another? A number that could be a mersenne prime cannot be one if the exponent isn't a prime also.

Proof: For every number with a non-prime exponent E, take two possible factors that compose E as K and F. Now:

11111...111 (F 1's behind each other) times 10000...(F-1 zeroes)...000010000...(F-1 zeroes)...000010000...(F-1 zeroes)...000001 with K-1 times the repeat (and thus K ones) will equal the candidate number.

You can also prove it more mathematically:

sum from (I = 0) to (K-1) over (2^F-1) * 2^(I*F)
Written out, the series goes:
= (2^F-1) * 2^0 + (2^F-1) * 2^F ...
= (2^F-1) * 1 + 2^2F - 2^F ...
= 2^F - 1 + 2^2F - 2^F ...
= 2^2F - 1 ...
= 2^(F*K)
= 2^E

Hope you enjoyed it ;)

10 million?

[Walterk]

Is that all? It'll be real news when it's 42 million.

Re:10 million?

[meringuoid]

42 million? How unimaginative. Personally, I'd like to see a huge prime with a prime number of digits...

Re:10 million?

[BarryNorton]

Personally, I'd like to see a huge prime with a prime number of digits

SB8, the largest non-Mersenne prime currently known, has 2759677 digits (which is prime).

Re:10 million?

[ComaVN]

Preferably in a prime base, instead of the unimaginative base 10

Re:10 million?

[EntropyEngine]

Can someone explain to me why any of this matters?

Is this just more number nerdery, or is there a practical application for such vast and unfathomable numbers?

Re:10 million?

[markov_chain]

SB8, the largest non-Mersenne prime currently known, has 2759677 digits (which is prime).

Moreover, 2759677 has 7 digits, which is prime too! How fun.

Re:10 million?

[BarryNorton]

Our comment numbers, 14297779 and 14298043, are also both prime...

Re:10 million?

[llamaguy]

Yep. You know those fancy encryption schemes that stop the evil criminal soviet fraudsters stealing your credit card numbers? They're based on the fact that, while finding out the product of two primes is easy, finding those two primes again from the given product is harder than it looks for big primes. A 'public key' is the product of two suitably large primes, and a 'private key' is those two primes.

Of course, we're still only on 256-bit encryption right now. Should be a while until however-many-bits-this-prime-needs-bit encryption will pass into common use.

Re:10 million?

[certel]

I was thinking the same thing. Maybe they could use the computers for other things, such as gene mapping and quit giving away thousands of dollars for something like this.

Re:10 million?

[pjt33]

For a large prime P the odds are pretty good* that there's an prime Q such that sqrt(P) < Q < P. That's equivalent to Q < P < Q^2, so P base Q has 2 digits.

* I'd say 1, but after 30 seconds' thought I haven't found a trivial proof.

Re:10 million?

[pomakis]

Hello?!? Where's 2*2*3*75011 when his infamous postings would finally be relevant?!?

I can't access the site

[ReformedExCon]

I am curious. Is this the next sequential prime after the previous one? Is it possible that there are other primes between this new one and the one found before it?

Re:I can't access the site

[BarryNorton]

It's definitely possible, and what's more they wouldn't know - they're only going for the easy pickings of Mersenne primes

Re:I can't access the site

[Moby Cock]

It is possible, and in fact, likely. Although they will not be Mersenne Primes. A Mersenne Prime is of the form 2^n - 1, not all prime numbers follow that form (e.g. 11)

Re:I can't access the site

[Anonymous Coward]

There are almost certainly a very large number. Mersenne primes are extremely rare compared to ordinary primes.

The Prime Number Theorem tells us that in a region of d around a large number n, there are approximately d/ln n primes. For a 9 million digit n, ln n is about 21 million, so one expects to see one prime every 21 million numbers. For example, between 10^9000000 and 1.1*10^9000000, one expects 5*10^8999991 prime numbers.

Re:I can't access the site

[shrykk]

I've been playing with the math myself for primes, but what library or technique do they use to get past 32bits? It's probably simple, but I'd appreciate some help.

You'll probably find this article interesting - it covers prime finding (in C) from naive algorithms to complexe ones involving paging bit arrays in and out of memory: "Fun With Prime Numbers"

Re:I can't access the site

[slavemowgli]

Unfortunately, what the grandparent wrote is misleading. Yes, the GIMPS project only checks Mersenne primes, so it's entirely possible (highly likely, even) that there are non-Mersenne primes in between them.

BUT it could also be that there's other Mersenne primes in there that we haven't found yet. The exponents the GIMPS project tests are not handed out in sequential order, so there are still "gaps" in there that haven't been checked and double-checked. I'm not sure what the current "watermark" is; the project has definitely checked all Mersenne numbers up to M6972593 (the 38th Mersenne prime), at least, but while finding another Mersenne prime that's smaller than another one already found before is unlikely, it can't be ruled out.

So there just might be smaller Mersenne primes, too (in addition to the smaller non-Mersenne primes that are almost certainly there).

Mersenne Primes

[BarryNorton]

Bah, show me a new non-Mersenne prime and I'll be impressed...

Re:Mersenne Primes

[fatphil]

Your wish is my command.

Let Phi(n,x) be the n-th cyclotomic polynomial evaluated at x.
Therefore Mersenne primes are Phi(p,2) for some p.
I found the prime Phi(98304,1063662)=1063662^32768-1063662^16384+1 the other day. However, it is _tiny_ with only 197000 digits (something like the 240th largest in the world).

Lots of people are finding large prime numbers - if you find one over ~64000 digits, it'll be one of the largest 5000 known primes.
See http://primepages.org/

Why prime numbers ?

[Alarash]

I'm just wondering, what's the point to calculate the largest possible prime number? I mean, there are a lot of distributed computing projects that sound more... useful : Climate Prediction (Hello Katrina), research protein-related diseases or another doing wider research on human diseases. That's just to name a few projects using the Berkeley Open Infrastructure for Networks.

So I'm not being sarcastic here, my genuine questions is : why should I spend my free computing power on calculating prime numbers instead of research to cure cancer?

Re:Why prime numbers ?

[Down8]

As the item suggests: to get a $100,000. :^)

-bZj

Re:Why prime numbers ?

[Moby Cock]

To be honest. Why not? Sure a cure for cancer would be great, but for some, research for the sake of research is interesting. I am curious as to what Mersenne primes are calculable. Is that not sufficient justification?

Re:Why prime numbers ?

[meringuoid]

So I'm not being sarcastic here, my genuine questions is : why should I spend my free computing power on calculating prime numbers instead of research to cure cancer?

Because you like numbers and think big primes are cool.

Seriously.

This is pure mathematics, it's number theory. Don't expect practical applications; if they turn up, they're a nice bonus, but they're not why you do mathematics.

There may actually be a practical result of this research eventually; the number theory surrounding primes is closely related to the security of the RSA cipher that most of the internet's commerce relies on. It's conceivable that this kind of work might eventually lead to a breakthrough in cryptanalysis. But I wouldn't count on it.

Re:Why prime numbers ?

[Burb]

Because pure mathematics sometimes turns out to have unexpected real-world benefits. Ancient Greek mathematicians such as Apollonius of Perga studied properties of the conic sections (circles, ellipses, the parabola, the hyperbola) as pure maths with no expectation of practical gain. Two thousand years later, we found that planets move in ellipses, that projectiles follow parabolic paths, and so on. Hey presto, that ancient pure mathematics becomes useful...

Re:Why prime numbers ?

[DenDave]

Actually it works the other way round.. the more primes are known, the less secure your encryption becomes. Brute forcing nowadays is more like a dictionary attack with combinations of primes.

Re:Why prime numbers ?

[fatphil]

I cannot speak for the EFF. But I do know several people directly involved with the administration of those awards, and have discussed many topics with them.

The smaller prizes - 1M digit (already awarded), and 10M digits (still pending) are actually pretty small and unimportant. They can be attacked simply by throwing huge numbers of inexpensive commodity PCs at the task. That's basically what GIMPS is. The larger prizes are the important ones, as they reward a much harder achievement. The algorithms used to tackle such tasks don't scale particularly well. It's more than 10 times harder to do a problem 10 times bigger. This in part is because of the hierarchical memory system that PCs have. Small fast caches, other medium-sized slower caches, and then large quantities of relatively slow main memory. FFTs really don't like such a hierarchical memory architecture, as they grab data from all over the place all of the time. Caches become very hard to use effectively, and enormous L1 caches are prohibitively expensive.

So these later prizes will almost certainly be awarded to systems either based on new algorithms that are vastly more scalable than current FFTs, or on new hardware (memory) designs which somehow get around the caching issue.

Moving up to even larger sizes, it may become impractical to perform such calculations on a single PC. Therefore communications systems will want to be invented that provide no more latency than main memory.

Those are real concrete advances in computer technology, and it's those that are being rewarded. The primes are almost a red herring.

Re:Why prime numbers ?

[fastgood]

the more primes are known, the less secure your encryption becomes

But the more we know about those people who calculate primes in their spare time,
the safer America will become.

Re:Why prime numbers ?

[VAXcat]

Yah...when primes are outlawed, only outlaws will calculate primes.

Re:Why prime numbers ?

[karthikg]

Mersenne prime finding is not the same as verifying a universal truth like 2*a = a+a. It is *NOT* yet proven that the number of Mersenne primes is infinite. So it is not a guarantee that you run a huge collection of machines and you always find the next bigger mersenne prime. The fact that we do indeed find them, makes it more convincing that the conjecture (that the number of mersenne primes is in fact infinite) is true.

BTW, this is cute

[ReformedExCon]

The ID for this story is 171673 which is itself a prime number.

Clever clever!

Re:BTW, this is cute

[chillmost]

Nerd!

Re:BTW, this is cute

[njchick]

The ID for this story is 171673 which is itself a prime number.

Extra credit to /. editors if the dupe story ID will also be a prime.

FYI

[Walterk]

The next largest known prime, as of today, is 225964951 1 (this number is 7,816,230 digits long); it is the 42nd known Mersenne prime. M25964951 was found on February 18, 2005 by Martin Nowak, a member of a collaborative effort known as GIMPS.

The third largest known prime is 224036583 1 (this number is 7,235,733 digits long); it is the 41st known Mersenne prime. M24036583 was found on May 15, 2004 by Josh Findley (member of GIMPS) and it was announced in late May 2004.

The fourth largest known prime is 220996011 1 (this number is 6,320,430 digits long); it is the 40th known Mersenne prime. M20996011 was found on November 17, 2003 by Michael Shafer (and GIMPS) and announced in early December 2003.

Historically, the largest known prime has almost always been a Mersenne prime since the dawn of electronic computers, because there exists a particularly fast primality test for numbers of this form, the Lucas-Lehmer test for Mersenne primes.

The largest known prime that is not a Mersenne prime is 27653 × 29167433 + 1 (2,759,677 digits). This is also the fifth largest known prime of any form. It was found by the Seventeen or Bust project and it brings them one step closer to solving the Sierpinski problem.

Some of the largest primes not known to have any particular form (that is, no simple formula such as that of Mersenne primes) have been found by taking a piece of semi-random binary data, converting it to a number n, multiplying it by 256k for some positive integer k, and searching for possible primes within the interval [256kn + 1, 256k(n + 1) 1].

Re:FYI

[gowen]

The largest known prime that is not a Mersenne prime is 27653 × 29167433 + 1.

Erm... isn't that an even number?

(Yes, I know, your "to the power of" got nobbled).

Why anything?

[Poromenos1]

Why do people calculate digits of pi? Why do they scale mt. Everest? Because they have small penises.

Re:Why anything?

[richie2000]

"No penis" is just a special case of "small penis".

Headlines

[sanctimonius hypocrt]

The number of primes found lately, four in just over two years, is higher than previously expected.

I can just imagine the newspaper report: Scientists report more numbers than previously thought.

FPGA prime number calculator

[cheesy9999]

I made a FPGA based prime number calculator back in one of my EE courses and it was pretty freakin fast. They should make a giant super optimized version of my little thing.

For newbies

[chord.wav]

If you think this is your grand chance to win money easily using GIMPS, think again.

As it states here

If you were to find a 10,000,000 digit prime today the above rules imply that $5,000 would go to Michael Cameron, discoverer of the 39th known Mersenne prime, $5,000 would go to Michael Shafer, discoverer of the 40th known Mersenne prime, $5,000 would go to Josh Findley, discoverer of the 41st known Mersenne prime, $5,000 would go to Dr. Martin Nowak, discoverer of the 42nd known Mersenne prime, $0 would go to discoverers of algorithmic breakthroughs, $5,000 would go to GIMPS primarily to fund future awards, $25,000 would go to charity, and $50,000 would go to you.

Now the bad news. Testing a single 10,000,000 digit number takes two months on a 2 GHz Pentium 4 computer. Your chance of success is roughly 1 in 250,000.
Someone may find a 10,000,000 digit prime before GIMPS does.

Radical compression scheme

[benhocking]

Consider this as a radical compression scheme. Rather than storing every single digit, you store a simple formula for arriving at the number. In this case, that formula is 2^x-1. All you need to store is x, which requires O(lg n) bytes to store where n is the number of digits in the original number.

What strikes me as somewhat amusing is that calculating 2^x-1, for an arbitrarily large x, requires O(2^x) amount of time. Of course, since 2^x is less than 10 million here, and it's actually quite a small bit of work O(2^x) times, it's no big deal.

Better tell me...

[Vo0k]

how much do I get for finding the extraterrestial in SETI@Home?

Re:why go for under 10k?

[Markus Landgren]

It's 10M, not 10k. And the EFF award for another prime below 10M digits is zero, no more payouts will occur until someone finds a number with at least 10M digits. But GIMPS was around long before the EFF award was announced. They are systematically testing "all" mersenne numbers, not only those elegible for prizes. Ultimately, it's up to the participants. The client has a checkbox for only downloading assignments big enough to qualify for the prize.

Re:Biggest useless (yet meaningful) number ever?

[shreevatsa]

Yep. I remember reading a Number Theory book long ago that Skewe's number 10^10^10^34 was "the largest number which has ever served any definite purpose in mathematics", but apparently, things have changed since then. The largest meaningful (but useless, as you pointed out) number used is apparently Graham's Number, which has even been listed by the Guinness Book of World Records as such. Tetration is explained here, or quite a lot of notation is explained here.

The best page about large numbers, however, is clearly the one at MROB, beautifully written.

But the amusing thing about this Graham's Number is that it is an upper bound on some quantity, which experts believe is equal to 6. That's right, SIX. So it's not only the largest number ever used; it's also probably the worst upper-bound ever :)

Re:Probably?

[geoffspear]

I'm still waiting for someone to publish the largest known odd number. I plan to memorize it to impress women.

New Possible Record Prime Number Found

[anshil]

Smallest Positive Mersenne Prime-Number ever: 3

Hey, also small is beatuiful.

Products of primes

[ockegheim]

Last week while factorizing random 5 digit numbers with a calculator (very bored at work) I decided that if a number has two prime factors it can't have any other factors. Is this true, and is the mathematics behind it obvious or complicated?

Re:Prime numbers aren't all that rare.

[Anonymous Coward]

The trouble isn't making an arbitrary number in the hopes that it's prime, it's in proving that it's prime. There are relatively simple methods to look for Mersenne primes, they just take constant time for crunch. For non-Mersenne primes, you'd have to crunch out every possible factor to prove that it's prime, a tedious process. The goal isn't to discover every prime number, there are far too many. We just want bigger prime numbers because it's a challenge. If you want to make arbitrary primes, you're free to, just know that it'll be a pain to prove it is prime.

Oh, and FYI, 1 000 000 ... 017 was debunked rather easily due to the fact that in base 10, if the sum of the digits is divisible by three (1+1+7=9, 9%3=0), then the number itself is divisible by three as well. It's covered at Wikipedia and the other repository of all geek knowledge, bash.org. Proving something's not prime can be surprisingly easy.

Re:How do they check a number that big for primene

[Jerry Coffin]

Do they recursively calculate if all the numbers before it modulus divide out to zero? Or something along those lines?

No -- for Mersenne numbers, they usually use the special number field sieve.

Darn It!

[Nom du Keyboard]

This prime is just under 10 million digits

To big for my /. .sig, darn it!

Re:WTF?

[bk4u]

just do what I do, use 1-2-3-4-5