I went to this university and took several of Professor Cooper's classes. He was a great guy and he seemed really passionate about his Mersenne project.
One thing that was annoying however was the prime finding software was put on every lab computer possible. It was suppose to pause when a user got on a machine and resume when they got off. This seemed to never be the case though because they would all run terribly slow and when you checked the process list the prime software would be pegging the CPU. After reporting the problem several times I simply added a line in my bash file to kill it when I logged on.
> A computer network administrator faces multiple felony charges and years in a Georgia prison for allegedly installing Distributed.net clients without permission. Prosecutors say its justice, others aren't so sure
> A college computer technician who offered his school's unused computer processing power for an encryption research project will be tried next month in Georgia for computer theft and trespassing charges that carry a potential total of 120 years in jail.
> The closely-watched case if one of the first in which state prosecutors have lodged felony charges for allegedly downloading third-party software without permission.
What a lot of people missed was the significantly raised electricity bills from having 500 PCs running this software all day.
He faced a theoretical 120 years in jail. Even though that was unlikely he settled because, from the EFF statement:
> "David never should have been prosecuted in the first place, but we're glad that the state decided to stop," said Senior Staff Attorney Lee Tien of the Electronic Frontier Foundation (EFF). "This is a very good result for David. He very likely could have won if the case had gone to trial, but trials cost money and you never know what will happen."
And this is what he got for settling:
> Under the terms of the deal, announced today, McOwen will receive one year of probation for each criminal count, to run concurrently, make restitution of $2100, and perform 80 hours of community service unrelated to computers or technology. McOwen will have no felony or misdemeanor record under Georgia's First Offender Act.
That's sounds familiar. I went to a university where the one professor that was using Linux (and his knowledge was very little) was constantly tying up the Linux machines in our labs to run his prime number generation tool.
His research was into finding a faster/easier way to do prime number factorization in an attempt to speed up cryptography of any kind that uses it. Part of that was finding an easier/faster way to compute prime numbers in the first place. It was fascinating stuff ... but those machines were useless for anything but doing those calculations since it was using up all cores/HT's.
My university's physics department did the same thing with SETI@home. The SETI@home guys were smart enough to make their program run as a screen-saver that displayed Fourier Transforms so people thought it made the lab look more sciency and left it on.
Another important note is that SETI@home actually did stop running when you were using the PC. If you left Task Manager up, you could see the difference on the CPU usage graph.
What OS was this? Processes like these (Folding, Seti, etc) should be "niced" on *nix-like OSes to have the lowest possible priority. Not sure what this looks like on Windows, but I imagine it's possible.
In windows, each process has one of 6 priority levels, and each thread has one of 7 priority levels. The combination is looked up in a table and yields one of 22 values between 1 and 31. http://msdn.microsoft.com/en-us/library/windows/desktop/ms68... You can manually change priority levels by right-clicking a process in the Task Manager. Not sure how to do it automatically or on a command line.
nice doesn't help with I/O pressure or memory contention, particularly if it used enough memory to contribute to swap activity. Even something like pressure on the system L2/L3 caches can be a big deal, particularly on older systems where those were less generous.
Agreed, although I would note that at least on Linux and FreeBSD those haven't been a realistic option for a terribly long period of time – if the user didn't go to school recently, it's likely that they weren't an option.
(also, not sure about cgroups but ionice did absolutely nothing useful with swap churn when I tested it awhile back)
In my freshman year of college, I discovered something neat about perfect numbers and Mersenne primes (verified by my math professor):
The first perfect number, 6, written in binary is 110
The second, 28, in binary is 11100
The third, 496, in binary is 1111100
The fourth, 8128, in binary is 1111111000000
See the pattern? Its a number of ones equal to the mersenne prime that generates the perfect number, followed by one less number of zeroes.
Just an interesting tidbit I discovered completely by accident in college that I always thought was cool. :)
Of course it derives directly from the fact that mersenne primes (and perfect numbers) are based on powers of two, but I still thought it was cool (probably because I discovered it accidentally and independently without trying to)
This is in fact the consequence of a fact first proven by Euler: every even perfect number is of the form (2^(p-1)) * (2^p - 1) where 2^p - 1 is a prime. That is, it's p ones shifted left by p-1 zeroes.
Good for GIMPS, 2⁵⁷⁸⁸⁵¹⁶¹ - 1 has a nice ring to it! GIMPS is one of the largest distributed computations in the world and have been tooling away finding primes since 1996. SETI@Home gets most of the credit for popularizing this kind of distributed computing, but GIMPS has been at it for even longer and has delivered consistent results.
What? Don't be silly. If they delivered no results or "nothing" at all, the project would have been shut down years ago. SETI has consisently reported that they have searched through a very large amount of signal and found only natural noise. That data is extremely valuable and is absolutely not "nothing".
It doesn't have to be encrypted, just some basic compression algorithm eliminate patterns and make it very difficult to distinguish from noise. Being efficient achieves the same result as being sneaky
If you want to run some distributed computing but don't like SETI@Home, give worldcommunitygrid.org a look. They run a number of projects aimed at curing stubborn diseases and working on clean energy and water. As a bonus, if you use it as your screensaver, the graphics for many of the projects are pretty cool.
So what's the application of finding these sorts of primes? (I don't mean to sound like a dick or anything, I'm genuinely curious what this kind of knowledge can help us with).
Honestly, this is pretty much a "because we can" thing, other sibling replies to the contrary. It is cool and fun, and the resources dedicated to this are a pittance compared to, oh, say, the amount of computational resources applied to playing pretty 3D games.
I think that the resources required deserve to be considered. If these computers are running 24 hours per day, and they require an extra 100 watts to look for primes (over their idle power consumption), then each computer is using the equivalent of 10 kg of coal per month.
In some cases, they're using renewable energy, and in some cases, they're offsetting heating costs. But the important thing is that the people installing the distributed computing software are not the people looking at the electricity bill. And that kind of breaks the whole economics of it.
Yes, but large numbers tend to just blow people's minds. Compare it to, say, power lossage due to people leaving their light bulbs on too long, or using incandescent bulbs instead of something more efficient.
Not Mersenne primes though. There are only a few of them, and it would be trivial to check if any of them are used as primes. The whole point of encryption schemes that use prime numbers is that the attacker doesn't know which primes are used.
While Mersenne primes make breaking discrete logs easier over prime fields, they're pretty OK to use as underlying field on elliptic curve groups (cf. p521).
And such encryption relies on the primes that are used remaining secret.
Using any of the 'well known' primes would be a bad idea as it is easy to go through the 'well known' primes and test to see if they were used as a basis for the encryption.
This part confuses me: "a 32-core server in 6 days" and "i7 CPU in 4.5 days" to do the same verification? Is the MLucas code really that much slower than GIMPS, or did the verification only use one core on the 32-core machine or what?
It's a myriad of answers. The Mlucas run used a larger FFT than was necessary, partly due to multithreading reasons. The Mlucas code also only uses SSE2 instructions, where the overclocked i7-2600K using GIMPS' Prime95 program is fully AVX capable. I would also expect that the i7 runs at a higher frequency, with a higher IPC, than the server. The "main" CUDALucas run took around 90 hours on a GTX 580. We didn't even hear about the 560 Ti run by Gilchrist, that was on the side.
One last clarification: the reason to use Mlucas, and not Prime95 since it's so much faster, is for independent-code verification of the prime. (CUDALucas also counts in that regard, but the more independent triple and quadruple checks, the merrier!)
Each of these verifications would have been using different code and algorithms, otherwise it's not really verification. So different speeds are entirely expected.
Yes it seems very odd, especially as they also mention CUDALucas running in 3.7 and 7.7 days on two different NVidia GPUs (one a 560, the other one unnamed — maybe a Fermi board?)
I have the 560 Ti mentioned in the article. It's a mid-to-high grade card, better than most $200 cards IMHO but if you're willing to spend the cash, it's not at all difficult to find a card with more horsepower. Dropping a cool kilodollar will net you a GTX 690 which seems to be the right relative speed. http://www.hwcompare.com/12683/geforce-gtx-560-ti-vs-geforce...
Sounds like 2 AMD Opteron 6200 Interlagos chips as found on many clusters. Each has 16 cores, but they have only 8 floating point units and a smaller clock then their Intel counterparts.
For some codes each core gives 60% of an Intel core for many others it is 40%.
The Bulldozers and the Interlogos go down in my mind as the chip that destroyed the AMD. It late, was hard to use, and underperformed.
It's definitely just a standard lots-of-bits. Every bit of information is needed, lose one and the whole test will be wrong. For current wavefront exponents, like 2^60,000,000-1, save files are around 8 MB, or ~60M bits -- exactly what you'd expect.
Also Prime95 doesn't use GMP, its code is all hand-coded assembly, optimized specifically for the LL test and x86 architecture, written by one very dedicated George Woltman.
Just imagine if we didn't have computers how many fewer primes would have been found.
Even with computers I started wondering how they even go about testing these. I know there are multiple algorithms etc for verification. I meant in the sense of how to keep everything in memory and doing computations on it (I assume that numbers these large aren't trivial to work with).
The number's representation in binary can fit in RAM comfortably -- it's "only" 3 million bits or so. From there, the goal is to perform the Lucas-Lehmer test in as few operations as possible:
I first wondered they wouldn't just multiply all the prime numbers up to this new prime and then subtract one from it to get an even bigger prime number.
But then I realized that they're not searching for them in sequence. I guess it's a very sparse table of primes once you get up there in the magnitudes.
It will not necessarily be a larger prime. But it will always be divisible by a larger prime. See
http://en.wikipedia.org/wiki/Euclids_theorem
(Though not necessarily the next largest prime).
The problem with this approach is that the product of the first n primes grows exponentially as the number of primes increases.
The absurd amount of time that takes just to verify the thing, shows how much we have yet to improve our computing power to be able to do more and more precise and groundbreaking science.
The argument can be made that, because there are an infinity of primes, then either (a) Mersenne primes are also infinite, or (b) a very strange effect prevents Mersenne primes above a certain size, while allowing an infinity of ordinary primes. Occam's razor suggests it's (a).
Edit: Less snarkily, the integers are mysterious and not at all well understood and chock-full of effects like the one you mentioned. It's fallacious to simply argue that because there are infinitely many primes, there must also be infinitely many primes of a given type.
In general, it does. The count of odd numbers in a set of integers. The count of integer square roots derived from a set of integers. And so forth. None of these can be used to argue that Mersenne primes have a fixed non-terminating relationship with their generating function as number size increases, but the reverse assertion cannot be categorically denied either, which is why work in this problem continues.
> It's fallacious to simply argue that because there are infinitely many primes, there must also be infinitely many primes of a given type.
Yes, therefore it's a good thing I didn't do that.
I used Occam's razor on the basis that, because Mersenne primes continue to appear as number size increases, it's more likely that this trend will continue than to imagine a reason why it wouldn't.
The tl;dr: a continuation of the Mersenne prime series is more likely than its abrupt end, so Occam's razor (only ever an assumption) is applicable.
Occam's razor in its simplest form and applied to math is something like this:
Proof 1: assumptions (i), (ii) imply that there are infinitely many Mersenne primes.
Proof 2: assumptions (i), (ii), (iii) imply that there are infinitely many Mersenne primes.
Both make the same "predictions", which in math it means they prove the "same" theorem. Then we choose Proof 1, because its assumptions are simpler. That's all.
Occam's razor doesn't apply when we are choosing between different theories that lead to different predictions.
Of course one can always conjecture that there are infinitely many Mersenne primes based on "intuition", and then go on to prove other results which rely on that assumption. People do that for P=?NP, for instance. But there's no point in invoking Occam's razor for that.
> Occam's razor doesn't apply when we are choosing between different theories that lead to different predictions.
Of course it does. If there are two or more possible outcomes, and one of them has a higher likelihood or represents a simpler solution, it's favored by the thinking behind Occam's razor. This can't be used to prove anything and it's only conjecture, but it's useful for sorting out questions that involve imperfect information.
When Andrew Wiles set out to prove Fermat's Last Theorem, the assumption was that it was true -- that there were no integer solutions for a^n + b^n = c^n with n > 2. The reason for the assumption? Occam's razor. And that assumption, like this one, didn't go anywhere to deciding whether it was true or not. It just seemed likely.
The argument can be made that, because there are an infinity of primes, then either (a) even primes are also infinite, or (b) a very strange effect prevents even primes above a certain size, while allowing an infinity of odd primes. Occam's razor suggests it's (a).
Or, as another poster said: math doesn't work that way.
Not necessarily - proving there are infinite primes is easy. It could be hard or impossible, or it could be easy or moderately hard but either way no one's figured it out yet. (And yes it's sometimes possible to prove that something can't be proved.)
The largest known prime number, 2^(57,885,161)-1, was discovered on January 25th 2013. It has 17,425,170 digits.
The new prime number is a member of a special class of extremely rare prime numbers known as Mersenne primes...
http://tldr.io/tldrs/51111f3dde23f15658000031/48th-known-mer...
One thing that was annoying however was the prime finding software was put on every lab computer possible. It was suppose to pause when a user got on a machine and resume when they got off. This seemed to never be the case though because they would all run terribly slow and when you checked the process list the prime software would be pegging the CPU. After reporting the problem several times I simply added a line in my bash file to kill it when I logged on.