Finding Prime Numbers

Date: 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/