Primality TestingDate: 12/02/2004 at 09:09:53 From: S. Kanagaraj Subject: Primality Testing How can I determine if a large number given to me is prime? Is there a process or test I can use? I'm writing a C program and have tried dividing the given number by 2 or 3 and by the numbers other than 1 and itself. But it takes so many steps in writing my program. Is there a faster test? Date: 12/02/2004 at 10:37:02 From: Doctor Vogler Subject: Re: Primality Testing Hi S, Thanks for writing to Dr. Math. The next thing you have to decide is how much math you want to learn. Testing for primality is not an easy thing to do, and there are numerous methods, some of which are better for different sizes of numbers, and some of which give better results or have better features. For example, on our prime number page, Prime numbers http://mathforum.org/dr.math/faq/faq.prime.num.html there is a link to one of the simplest primality tests at Primality Test http://mathforum.org/library/drmath/view/54371.html This will tell you to try dividing by every number up to sqrt(222221) = 471.4 and you will eventually find that 222221 is divisible by 359. A faster test, slightly more complicated but the least complicated of the advanced tests, is the Fermat Pseudoprimality Test. It is called a "pseudoprimality test" because it can only tell you if a number is NOT prime, and if it doesn't tell you that it's not prime, then it might still be either prime or composite. That uses modular arithmetic, Mod, Modulus, Modular Arithmetic http://mathforum.org/library/drmath/view/62930.html and is based on the fact that a^(p-1) = 1 (mod p) whenever p is prime and does not divide a (this is sometimes called Fermat's Little Theorem). So you pick a=2 or a=3 or something similar (and perhaps try several values) and test if a^(n-1) = 1 (mod n). If it doesn't, then n cannot be prime. If it does, then... well... n is *probably* prime. There are many other more complicated tests, but they get harder and harder to understand, and harder and harder to use. But when you have a really, *really* big number that you want to test, you generally need a really advanced primality test. See also Determining If a Number is Prime http://mathforum.org/library/drmath/view/65454.html Exploring Fermat's Little Theorem http://mathforum.org/library/drmath/view/51588.html Large Prime Numbers http://mathforum.org/library/drmath/view/51539.html Primality Testing http://mathforum.org/library/drmath/view/55846.html Prime Number Tests http://mathforum.org/library/drmath/view/55884.html Testing primality of 32-bit numbers http://mathforum.org/library/drmath/view/51512.html Testing Prime Numbers http://mathforum.org/library/drmath/view/62917.html If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, 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/