Mersenne primes project

[R.D. Silverman]

Originally Posted by Mathsgirl

I don't think he was being rude, just making a joke! Thank you for all your replies though! absolutely any information is very helpful!

He was definitely NOT joking, based upon many similar responses he has made in the past.

Because I am very blunt, often talk at a high level, and have little patience for cranks and willful ignorance,
"The Mawn" and others like him are
often very quick to reply to my purely technical responses with derogatory personal comments
about what they perceive to be "rudeness". They have a long history of doing this.

He WAS being rude. There was no reason for ANY personal comments.

[TheMawn]

Originally Posted by Mathsgirl

thank you @TheMawn, very, very helpful! and you did well to read between the lines of my unclear question! I just heard that very large primes are very useful in security, so as mersenne primes are easily proved to be prime, large mersenne primes are easier to find??? therefore better in that sense than other primes. I was just wondering about the Lucas-Lehmer test, does it find mersenne primes, or after mersenne primes are found, are they then checked to be prime by the Lucas-Lehmer test? thank you so much for all the help everyone :)

The Lucas-Lehmer test takes a candidate (i.e. We Don't Know if it is Prime or Composite Yet) and at the end of the test, you get an answer that tells you if it is Prime or Composite.

The test runs P - 2 iterations of the following, where the candidate is M_P = 2^P - 1.

You begin with S = 4.

In the next step, you take S² - 2.

Next you divide it by M_P and keep the remainder of that division. This is known as modular arithmetic. For example, 14 mod 5 is the remainder of the division of 14 by 5 which is 4 (14/5 = 2 with remainder 4). It is very fortunate that we are able to take the modulo of M_P in this step, because we repeat the squaring process over and over again (P - 2 times, actually) and the numbers would start to become too big to use. This step keeps the numbers (relatively) small.


Let's try with M₇ = 2⁷ - 1 = 127.

S₀ = 4.

S₁ = (4² - 2) mod 127 = 14 mod 127 = 14.

S₂ = (14² - 2) mod 127 = 194 mod 127 = 67.

S₃ = (67² - 2) mod 127 = 4487 mod 127 = 42.

S₄ = (42² - 2) mod 127 = 1762 mod 127 = 111.

S₅ = (111² - 2) mod 127 = 12319 mod 127 = 0.

If S_P-2 = 0, your number is prime! 127 is in fact a prime number. Notice that S never got larger than 127. That's the point of the modular arithmetic.


A bit faster now, trying M₁₁ = 2047.

S₀ = 4.

S₁ = 14.

S₂ = 194. We're still going up at this point. Last time we had gotten past M, but we're not there yet.

S₃ = 788.

S₄ = 701.

S₅ = 119.

S₆ = 1877.

S₇ = 240.

S₈ = 282.

S₉ = 1736.

Because we didn't arrive to 0 this time, we see that 2047 is NOT prime. In fact, 2047 = 23 * 89. (This is just common knowledge; The LL test tells us NOTHING about what the factors actually are)


Regarding your question about security and cryptography, this is treading into Silverman's area of expertise (EDIT: In the time I took to write this, he has in fact already begun to share). You can start here: http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29

One of the elements of RSA is taking TWO primes p and q and getting n = pq. p and q are kept secret, but n is publicly available.

Using Euler's Totient Function Phi, you get Phi(n) = Phi(p)*Phi(q). The Totient Function gives you the number of integers less than n which share no common factors. It is MUCH easier to find Phi(p) and Phi(q) than to find Phi(n) and that's part of the trick.

Phi(n) is used to create two other numbers, e and d which are like two keys to the lock. e is public; everyone gets to know it. d is private; you keep this one secret. n itself is used in the encryption and decryption process with without e and d, you don't have enough to decrypt the message.

If you could figure out Phi(n) you would be able to quickly find e and d, but Phi(n) is hard to compute without knowing p and q. That's the trick.


If what you say is true and that bigger primes p and q make bigger n's and that makes the system harder to crack, it might seem tempting to go and find the biggest primes you can (Mersennes) but part of the trick is keeping p and q secret. Anyone can find what the Mersenne Primes are. If you know that at least one of the two primes used is a Mersenne, you just have to try them all until you figure out which it is, and then the key is easy for you to crack now.

[Mathsgirl]

@R.D silverman, I am now finding it hard to write anything about these stupid Mersenne primes! give me something they are good for! I have coded an algorithm that finds Mersenne primes up to and including some value n, then I was going to iterate through them and use the LL test to show that they are indeed Mersenne primes. But now I don't even know the point :( this was going to be the layout of my essay
1. briefly explain what a mersenne prime is
2. connection with perfect numbers
3. explain the LL test
4. use the fact that the LL test makes it easier to prove if a number is a Mersenne prime, therefore easier to find larger primes if they are Mersenne, then explain why that is helpful in security. Why are people giving £100,000 for finding the next mersenne prime if they are not helpful? what is the point of the great internet search for mersenne primessssssssssssssssss???

Also, I heard that when we have found primes large enough, then super computers will then be allowed to be sold to the general public as they won't be able to hack into people's security anymore

[Mathsgirl]

@TheMawn, thank you. Ok then, I can obviously not use the fact that mersenne primes are helpful in security anymore, so thank you everyone for helping me avoid that horrible mistake. but what should I write about? why are you guys so interested in Mersenne primes?

[TheMawn]

Some of those interested in mathematics are interested in finding bigger and bigger primes. It was known a very long time ago that they form the sort of "building blocks" for all other numbers, and the original question was whether or not there are infinitely many. When it was discovered that there was in fact no biggest prime number, it was all about finding bigger and bigger primes.


The Prime95 software has some uses for computer hardware. I myself have helped a few people on other forums diagnose their computer issues by helping them use Prime95's stress testing package. As you saw, the process is iterative and because each answer depends on the last, every calculation needs to go perfectly in order to arrive at the right "final" answer. So, what you can do is run a test KNOWING what result you should arrive at, and see if you actually do. If you don't, something is wrong with your computer's hardware.


GIMPS is probably the longest running distributed computing project, and has every reason to be the envy of all other similar projects. There were many lessons learned here that could shape the future of "cloud" computing.


Unfortunately, the study of Mersenne Primes exists in large part for its own sake.

[Mathsgirl]

ok! I ditched doing perfect numbers because they didn't have any real purpose, then chose Mersenne primes ...

Anyway, I guess I will just talk about them and perfect numbers, I don't need to discuss their significance. Thank you for all your help, you have given me lots to write about!

[Puzzle-Peter]

Originally Posted by Mathsgirl

@TheMawn, thank you. Ok then, I can obviously not use the fact that mersenne primes are helpful in security anymore, so thank you everyone for helping me avoid that horrible mistake. but what should I write about? why are you guys so interested in Mersenne primes?

The main reason (I think) for people being interested in Mersenne primes is the fact that the LL test is very fast compared with other test methods. Because of this, the Top 10 largest known primes are all Mersenne primes at the moment. (See http://primes.utm.edu/top20/page.php?id=3 ). So if you're looking for a world record prime, Mersenne is the way to go.

Originally Posted by Mathsgirl

Also, I heard that when we have found primes large enough, then super computers will then be allowed to be sold to the general public as they won't be able to hack into people's security anymore

It wouldn't do any good using the largest known primes for cryptography. It's too slow and they are rare & widely known, so you can go and try all of them instead of trying to factorize. As R.D. Silverman pointed out, finding sufficiently large primes for secure encryption is a matter of no time at all. Even bigger primes do not have any practical value I am aware of.

The main reason I do not own a supercomputer is money for the machine itself, for the building to keep it in and for the electricity bill. I am not aware of not being allowed to buy one but I am quite sure of being unable

EDIT: It took me long enough to write this so it's rather obsolete now LOL

[Mathsgirl]

Not at all! I think it would be a good idea for me to write about how the largest primes are Mersenne primes. I don't who told me about primes and super computers, but obviously they were talking a load of rubbish.

[paulunderwood]

Here is an intesting page on Mersenne primes:

http://primes.utm.edu/mersenne/index.html

[TheMawn]

Well, prime numbers themselves have their importance. Mersennes are just a special case.

[R.D. Silverman]

Originally Posted by Mathsgirl

@R.D silverman, I am now finding it hard to write anything about these stupid Mersenne primes! give me something they are good for! I have coded an algorithm that finds Mersenne primes up to and including some value n, then I was going to iterate through them and use the LL test to show that they are indeed Mersenne primes. But now I don't even know the point :( this was going to be the layout of my essay
1. briefly explain what a mersenne prime is
2. connection with perfect numbers
3. explain the LL test
4. use the fact that the LL test makes it easier to prove if a number is a Mersenne prime, therefore easier to find larger primes if they are Mersenne, then explain why that is helpful in security.

This is all very fine except for the fact that they really are not helpful in security.

Interest in Mersenne primes arises because of their connection to the LL test. It is the fastest
known test (and there are some reasons for believing it is the fastest any test can be) for finding primes.

People chase new Mersenne primes almost solely as a hobby; to set records. The LL test also has
a limited use as code to test computer hardware: it pushes computational limits so can be used as
stress tests for CPUs.

Why are people giving £100,000 for finding the next mersenne prime if they are not helpful? what is the point of the great internet search for mersenne primessssssssssssssssss???


Also, I heard that when we have found primes large enough, then super computers will then be allowed to be sold to the general public as they won't be able to hack into people's security anymore

There is no restriction on the public buying supercomputers. All one needs is a lot of money to buy
the hardware and a lot of money for the electricity. The cash prize is NOT for finding the next Mersenne prime
specifically.

It is for finding a prime [any prime] with 100 million digits; It's purpose is to push the limits of computation.