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

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

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

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 ?

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

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.

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

[Xylaan]

I used to participate in the project while I was in college.

They use a distributed Lucas-Lehmer Test. This takes days to weeks depending on the computer. However, given the possibily of either implementation bugs or some sort of minor rounding error in the vast amounts of floating point operations being performed (and since it's iterative, if an error occurs early in the run, it could propagate to something large by the end), they do independant verification on any number that's found.

In addition, if you have slower computers, you can elect (or will be assigned) factoring work, which is simply to do first-pass factoring (again, up to a limit to reduce the number of things that have to be tested) on numbers. Any number you can't find a factor for will be flagged as 'factored', and will eventually be scheduled for a LL test.

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: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: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: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/

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 ;)