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

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

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

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:Radical compression scheme

[pjt33]

What do you mean by "calculating"? Converting to base 10? You can convert to base 16 in O(x) time.

Converting to base 16, base 2, whichever

[benhocking]

If you want to just represent this as 111...111, it will obviously require O(n) or O(2^x) time, since there are O(2^x) digits. To represent it as FFF..FFF (or 3FF..FFF, etc., depending on the situation), will require O(n/16) time which is still O(n) or O(2^x), by definition of O().

Converting to base 10 is also only O(n), but would be slightly slower, of course.

Subtracting 1 requires O(n) carries

[benhocking]

2^x = 1000...0000 in binary.

2^x-1 = 111...1111.

There are intelligent ways to do this very quickly; however, it's still O(n), or O(2^x), where n is the number of digits. Let's assume that you have an infinite number of 64-bit registers, and each register can subtract one in constant time (for a fixed size register, this is a trivial statement). If you have n binary digits, then you'll require n/64 registers to store 2^x. Two carry the subtraction from each register will require O(n/64) time, and O(n/64) is

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 eve

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

[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

[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

[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.htm l [utah.edu]

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

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. [mersennewiki.org]

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

[dascandy]

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

(cleverly avoiding girl jokes by completely forgetting about them)

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?

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

[pomakis]

Hello?!? Where's 2*2*3*75011 [slashdot.org] when his infamous postings would finally be relevant?!?

Re:10 million?

[ComaVN]

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

Re:10 million?

[BlowChunx]

Wouldn't that just be 1?

At least it would be if I get to pick the base after I found the prime number...

Re:10 million?

[BarryNorton]

No... that's not a prime number of digits.

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?

[penguinoid]

Actually, *all* mersenne primes have a prime number of digits.

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?

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

Re:10 million?

[CastrTroy]

But this really doesn't help at all in cryptography. So we can spend thousands of computing hours finding big primes with known algorithms. What we really need would either be new algorithms which could find large primes as this, or a new algorithm to factor large primes in order to defeat encryption. Another thought is, what use for encryption is using large primes such as these. If we decide we are now using 1,000,000 bit primes for encryption, because we have an easy way of finding them, then maybe

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?

[Metasquares]

You can get a new perfect number out of this (2^(n-1) * (2^n)-1), but other than that, there's not much point. Maybe cryptography.

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

[p2sam]

yeah, me too. But what kind of a sociopathic marker would think that n could be anything but integers? n can only represent integral values, it's blasphemy to think otherwise!!!

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 pr

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 [wolfram.com] 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

[gnasher719]

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

If p is a prime, then the distance to the next smaller prime is on the average about ln (p). Cases where the gap to the next smaller prime is more than (ln (p))^2 seem to be exceedingly rare. So yes, there are gazillions of primes between this one and the next smaller one.

There may be no Mersenne primes between this one and the previously la

Re:I can't access the site

[Kjella]

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?

It is for all intents and purposes certain. The prime number theorem will give the approximate density of primes, even though it can't locate them exactly so we know there are many many more primes out there. For the rest of the primes we have no efficient way of determining if they are prime. We have very fast algorithms to determine if a number

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" [troubleshooters.com]

Mersenne Primes

[BarryNorton]

Bah, show me a new non-Mersenne [wolfram.com] 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/ [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 [climateprediction.net] (Hello Katrina), research protein-related diseases [scripps.edu] or another [bakerlab.org] doing wider research on human diseases. That's just to name a few projects using the Berkeley Open Infrastructure for Networks [berkeley.edu].

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 ?

[Slick_Snake]

What's the point of a large mersenne prime? It is useless. Mersenne primes are easy to calculate and completely pointless for encrytion. Find me a real use for such a number and then I'll care until then I say SO WHAT.

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 ?

[Alarash]

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.

Thanks, that's all I wanted to know.

Re:Why prime numbers ?

[Analogy Man]

I am all for 33,000,000 bit encryption. That ought to keep the NSA's brute force decryption of my subversive activities spinning for a few millenia.

Re:Why prime numbers ?

[jellomizer]

Unless they start with the big prime numbers first.

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:Why prime numbers ?

[VAXcat]

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

Re:Why prime numbers ?

[hackstraw]

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.

But someday, we will be able to factor them!

Re:Why prime numbers ?

[meringuoid]

Excuse me, but this project it totally useless!

Of course. It's pure maths, done for its own sake. You think these people care for the practical usefulness of their work?

I have never done anything "useful". No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world. I have helped train mathematicians, but mathematicians of the same kind as myself, and their work has been, so far at any rate as I have helped them to it, a

Re:Why prime numbers ?

[imsabbel]

Sorry, this project is NOT maths.
Developing the algorithms was maths. Running them on 1000s of computers wasting resources is just like trying to to verify that 2*a = a+a by calculating it for all a`s.... A waste of time and no benefit for science or math.

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

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 ?

[Darth_Burrito]

Better question... why is the EFF offering prize money for finding primes? It seems only very loosely related to their purpose. That's not the kind of thing I gave them money to do.

Re:Why prime numbers ?

[Viper Daimao]

Yeah, thats exactly what I was wondering. If theres $100,000 dollars being offered for a prime over 10 million digits, then I would think it must have a practicle application. I guess I was expecting more than just, theres a small chance it could help with cryptography. Oh well, I have never given any money to the EFF, so I guess I can't get too bothered by what they do with their money.

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 t

Re:Why prime numbers ?

[Mantorp]

Then the question is why do these people care enough about it to donate money for this cause specifically rather than curing cancer or finding aliens? It's the old, why do people care about saving old buildings or seemingly insignificant insects when there are people starving? Or to put it in ./ context trying to resurrect sci fi shows that were taken off the air instead of whatever...

Re:Why prime numbers ?

[pomakis]

why should I spend my free computing power on calculating prime numbers

So you can determine the optimum number of buckets for a really really really really large hash table?

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 [wikipedia.org]. M25964951 was found on February 18, 2005 by Martin Nowak, a member of a collaborative effort known as GIMPS [wikipedia.org].

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 [wikipedia.org].

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 [wikipedia.org] and it brings them one step closer to solving the Sierpinski problem [wikipedia.org].

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

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.

Re:Headlines

[HD Webdev]

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

That's an Onion [theonion.com] worthy headline!

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.

Biggest useless (yet meaningful) number ever?

[Sockatume]

Is there another candiate?

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 [york.ac.uk], which has even been listed by the Guinness Book of World Records [ucsd.edu] as such. Tetration is explained here [wlonk.com], or quite a lot of notation is explained here [york.ac.uk].

The best page about large numbers, however,

For newbies

[chord.wav]

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

As it states here [mersenne.org]

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:For newbies

[BarryNorton]

Your chance of success is roughly 1 in 250,000

Better than buying a lottery ticket?!

why go for under 10k?

[v1]

If I'm reading this correctly, the reward for a prime > 10k digits is twice that the reward for the next prime 10k. So wouldn't it make more sense for them to skip ahead to 10k digits and start looking there instead?

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.

Better tell me...

[Vo0k]

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

New Possible Record Prime Number Found

[anshil]

Smallest Positive Mersenne Prime-Number ever: 3

Hey, also small is beatuiful.

Re:New Possible Record Prime Number Found

[the computer guy nex]

2^1-1=1. 1 is by definition prime, mathematicians convieniently forget it to make other math work :P

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:Products of primes

[Lord Crc]

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

A composite (ie non-prime) number is a product of at least two prime numbers, otherwise it would be a prime number. That follows directly from the definition of a prime number. A composite number can have more than two (different) prime factors though. Take your favorite number 42 = 2 * 3 * 7. Or if you want a 5 digit number: 11 * 23 * 127 (a Mersenne prime, btw :) =

Whao this has so many digits

[Arthur B.]

I'm totally using it to produce my GPG secret key, with so many digits it'll never be cracked!!

So, will THIS GIMP be...

[davidsyes]

EFF'ed? That's going to be quite some long digita...

Sorry, i just had to...

Wow!

[Chemisor]

I finally have an unbreakable number to use as my GPG key!

WTF?

[UnknowingFool]

The Great Internet Mersenne Prime Search (GIMPS), a distributed computing project, has probably found a new record prime number

Damn it! Now I have to change my luggage combination again. You bastards.

Darn It!

[Nom du Keyboard]

This prime is just under 10 million digits

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

Re:I'm aiming at the $150,000 prize

[moonbender]

Most important note to this story: (Prize money comes from a special donation provided by an individual EFF supporter, earmarked specifically for this project. Prize money does NOT come from EFF membership dues, corporate or foundation grants, or other general EFF funds.)

So at least they're not wasting your membership fees on this "huge scientific problem".

Re:Probably?

[BarryNorton]

Why only probably? Just divide it by 2 and see if it comes out even.

I think you're confusing odd [wolfram.com] and prime [wolfram.com] numbers...

Re:Probably?

[shreevatsa]

Or he has taken this proof of All odd numbers are prime [gdargaud.net] very seriously ;)

My favourites from that list:

Physicist:
3 is prime, 5 is prime, 7 is prime, 9 is an experimental error...

Logician:
Hypothesis: All odd numbers are prime
Proof:
1. If a proof exists, then the hypothesis must be true
2. The proof exists; you're reading it now.
From 1 and 2 follows that all odd numbers are prime

and oh, lots of others.

Another one of note:

GNU programmer:
% prime
usage: prime [-nV] [--quiet] [--silent]

Re:Probably?

[FirienFirien]

"Just divide it by 2"

What on earth are you talking about? At first look, you seem to be thinking of "odd numbers", a fascinating concept made yet simpler by the fact you don't even have to divide the huge number by anything, just look at the last digit and see whether it's odd or even. Yet that still doesn't fit with your 'divide it by 2 and see if it comes out even; you seem to take "prime number" to mean "anything that isn't divisible by 4".

Re:Probably?

[geoffspear]

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

Re:Probably?

[psergiu]

Here it is [york.ac.uk]. Just spell-it out to them digit by digit and they will be all over you when you finish.

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 [wikipedia.org], 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

Re:Prime numbers aren't all that rare.

[Jerry Coffin]

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.

This is not even close to correct. Testing primality this way becomes impractical around 30-40 digits or so (depending a bit on how patient you are) and there are methods that

Re:Upon further review...

[iphayd]

Eureka!

I needed a prime number ending in two (that is not two) for my Cold Fusion generator and Perpetual Machine.

It also will allow me to make Windows virusproof.

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 [wikipedia.org].