Tag Archive

Witness Numbers: Finding Primes

The Numberphile video above is an excellent introduction to primality tests – where we conduct a test to determine if a number is prime or not.  Finding and understanding about prime numbers is an integral part of number theory.  I’m going to go through some examples when we take the number 2 as our witness number.  We have a couple of tests that we conduct with 2 – and for all numbers less than 2047 if a number passes either test then we can guarantee that it is a prime number.

Miller-Rabin test using 2 as a witness number:

We choose an odd number, n >2. First we need to write it in the form:

Then we have to conduct a maximum of 2 different tests:

If either of the above are true then we have a prime number.

Testing whether n = 23 is prime.

First we need to write 23 in the following form:

Next we need to check if the following is true:

Remember that mod 23 simply means we look at the remainder when we divide by 23.  We can do this using Wolfram Alpha – but in this case let’s see how we could do this without a calculator:

Therefore this passes the test – and we can say that it is prime.

Testing whether 1997 is prime

For 1997 we have:

So we need to first test if the following is true:

However using Wolfram Alpha we get:

So this fails the first part of the test.

Trying the second part of the test, we need:

We have already tested the case when r=0 (this gives the earlier result), so just need to look at what happens when r=1.  Again we use Wolfram Alpha to get:

This passes the 2nd part of the test and so confirms that 1997 is prime.

What happens with 2047?

2047 is not prime as we can write it as 2 x 3 x 11 x 31.  However it is the first number for which the witness 2 gives a false positive (i.e we get a positive result even though it is not prime).  We write 2047 as:

But we do indeed get:

So we can call 2047 a pseudoprime – it passes this prime number test but is not actually prime.

Larger primes

For numbers larger than 2047 you can combine witnesses – for example if you use both 2 and 3 as your witness numbers (and regard a positive result as at least one of them returning a positive result) then this will find all primes for n < 1,373,653.

More interestingly for extremely large numbers you can use this test to provide a probability estimate for the likelihood that a number is prime.  Lots to explore here!