Finding and Factoring Large or Mersenne PrimesDate: 02/22/98 at 03:06:33 From: Nathan Cypra Subject: Finding Large Primes (Mersenne Primes), Efficient Factorization I have two questions: 1. How do you find extremely large primes (Mersenne Primes) and how do you tell if they are prime? 2. What is the most efficient way of finding prime factors? I have come up with no possible solutions and am completely stumped. Thanks. Date: 03/03/98 at 12:45:12 From: Doctor Nick Subject: Re: Finding Large Primes (Mersenne Primes), Efficient Factorization Hello Nathan - For your first question, you'll want to take a look at what's known as the Lucas-Lehmer test (L-L test). This is the best way for checking if a large Mersenne number is prime. A Mersenne number is a number of the form 2^n-1. That is, it's any number that's one less than a power of 2. Let M(n) = 2^n -1. The L-L test says that all we have to do to see if M(n) is prime is to check if it divides evenly into a certain other number. That "certain other number" is generated in the following way. We make a sequence s(m) starting with s(0) = 4 by squaring and subtracting 2 to get to the next number. So, s(1) = s(0)^2 -2 = 4^2 - 2 = 14. s(2) = s(1)^2 -2 = 14^2 - 2 = 194. s(3) = s(2)^2 -2 = 194^2 - 2 = 37634. s(4) = s(3)^2 - 2 = 37634^2 -2 = 1416317954. s(5) = s(4)^2 - 2 = 1416317954^2 - 2 = 2005956546822746114. And so on. Notice the numbers get big really fast. Now, the L-L test says that M(n) is prime if (and only if) M(n) evenly divides s(n-2). So for instance, M(3) = 2^3 - 1 = 7 is prime because 7 evenly divides 14, which is s(3-2) = s(1), since 14/7 = 2. M(4) = 2^4 - 1 = 15 is not prime because 15 does not evenly divide 194, which is s(4-2) = s(2), since 194/15 = 12 + 14/15. M(5) = 2^5 - 1 = 31 is prime because 31 evenly divides 37634, which is s(5-2) = s(3), since 37634/31 = 1214. Now, the numbers s(m) get big really fast, and that could be a problem for our calculations. It turns out we can improve things by doing what's called "reducing modulo M(n)" at each step. What that means is that if s(m) is bigger than M(p) at any step, we can subtract M(n) until it is less than M(n), but still bigger than 0. For example, to reduce 29 modulo 6, we subtract 6 from 29 repeatedly until we get less than 6: 29 - 6 = 23 -> 23 - 6 = 17 -> 17 - 6 = 11 -> 11 - 6 = 5. So 29 reduced modulo 6 is 5. Another way to get there, instead of repeatedly subtracting, is to divide and take the remainder: dividing 6 into 29 gives 4 with a remainder of 5. Now getting back to our test, suppose we want to see if M(5) = 31 = 2^5 - 1 is prime. We generate the s(m), but reduce by 31 as we go. So we get s(0) = 4. s(1) = 4^2 - 2 = 14. s(2) = 14^2 - 2 = 194 = 31*6 + 8 (so 194 reduced modulo 31 is 8), so we have s(2) = 8. s(3) = 8^2 - 2 = 62 = 31*2 (so 62 reduced modulo 31 is 0), so we have s(3) = 0. Since 31 divides 0 (everything divides 0), 31 is prime. Let's do another example. Suppose we want to see if M(7) = 127 = 2^7 - 1 is prime. We generate the s(m), each time reducing modulo 127. We get s(0) = 4. s(1) = 14. s(2) = 194 -> 67 (since 194 - 127 = 67). s(3) = 67^2 - 2 = 4487 -> 42 (since 4487 = 35*127 + 42). s(4) = 42^2 - 2 = 1762 -> 111 (since 1762 = 13*127 + 111). s(5) = 111^2 - 2 = 12319 -> 0 (since 12319 = 97*127). Again, since M(7) divides s(5), M(7) is prime. You can see here that reducing modulo 127 kept the numbers we had to deal with from getting too large. One more example of the L-L test. To check if M(6) = 2^6 - 1 = 63 is prime, we have s(0) = 4. s(1) = 14. s(2) = 194 -> 5. s(3) = 5^2 - 2 = 23. s(4) = 23^2 - 2 = 527 -> 23. Since 63 doesn't divide 23, we can tell that 63 is not prime. By the way, it can be shown that if M(n) is prime, then n itself is prime. So you don't need to check, for instance, M(8) - we know it's not prime since 8 isn't prime. For your second question, have a look at http://mathforum.org/dr.math/faq/faq.prime.num.html If you want to efficiently factor numbers that aren't too big, the fastest way (and it's pretty fast) is to test for divisibility by primes. To do that well, you'll need a table of primes, which you can generate using the Sieve of Eratosthenes (it's described at the web page above). If you want to find the prime factors of n, try dividing it by 2, then 3, then 5, etc., running through the primes. At each step, if the prime divides the number, replace that number with the result of that division. This will speed things up. For example, if we want to find the prime divisors of 30, we start by dividing by 2, which gives us 15, then 3, which gives 5, which is itself prime. Hence the prime factors of 30 are 2, 3 and 5. Another example: take 98. It's divisible by 2. We get 98/2 = 49. Now we try to divide 3 into 49: we get a remainder of 1, so 3 doesn't divide 49. Now try to divide 5 into 49: we get a remainder of 4, so 5 doesn't divide 49. Now try to divide 7 into 49: we find it divides evenly and gives us 7. We know 7 is prime, so we're done. The result is that 98 = 2 * (7^2). Once you have a table of primes to work from, this method is probably fast enough unless the number you're trying to factor is pretty large (say, at least 10^12). There are ways to check if a number is prime, though, to save you the trouble of trying all those prime factors. There are tests like the Lucas-Lehmer test that can be applied to numbers of any form. Now, for really large numbers, there are very sophisticated factoring methods, such as the Number Field Sieve. These methods work on numbers of all sizes, but for small numbers, there are faster methods. Your questions are part of the area of mathematics known as number theory. You can probably find books on number theory in a local library which you might enjoy. Have fun, -Doctor Nick, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/