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

[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

[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

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

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

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

BTW, this is cute

[ReformedExCon]

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

Clever clever!

Why anything?

[Poromenos1]

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

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

New Possible Record Prime Number Found

[anshil]

Smallest Positive Mersenne Prime-Number ever: 3

Hey, also small is beatuiful.