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

[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

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

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 ?

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

[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:10 million?

[meringuoid]

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

BTW, this is cute

[ReformedExCon]

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

Clever clever!

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

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.

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.

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

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?