Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search