Finding Prime NumbersDate: 11/10/97 at 22:54:21 From: Ulric Cajuste Subject: How to determine if a number is prime Hi. What is the fastest way to determine if a number is prime? I thought of dividing that number by up to half of it but I'm sure there is a better way. Date: 11/11/97 at 10:09:50 From: Doctor Wilkinson Subject: Re: How to determine if a number is prime You don't have to go as far as half the number. The square root of the number will do, because if for example n has a factor d greater than the square root of n, then n/d will be less than the square root of n. There are many more sophisticated methods for determining whether a number is prime without actually factoring it. Especially for very large numbers, these are a lot faster than just trying to find factors. I can give you more details if you're interested. -Doctor Wilkinson, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 11/11/97 at 15:31:56 From: Ulric Cajuste Subject: Re: How to determine if a number is prime Yes, I'm interested in more sophisticated ways to determine prime numbers. Thanks for your time. Ulric Date: 11/11/97 at 20:47:32 From: Doctor Wilkinson Subject: Re: How to determine if a number is prime The most common way to check whether or not a large number is prime is known as the Miller-Rabin test. This has the interesting property that if it tells you the number is composite, then it is definitely composite, though it won't tell you any of the factors. If it doesn't tell you the number is composite, however, it only tells you that it is probably prime. The degree of certainty is very high, however. If you need to be absolutely sure, there are fancier tests you can use, but I don't have the details. In most practical applications, 99.999% certain is good enough. Here's how it works: let N be the number you want to test, and let N - 1 = 2^s * t, where t is odd. This is easy to calculate. You just keep dividing by 2 until you get an odd number. Pick a number < N at random. You can keep repeating the test for different values of a. The more values of a you use, the more certain the result. Now all the arithmetic you do from here on out is going to be mod N. That is, you always take the remainder from dividing by N after every operation. You start the process by letting u = a^t That is, you take the t'th power of u, taking the remainder mod N after every multiplication. (There are shortcuts to doing this power operation so that you don't have to actually multiply t times: this is important when you are looking at very large numbers.) Now if u is 1, you conclude that N is probably prime. To make sure, try some more values of a. If u isn't 1, then you keep squaring u (don't forget to keep taking the remainder mod N). If you hit 1 without hitting N-1 first, you can definitely conclude that the number is composite. Otherwise, you again conclude that the number is probably prime, and you can try another value of a to be more certain. -Doctor Wilkinson, The Math Forum Check out our web site! 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/