Slashdot Mirror
45th Known Mersenne Prime Found?
An anonymous reader writes "The Great Internet Mersenne Prime Search (GIMPS) has apparently discovered a new world-record prime number. A GIMPS client computer reported the number on August 23rd, and verification is currently under way. The verification could take up to two weeks to complete. The last Mersenne prime discovered was over 9.8 million digits long, strongly suggesting that the new value may break the 10 million digit barrier — qualifying for the EFF's $100,000 prize!"
http://en.wikipedia.org/wiki/Mersenne_prime
Fun.
How we know is more important than what we know.
So there!
To what use will this long, long prime be put?
Absolutely none whatsoever. That's the beauty of mathematics.
And you only get 6 digits in prize money? What a rip off. That is only one $digit per 1.67 million prime digits.
To what use will this long, long prime be put?
To pick up chicks!
"Hey babe! I just found the largest prime evar! Your place or mine?"
When it comes to cryptography, when youbigger the prime numbers you have the harder it is to break the encryption.
According to their own benchmark pages a newer Core 2 Duo E8500 process in less than 21 days. Just recently I know that password cracking programs were written to use GPU's which dramatically increased the performance. Wouldn't writing code to run this on the GPU's result in even faster processing times?
I was hoping it would be me. I have been using ./mprime on all my boxes for years now.
Congrats to the team and world.
"The price good men pay for indifference to public affairs is to be ruled by evil men." ~Plato (427-347 BC)
...he asks on slashdot.
From the GIMPS website:
Finding new Mersenne primes is not likely to be of any immediate practical value. This search is primarily a recreational pursuit. However, the search for Mersenne primes has proved useful in development of new algorithms, testing computer hardware, and interesting young students in math.
The beauty is that it doesn't HAVE to be useful.
Agreed. People should be using their extreme CPU cycles for things that matter, like helping the SETI program or running Microsoft Vista.
I'm pretty sure that in the past, the government would pay money for large prime numbers to use for encoding purposes. I don't know if they still do but they used to pay 1000 dollars (I think it was 1000) for primes over 100 digits.
And work backwards, that will find the largest much faster than starting at zero.
That depends. If it's over 10,000,000 digits then it will be cashed in for $100,000.
Slashdot: Failed Car Analogies. Amateur Lawyering. Anecdote Battles.
You shouldn't think like that. Just think about your question, seriously. Whatever we do is pointless and useless and everything will be destroyed eventually through the heat death of the universe.
That being said, all that is important is that you have fun doing whatever you do. Believe it or not, some people really dig maths. Also, it's one more thing the species knows.
But when it comes to primes in the 10 million digit range (I couldn't even guess how many bits you would require for a number that large)
About 33 million bits ( ln(10)/ln(2) = 3.3219 ) or 4MB.
10 million digits would be more than 31 MB. It's a simple conversion from digits to bits, you just multiply by 3.32 (the base-2 log of 10).
Sure, you are excited now, but I predict you will look back on this moment with indifference once the 46th is discovered. For now, I'm going to keep the champagne on ice.
I Heart Sorting Networks
...even!
They don't, at least for numbers that small. If they did, you could take a copy of ssh-keygen and a second-hand computer and make millions in fairly short order.
>> To what use will this long, long prime be put?
We'll sell it into slavery on the Venusian mining colonies, what else you fool?
My new lock combination...
I guess some of us have different standards on beauty...
5 years ago few believed that a simple prime number could be calculated to 10 million digits. There was a lot of scepticism that a prime number could be calculated so large. A prime number, calculated to 10 million digits?? pfft. But now, 5 years later GIMPS has calculated Mersenne primes over 9 million digits using computers of all ages, all over the world. That's because GIMPS is scientifically proven to work. It's not a gimmick.
...
(Random interviews)
Q: What happened when you participated in the GIMPS project?
A: Ah.. It got bigger.
Q: And you're not embarassed to say that?
... why the EFF considers it worth $100,000 of donated funds to pay someone for finding a 10,000,000-digit prime number. That is not what my donations were intended to do.
Go fix warrantless wiretapping, then go looking for prime numbers, kthxbye.
Since this is a particularly good prime, we should
standardize on it. That way we wouldn't have to
find our own ones every time we want to use RSA.
"Physics is like sex. Sure, it may give some practical results, but that's not why we do it." - Richard Feynman
I'm guessing it's the same logic at work here.
The submitter or editor could have at least typed the number into the summary. Lazy bastards.
I wonder how much electricity was used, and therefore coal and #6 burned, to find that prime - which will be used for what exactly?
Because doing it by hand is a real bitch and a half. Doing it by hand in moon or candle light sucks worse, I must add.
Navicula hydraulica plena anguilarum est. Omnes castelli tuus nostri sunt. Ed elli avea del cul fatto trombetta.
Oblg.
http://xkcd.com/435/
This is not a sig.
You forgot to divide by 8...bits != bytes
I wonder if the guy who's computer happened to be lucky enough to find the prime will be the one to get the prize.
// MD_Update(&m,buf,j);
...is a list of all the prime numbers whose length in number of digits is also a prime number as well. I wonder if anyone has found any really big ones of those.
I think big prime numbers are a clue. I just don't know what they are a clue to.
Because it's 2^n-1 it'd be 1111111....1111111 (the prime number is entirely made of 1s in base 2). So there's way less than 31MB of information in the number
// MD_Update(&m,buf,j);
It goes towards the enormous knowledge on prime number theory.
The problem of if there is a pattern to the sequence of prime numbers is unknown. That is, if I ask you what is the 69th prime number, the only known general algorithm is to computer the 1st prime, 2nd prime and so on until the 69th prime. And, also there are unsolved problems with Mersenne primes as well.
So, if someone comes up with a good theory, then it's good to have some big examples.
And, in case you didn't know, prime number theory is used in cryptography.
And who gets the prize, GIMPS or the person running the client?
If it's the latter i'll go download the client right now.
I thought you used primes for encryption?
I wouldn't say the 45th known Mersenne prime has been found. I'd say the first unknown Mersenne prime has been found.
My friends and I wrote a unique prime number sieve, using previously unknown numerological techniques (exploiting digital roots).
You can find our sieve here:
http://jessicalogsdon.com/page5/page5.html
We are currently turning our sieve in a method for rapidly factoring semi-prime numbers. Digital root mechanics have certain properties that make it easy to identify semi-prime candidacy positions in a by-9 table of the natural numbers.
A PDF at the bottom of the above-linked site explains our latest investigation of solving for [p, q] where n = p*q. The source code on the page is our prime sieve implemented in Perl.
Big Money! No Whammy! You, too, could become a hundred-millionaire M.O.H.'ing RSA to the ground!!
-=/\- Jizzbug -/\=-
The summary is right. The parent is wrong and/or suffering from missing zero syndrome.
Well.. maybe. Or Maybe not. But Definitely not sort of.
On slashdot, even the submitters don't RTFA apparently:
Or you didn't read it properly: the bit about being just short of 10 million is about the 44th when it was new, not the new new prime.
So little time...
Sig this!
I do IT-support in the school district...let me tell you:
The kids were in a veritable state of mathematics riot today.
Smoking pot, getting laid, and blowing off responsibility is so not punk rock.
God...do these guys realize how embarrassing they make adulthood?
That has to be one of the best penis pill ad spoofs I've ever read. Kudos on that classy rewrite.
My only question is where the reasonably attractive blond chick who blinks too damn much comes in.
Try not to take me more seriously than I take myself.
I think the real question is why it is worth $100k. I'd sure be interested to know, especially seeing that my system can probably attempt to find prime numbers pretty damn quick if it's a threaded app.
How are sites slashdotted when nobody reads TFAs?
Remind me to change the combination on my luggage!
Make SELinux enforcing again!
So this is like math's version of Paris Hilton? Pretty but useless?
basically, they distribute the prize to contributors...currently $50,000 would go to you
One last thing: Sometimes I wonder; "Is that someone's signature? Or do they type that at the end of each post?"
doing it by hand would be like building the pyramids, by yourself.
it's not a weekend project, just writing down all the numbers from 1, to the number composed of at least 9 million but possibly ten or eleven million digits long... much less then dividing that number by every number from 1 to the number of the same length to make sure it is only evenly divisible by itself, and 1.
i repeat myself it's like trying to build they pyramids by yourself. or even better, trying to build a four lane highway by yourself. I remember hearing about a guy from Duluth Minnesota, who had been trying to build a highway the most direct route between Fargo, ND and Duluth, MN, and he actually started on the Duluth side, i know he didn't get far, but Duluth Minnesota is one of those 'rare' towns that was booming about 100 years ago, but then started shrinking (i forget when) and has never really completely recovered.
the guy started on his quest to get the highway built believing a direct route to Fargo would increase trade and tourism and what not (it would save on average an hours drive each way)
but i think he finally died, having completed somewhere between 12-40 miles of highway.
today's PCs are like having millions of number crunching slaves with never ending papyrus scrolls, there are things computers can do that a human being would never complete if they lived a million years. and even with those millions of number crunching slaves some things take a long time to compute.
the point being, the reason why people do these things with computers is because computers are the only thing that can do them, and to be the first to do something vastly unimaginable by normal standards. kinda like, 'why did we shoot a robot lander to mars?' instead of say, making beer free for everyone in the united states for a day.
https://www.gnu.org/philosophy/free-sw.html
Over a hundred comments posted and I see no ridicule of their silly silly self-deprecating name?
Have years of open source naming conventions desensitize you so?
actually, it can be used as a benchmark or the stability and number crunching abilities of a new, never burned in personal computer. if the computer gets the numbers wrong, or says other numbers are evenly divisible within the number, you know something is seriously wrong, and you can RMA the parts that are screwing the pooch.
much better than say, finding 6 months down the line that your computer keeps randomly rebooting because of a serious flaw in the chips inside it and oh wait it was 6 months tough luck trying to RMA things now...
https://www.gnu.org/philosophy/free-sw.html
That has to be one of the best penis pill ad spoofs I've ever read. Kudos on that classy rewrite.
Not a troll
Thanks! I almost didn't post it, I figured it was boring. How wrong I was apparently. The girl comes in on the "It's not a gimmick!!" line IIRC.
And mods, WTF? Parent is most definitely not troll.
I saw this joke posted on slashdot like, less than a week ago,b ut it's so relevant to the discussion ... fuck it.
"An engineer, a physicist and a mathematician were all staying in a hotel, when each of their rooms individually caught fire. The engineer did some basic math, flooded the floor and said, "it is out." The physicist did more complicated math, used just precisely the amount of water needed to put out the fire and said, "It is out." the mathematician did a lot of complicated math, said, 'I HAVE SOLVED IT!' and went back to bed."
Non impediti ratione cogitationus.
Testing a single candidate Mersenne prime takes a month of straight computation on a single 2.4 GHz Pentium 4 (assuming a 10 million digit prime, which would be the minimum to win the prize). This assumes the use of only one core, but you'd need at least 100 cores to make it anything resembling "quick" (~7 hours), if you could even parallelize the procedure that much.
Never mind the fact that only about one in 150,000 exponents will yield a prime, meaning that on average, 150,000 months of computation is required for a single prime to emerge, and furthermore, finding giant Mersenne primes is easier than most other kind of primes. So, I don't think your computer will find these giant primes "pretty damn quick".
Pessimism aside, I think this is a pretty impressive achievement considering that GIMPS doesn't have nearly the power of larger efforts like Folding@Home (GIMPS has around 500 GFLOPS while F@H has around 3372 TFLOPS, or 3372000 GFLOPS).
Mersenne primes would not make very good encryption keys, because they're not very secret. :)
Yes, half of it.
If you were to find a 10,000,000 digit prime today the above rules imply that $3,333 would go to Michael Cameron, discoverer of the 39th known Mersenne prime, $3,333 would go to Michael Shafer, discoverer of the 40th known Mersenne prime, $3,333 would go to Josh Findley, discoverer of the 41st known Mersenne prime, $3,333 would go to Dr. Martin Nowak, discoverer of the 42nd known Mersenne prime, $6,667 would go to Curtis Cooper and Steven Boone the discoverers of the 43rd and 44th known Mersenne prime, $5,000 would go to GIMPS, $25,000 would go to charity, and $50,000 would go to you.
This is great news, I've been crunching Mersenne numbers myself and it's nice to finally see a potential >10M digit one.
You're complaining?
I studied psychology!
:(
Yeah... the 31 MB figure is for an arbitrary 10 million digit number.
Those bastards! Now I have to change my luggage combination again.
Well, there's spam egg sausage and spam, that's not got much spam in it.
Aaah yes, the xkcd that made me stop reading xkcd.
As a chemist, i felt a bit upset at the elitist attitude of the comic, and no I do not think that biology is 'merely' applied chemistry, and therefore somehow less 'pure'.
Cry me a river, impure professional.
Mersenne primes are almost completely useless. I used one to win a programming contest in college involving finding the largest prime number though. Unfortunately the moderator posted my number without the last digit and everybody complained it was divisible by 2.
Thankfully the comic didn't imply a sense of humor.
You stopepd reading a comic because it made fun of you? I'd hate to live in that sad boring dreary life of yours, Monday, Wendsday and Friday that comic makes fun of me and I love it for it.
If you can't laugh at yourself then you have no right to laugh at anyone else.
I may agree with what you say, but I will defend to the death your right to face the consequences of saying it.
Right, but at least there's a chance. With most distributed computing there's absolutely nothing in it for the individual user.
beyond the exeptions of the first few primes (and whether or not 1 is a prime(pssst... its not)) you CANNOT have an even prime becuase all even numbers are divisible by 2 and therefore not prime.
I may agree with what you say, but I will defend to the death your right to face the consequences of saying it.
I know a 100 Billion+ digit prime number....figured it out in my sleep about 10 years ago. But it would take me like 6 years speed writing 24/7 to write it out....not to mention the 500,000 trees it would take to make all the paper.
That's ridiculous. Being useless is not what makes math beautiful. There are plenty of useless things that aren't beautiful.
A lot of them post here.
echo -e 'global _start\n _start:\n mov eax, 2\n int 80h\n jmp _start' > a.asm; nasm a.asm -f elf; ld a.o -o a;
Becuase it is there and becuase we can. why bother to do anything at all? In a hundred years nobody will care or remember you for anything you have done at all during your lifetime, perhaps you should just go crawl back into bed and stay there for the rest of your life? You will have the exact same impact on the rest of the universe that you would have otherwise. While your doing that the rest of us will 'waste' out time discovering the universe around us, it may not server any purpose but we choose to do it and we feel better for it.
I may agree with what you say, but I will defend to the death your right to face the consequences of saying it.
It shall lead the autobots into battle against the evil Decepticons!
If you can read this, I forgot to post anonymously.
I for one am glad that the EFF isn't using my donations for this award, beautiful mathematics or not. When I donate my hard-earned money to the EFF, I expect them to use it for something worthwhile. From TFA:
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.
Ah, arrogance and stupidity, all in the same package. How efficient of you. -- Londo Mollari
To what use will this long, long prime be put?
So we can watch the stars go out,... one by one.
(the 9 billion names of god)
If telephones are outlawed, then only outlaws will have telephones.
Prime numbers routinely prove to be useful.
I, for one, will be using it for my hashtables, thank you very much.
If you can read this, I forgot to post anonymously.
My favorite incarnation of that joke has the mathematician saying "THERE IS A SOLUTION!"
:)
It's amazing to me that it's possible to know that there is a solution, but not know what it is. Kudos, math people
Life is rarely fair. Cherish the moments when there is a right answer.
Close, but she's only pretty useless.
If you can read this, I forgot to post anonymously.
Hey, at least it wasn't computational linguistics.
Dude, it's a joke :( Laugh? Do you really think xkcd is 'elitist?' If anything, the comic is satirizing the ostensible 'elitism' of mathematicians.
Limina.Log
Maybe /. can take up a collection for the $31,071.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
I was looking for a good replacement password that would be easily memorized.
Accept any challenge, No matter the odds.
or sorting pr0n. Now that's important!
But are the bits analog(ue) or digital(e)? There is a tradeoff between accuracy and flexibility and freedom.
John_Chalisque
Can I get that in Roman Numerals pls?
Don't be apathetic. Procrastinate!
Mathematicians generally have a sense of humor about their field, which is the real point of that particular strip. It may be exceedingly dry, but at least it's there. Seeing an elitist attitude there is foolish: Mr. Munroe has a physics degree. Failing to acknowledge humor just because you happen to be a character in the joke is also foolish: Mr. Munroe most likely doesn't know you and most definitely was writing humor, not hate speech.
I didn't see your response, so I wrote my own instead of moderating yours like I should have. If anything, laughing at yourself should be easiest of all since you are more likely to get the joke given an intimate knowledge of its subject matter. =)
Yeah they even can provide complicated proof that there's a solution, while being unable to provide one.
:)
Consultants on the other hand can provide expensive proof that there are solutions, while being unable to provide one.
Not if he dies in the fire. The whole "I have found a solution but there isn't enough room in the margins to write it" only flies once.
Learning HOW to think is more important than learning WHAT to think.
"Physics is like sex. Sure, it may give some practical results, but that's not why we do it." - Richard Feynman
Which is why Richard Feynman is known as the father of quantum mechanics.
And of course, you can write a custom compression program that can store that specific number in 1 bit.
You wouldn't really be compressing then. More info
No, he did it right. 33 million bits ~ 4 million bytes.
I can't figure out if this is a troll of if you just don't realize the magnitude of the problem, it's not something that the computer in your mom's basement can just churn out!
Oh, why not make a threaded app that makes 9.8 million threads and test all the numbers at once? ROFL
And the mod that thought this was insightful? Can I have some of that stuff you're smoking?
Very Wrong
Large prime numbers are used in cryptography because it gives you massive amounts of digits that are not divisible by any other number. There's types of crypto that use multiple large prime numbers to build the keys from. If you use one of these as your seeds it will take a long time to crack anything encrypted as the number is huge and has no smaller factors. At 10 million digits you're going to take a long time to "guess" what it is.
Another fun relationship is between Mersenne Primes and Perfect Numbers, numbers whose factors add up to themselves.
If 2^n-1 is prime, (2^n-1)(2^(n-1)) is perfect (and has a distinctive pattern of digits in binary, to boot...). The proof in this direction is easy. Proving that all even perfect numbers are of this form is a little harder, but doable.
The hard one is proving whether or not there are any odd perfect numbers, and, if so, what form they might take. Nobody has done this yet.
...laura
>if you could even parallelize the procedure that much
You can't. Multiple cores are of no help in speeding up a prime number search like GIMPS. Each iteration of the test requires the results of the previous iteration. All multiple cores do is allow you to run multiple copies of the software (one per core) in order to allow a machine to test more than one prospective prime at a time.
FWIW, I run two copies of the GIMPS software on an E8400 processor, one copy on each core. And last time I did a benchmarking check on it, its currently taking 26 days and a few hours to fully test exponents in the 42,000,000 range.
I want a new quote. One that won't spill. One that don't cost too much. Or come in a pill.
that will essentially map all the primes to n? akin to f(n)=prime number?
So what you mean is: other than 2, no even numbers are primes. I dunno about you but I wouldn't call just one number "the first few" ;)
It's yet another exotic butterfly, even rarer than the last and as a display of the state of brute force computation.
Algorithmic and distributed computing development will benefit from these kinds of "useless pastimes".
Mathematician #1: How are we going to find the 46th Prime?
Mathematician #2: Bring out the GIMPS.
Mathematician #1: The GIMPS is sleeping.
Mathematician #2: I guess you're going to have to wake him up then.
The manifest absurdity of it is too obvious to require explanation
My favorite incarnation of that joke has the mathematician saying "THERE IS A SOLUTION!"
Try: "A solution exists." For the punchline to work best, use the math lingo as it would be used in a real proof. Also, since he was a theoretical mathematician, he didn't do "a lot of complicated math", he "looked at the fire, looked at the bucket of water [*1], concluded that 'a solution exists', and went back to sleep".
It's amazing to me that it's possible to know that there is a solution, but not know what it is. Kudos, math people :)
Heh -- when you put it that way, it does seem kinda weird, but it's really not that hard to explain how it works: the key is that the task of figuring out whether or not a solution exists for one problem can itself be taken as an entirely different problem, so if you just solve that one instead of the original one, there you are. And those "meta-problems" tend to be both much easier in terms of actual computation required and much more "interesting" [*2] in terms of conceptual effort required, which is why mathematicians prefer to focus on them. And yes, it works recursively (figuring out whether or not it's possible to determine whether or not a solution exists for a particular problem, and so on...)
[1] one of which, the GP forgot to mention, was conveniently in each room
[2] in math lingo, i.e., "harder" in normal terms
David Gould
main(i){putchar(340056100>>(i-1)*5&31|!!(i<6)<< 6)&&main(++i);}
No I wasn't trolling, but apparently quite a few people didn't catch the intended 'relatively' in the post. 7 of my 8 cores are running pretty near idle most of the day (or night I should say; I actually use that horsepower during the day), so if prime95 or whatever is threaded I'd have an advantage over most systems, but it's still obviously no supercomputer. Yes, I'm perfectly aware that it'd still take days or weeks to crunch numbers that large, giving me approximately a 1/0 chance of hitting the jackpot.
I'm still trying to figure out what the hell makes a huge prime number worth $100k, though. And indeed, how I was modded insightful - I posed a question and told a really lousy joke that nobody got.
How are sites slashdotted when nobody reads TFAs?
Put another way, mathematics is to physics, as masturbation is to sex.
I hate printers.
Great idea! I love how you've obviously thought about how to prevent such a system being abused or gamed.
Oh wait, no you haven't.
I hate printers.
Failing to acknowledge humor just because you happen to be a character in the joke is also foolish
I'm really curious as to how far that extends, in your opinion. Should a woman be offended when someone tells jokes about them? Blondes? Black people? Men? Irish? Gays? Handicapped?
Yay for sensitive people (not you). Pretty soon there won't be anything left to joke about.
"So long and thanks for all the fish."
A nonconstructive proof that P = NP would be very interesting, and also very annoying (since the actual algorithm might be hideously complex).
At 10 million digits you're going to take a long time to "guess" what it is.
If there is only one known prime number with 10 million digits, then I reckon I could guess this one quite quickly.
U1NCaVpYUWdlVzkxSUhkcGMyZ2dlVzkx SUdoaFpHNG5kQ0JpYjNSb1pYSmxaQT09
No, that would be Max Planck.
That's not Picasso, that's Kandinsky!
I heard that after this strip a lot of people also stopped reading. Not because they were offended, but because they then spent all their time discussing the socio-political implications of it.
Cryptography
why would you need the extra byte for context? without it you could represent any Mersenne prime up to one with 4294967295 digits with ease.
Must.... resist... mother joke...
Not when they are this big. It'd be too hard to work with and there are too few known primes this large for it to be secure.
That's exactly what this project is doing, and it took them years to find it. So no, it wouldn't be quicker.
I couldn't even guess how many bits you would require for a number that large
For 10 million decimal digits, it would be 10000000*log10/log2 = 33219281 or about 4 GB.
That seems like a really bad idea. You're trying to encode something, presumably to keep it secret, given "secret" information that was given to you by somebody else.
After reading that strip, I went to the wikipedia article on Deconstructionism, read it, and then still had no idea what Deconstructionism was. I'm pretty sure it doesn't actually mean anything.
Actually, if you have a possibly prime number N, you don't need to divide by every number from 1 to N to check whether it's prime.
A simple test is to test every odd from 1 to the square root of N. If 2 doesn't divide evenly into the number, then no other even number will. Also, if something can cleanly be factored out, it's not prime.
Wikipedia also suggests storing a list of primes to test first--If N can divide by any of those primes it is composite.
There are much better algorithms out there, but those are a few easy ways to speed up a primality test.
Yeah they even can provide complicated proof that there's a solution, while being unable to provide one.
Yeah, there's some really weird stuff like that. I just finished the Maths Tripos at Cambridge (UK) and in a Logic supervision I was discussing the theory of proofs and the fact that you can show something is provable but without actually finding a proof (mad, I know). I asked whether this really mattered because if you know there's a proof of something you know it must be true, and my supervisor gave me a very interesting example:
Colouring graphs on orientable surfaces of genus n is something that is quite interesting. (Think colouring a map, painted on a doughnut with n holes, with the fewest colours necessary). We know that there is a way to construct a fast (polynomial time) algorithm which colours such a graph in the least possible number of colours. However, because we haven't found a constructive proof, we have no idea how to find these algorithms! Frustrating, eh?
If i so deem to put that specific number in my dictionary with an index of one bit with value 1 .. that's my own choice. Obviously, that means only two different numbers cant be represented with one bit, and some of the rest may have far less compression than their ascii equivalent. But it would still be a valid number compression program none the less.
No, sorry. You're missing the point. You'll have a compressed file of one bit (byte, if we're nitpicking)... along with a 4mb executable for the decompressor. One is useless without the other, hence, you have efectively failed to compress the original data - to be able to recover it, you need both. This is why all compression challenges require both the compressed data and the decompressor software combined to be smaller than the original data.
Now, to simplyfy it, Komolgorov's complexity defines minimum number of bits into which a string can be compressed without losing information - basically how small a program (running on a Turing machine) can be which outputs the original string. This minimum compressed length is easy (yet very slow) to find out. Read the link, is interesting stuff.
..Can I have it back please, then.
Quantum Physics has many fathers. Classical physics is a bit of a slut.
It's been a long time.
How many digits-per-minute can you type?
You know, there is a difference between trolling and pointing out the flaws in your reasoning. Just saying.
what you haven't realized is that she's blinking a prime number of times!
Any science news is good news, IMHO. But I do have to wonder what's going to come out of this discovery? Is the cure for cancer going to be found based on solving all the prime numbers out to like a gadzillion digits? Personally, I'd rather put my computers to more useful things -- like finding more drugs,... :-)
You don't want my opinion on this, because I'm absolutist about it. If you can ignore that a joke is offensive and come to the conclusion that it is also funny, then you shouldn't be offended by it no matter how offensive it was to begin with. I of course understand that most people draw the line somewhere else. :P
See, this is what happens when psychologists try to be funny. There's always someone who finds it insightful.
This minimum compressed length is easy (yet very slow) to find out.
Er... You'd better get that paper published and claim your prize for solving the halting problem! Oh wait...
The Kolmogorov complexity of a string s is uncomputable.
SIGSEGV caught, terminating
wait... not that kind of sig.
Er... You'd better get that paper published and claim your prize for solving the halting problem!
Touché. Given a string of lenght "l", i thought you could try all programs of the same lenght (or less) until you get the desired output. Oh well... :)
I do not think that biology is 'merely' applied chemistry, and therefore somehow less 'pure'.
Not yet anyway. But we're getting there, and maybe some day we understand biology well enough that it can be reduced to just applied chemistry... At that point biology will be as pure as chemistry, because it will be same as chemistry.
And one day we can perhaps make any arbitary universe just based on the maths of it. At that point everything will be as pure as maths, because everything will be maths (from scientific point of view).
(No, I'm not entirely serious with above, just letting my mind wander with fingers on keyboard.)
So you just take the first 1024 bits or so. I'm sure it'll be good enough...
Oh yeah! I guess that without the *blinks* in "*blink* It's *blink* not a *blink* gim*blink*mick! *blink* *blink*" I missed it.
Try not to take me more seriously than I take myself.
You could store it as "2^n-1", does that count as a programmatic representation?
// MD_Update(&m,buf,j);
Wouldn't big M-primes be useful in crypto? Given that the EFF cares a great deal about privacy, one could see how they might consider it worthwhile.
When it comes to cryptography, when youbigger the prime numbers you have the harder it is to break the encryption.
That's "embiggen".
not quite so useful this high up. Pick medium size 10-20000digit primes and you'll be safe. 10million digits is just a waste of processing power.
I search for incredibly large primes with the lights out, i feel it sets the mood.
Large prime numbers are used in cryptography
...which has nothing to do with finding Mersenne Primes.
Advice: on VPS providers
Yeah, I saw the subthread below after I posted. Thanks for actually explaining instead of flaming, though. Not all of us are cryptomaniacs. :)
Perhaps you could use a number-theoretic fft (using modular arithmetic instead of fp arithmetic) on a gpu to avoid the errors accumulation. Although old gpus only processed single precision fp, new gpus can process 24-bit integer multiplication at full speed as well (at least for nvidia's cuda). You probably gain a little bit of accuracy using NTTs vs single precision FP FFTs (where you probabaly need a few guard bits to avoid subtraction errors) which is likely an exponental speedup with these types of algorithms.
Of course the double precision arithmetic is only somewhat slower than single precision on GPUs, but consumes twice the register space (so on actual algorithms, it runs quite a bit slower because of this). Right now, GPU ffts are quite a bit faster than CPU ffts, but not yet 10x (unless you have a very large GPU and a fairly ordinary CPU) if you copy the data back to the CPU every time after an fft, but if you leave the data in the GPU and code the rest of the digit-convolution algorithm on the GPU, I'll bet it isn't that far off of 10x on average.
You're talking information theory, he's talking simple math. Yes, you could represent it as (2^n)-1, and so represent it as 2^32,582,657-1, which can be represented in 8-bit ascii by around 15 bytes; but the actual binary representation of the number you'd get if you ran
(x = 0; x < 32582657; x++){System.out.print(1);}
and got that
111 [....] 111
would be roughly 33 megabits.
For Brian Recall: if you remember that 10^3 = 1000 and 2^10 = 1024, you can just multiple the base-10 log of the number by 10/3 and get a *very rough* estimate of the binary log of the number; Timothy Brownawell's 3.3219 is a more precise figure for the ratio that my 10/3 represents. The binary log is equal to the number of bits in the number.
Anyway, it's around 10^9,808,358, and is exactly 2^32,582,657-1, so it's exactly 4072833 MB (32,582,656 is divisible by 8 but 32,582,657 is not)
We already have an algorithm that solves NP problems in P time, but only if P = NP.
http://en.wikipedia.org/wiki/P_%3D_NP#Polynomial-time_algorithms
Correction: the prime I used is the 44th, which is a known prime, not the new possible 45th, which is not given in the article.
Do we at least know who the mother is??
Of Code And Men
So, mathematics is done in all-night sessions alone in your mom's basement while staring and shapely Riemann sums and Physics is done in the real world while drinking a beer and when you get the final product, you'll have no idea how you did it.
He who can laugh at himself becomes invincible to insult.
You can write the 44th prime out as (2^32582657)-1. I don't think this 45th is much longer. That's 98 bits in 7-bit ascii.
-- Don't believe everything you read, hear or think
Luckily you can easily see if the number is divisible by 2, 3 or 5[*] so you can start checking at 7 and work up to the square root of the number you're searching. You'll find that much faster.
* with 2 or 5 you can look at the last digit. with 3 you add all the digits together and see if they're divisible by 3.
-- Don't believe everything you read, hear or think
So, if there is a 10 million digit figure that exists as a prime number, but it's too long to write out such that we can see or behold it tangibly, do we really know if it exists?
52 52'23" W 47 32'07" N
Large prime numbers, yes. Large prime number tables, no. Or rather not primes, usually pseudoprimes which are *probably* primes but not 100% certain. For practical purposes you take some pseudoprime tests, throw out any that fail and a few other "weak" cases and use those. In practise it doesn't matter because the rarity and difficulty of identifying pseudoprimes (if we could, we'd use it to exclude them...) means it makes little practical difference.
Live today, because you never know what tomorrow brings
I am impressed. I'm a mixed race and, because of this, people have often said racial jokes in front of me. For LULZ I usually tell them I'm the race in the subject of the joke (I usually really am but I look Asian but can pass for any race) and then I counter with my own joke concerning either their race or my own. If you can't laugh and can't recognize humor (humor != hurtful speech always) then I think your life is broken. Then again, somethings just aren't funny.
"So long and thanks for all the fish."
EFF hopes to spur the technology of cooperative networking and encourage Internet users worldwide to join together in solving scientific problems involving massive computation.
10 million digits would be more than 31 MB.
You read the wrong post that he was replying to.
There's a similar project out there called "Seventeen or Bust" whose goal is to find primes that will eventually prove a conjecture. To date they have eliminated 11 of the 17, leaving only 6 candidates left. I prefer to donate my cycles to them since there's bound to be a big party when the last candidate is eliminated and the goal is completed.
"Follow me" the wise man said, but he walked behind.
I don't think you give GIMPS enough credit..
according to primenet:
Mersenne PrimeNet Server 4.0 (Build 4.0.101)
Status Summary Report 28 Aug 2008 17:00 (28 Aug 2008 10:00 Pacific)
This report is updated every 60 minutes
All dates and times are Coordinated Universal Time (UTC)
Assignment overdue check-in is set at 60.0 days (0.0 days to expire)
Aggregate CPU Statistics, P90 Units
Last 7 Days Average Cumulative Today
from 22 Aug 2008 06h from 28 Aug 2008 06h
Test Type CPU yr/day GFLOP/s CPU years CPU yr/day GFLOP/s
Lucas-Lehmer 2326.526 28006.020 1166.073 2549.438 30689.375
Factoring 70.066 843.432 33.633 73.534 885.185
TOTALS 2396.592 28849.451 1199.706 2622.973 31574.561
That looks like they are sustaining roughly 30 TFLOPS
That may not be 3372 TFLOPS, but that beats the pants off 500 GFLOPS
You just made him stop reading slashdot...
dividing that number by every number from 1 to the number of the same length to make sure it is only evenly divisible by itself, and 1.
To be just a little bit picky... You can skip all of the even numbers, so really its only half as bad as you make it out to be ;)
Umm... 2? 5? 11? (10, 101, and 1011 respectively)
But basically, the project is more or less doing that, actually using a subset of numbers where the exponent is a known prime. Those numbers were chosen particularly because they're easy to test. That being said, it still takes an average desktop about a month of constant computation to determine if a number that size is prime or not. So anything you can do to narrow down your search is a good thing.
...when he thought all he was doing was fucking around!
At 10 million digits you're going to take a long time to "guess" what it is.
If there is only one known prime number with 10 million digits, then I reckon I could guess this one quite quickly.
Shhhh!Don't tell him!! I'm having fun reading his "encrypted e-mail".
"There are four boxes to be used in defense of liberty: soap, ballot, jury, and ammo. Please use in that order." -Ed H
May I suggest you spend some of your time learning how to type typoless ?
I'm not a coward by any name.
details here: http://mersenne.org/prize.htm
Free unix account: freeshell.org
That constant will kill you, though.
I'm a fan of the version that includes a computer scientist. After all of this with the engineer, the physicist and the mathematician, the computer scientist sets his room on fire, thereby reducing the problem to another one with a known solution.
lol only on /. can you get flamed for not understanding crypto fully.
Well, physics is basically an extension of mathematics...
Help us build a better map!
Well, once you take any sort of altruism out of the picture, then yeah, nothing.
http://v5www.mersenne.org/ is where I got my info; clearly we have a slight disconnect between that and http://mersenne.org/primenet/. Thanks for the heads-up.
My new RSA public key is this number times 3.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
Yeah, if it was I'd be bagging that 100k right about now.
// MD_Update(&m,buf,j);
You're right! That's a pretty drastic difference in numbers.. it makes you wonder which stats are right.
I'm inclined to believe the results you posted, since there's a news post which suggests that by 2006, the computational speed was 20 TFLOPS: http://mersenne.org/ips/stats.html
It is, though, still two orders of magnitude smaller than Folding@Home.