Slashdot Mirror
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."
The ID for this story is 171673 which is itself a prime number.
Clever clever!
Jesus saved me from my past. He can save you as well.
As the item suggests: to get a $100,000. :^)
-bZj
.sig
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].
"If anyone needs me, I'm in the angry dome."
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.
Real Daleks don't climb stairs - they level the building.
Finding common divisors is usually done with the formula of Euclides. That brings it down to iirc the log of the number, which is just 10000000.
A very good (but not perfect) sieve for primes with no false negatives is the Lucas-Lehmer primality test. I expect them to use that for first selection runs.
For a full certainty, the only cause (I think) you have is to repetitively try to divide it by another and figuring out you keep stuff left. I am quite certain they're using distributed computing for that.
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)
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.
There are undoubtedly more primes between this Mersenne prime and the last one as there is roughly a million orders of magnitude between this new number and the previous record. Good luck trying to prove that one of them is prime however. Mersenne numbers are "easy" to prove composite or prime by running the Lucas-Lehmer test. http://primes.utm.edu/mersenne/index.html has some background info.
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.
The point behind a mersenne prime is that, in binary, it's always like this:
1 1
111111111111111111.................11111111111111
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.
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.
Ben Hocking
Need a professional organizer?
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.
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.
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.
HAH! I just wasted a second of your life making you read this, but I wasted a minute of mine thinking it up. DAMN.
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.
... 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.
Oh, and FYI, 1 000 000
Mersenne Numbers (numbers of the form 2^n -1 which as you say are 111.111 in binary) are not relatively often prime...
:P
There are only 42 confirmed mersenne primes, the largest being 2 ^ 225,964,951-1...
So only 42 out of 225,964,951+ are prime... relatively infrequent I would say
No -- for Mersenne numbers, they usually use the special number field sieve.
The universe is a figment of its own imagination.
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).
quidquid latine dictum sit altum videtur.
http://www.math.utah.edu/~alfeld/Eratosthenes.html
and http://mathforum.org/dr.math/faq/faq.divisibleto50 .html
We are the Borg...
The special number field sieve is an integer factorization algorithm. It is not generally used for primality testing. The task of primality testing is in practice dramatically different from integer factorization, even though to one uneducated or moderately educated in mathematics the two problems might appear similar. In particular, the special number field sieve runs slower than polynomial time, so running it on a number of 10 million digits is wildly impractical.
Primality testing for Mersenne numbers is actually performed using the Lucas-Lehmer test, which runs in polynomial time and has little to do with the special number field sieve or indeed with any integer factorization algorithm at all.
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.
Surviving America