For September 15, 2009
This is an exercise in making static methods and loops, and in expressing algorithms in Java.
An algorithm is a way of solving a problem. Many algorithms are obvious enough that an experienced algorithm designer can be expected to find them on his or her own, without too much work. Typically, those algorithms correspond closely to how you would solve a problem by hand.
But some algorithms are more subtle. Typically, they are discovered by people with specialized knowledge and you read about them in books or papers. After you read about them, you should be able to make those subtle algorithms work for you, even if you do not understand everything about why they work.
This exercise involves a subtle algorithm. I will explain what is involved in the algorithm, and partially justify it, but cannot explain completely why it works. But writing the algorithm in Java is a simple matter.
A positive integer n is prime if n > 1 and the only factors of n are 1 and n. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19.
For cryptographic applications, such as sending secure email over the internet, some programs need to have very large prime numbers. For security, a program should never get a prime number from a table. It needs to find its own. Typically, prime numbers with 100 or more decimal digits are used. In Java you can only use about 18 digit numbers, if you use type long, and that will be large enough for our purposes.
An obvious way to tell whether a number n is prime is to try all numbers from 2 to n-1, to see whether any of them are factors. But that can be very expensive if n is a really large number. For a 100 digit number, that algorithm will not finish within the lifetime of the computer. You can improve the algorithm by realizing that, if n has a factor, then at least one of those factors is no larger than the square root of n. So you only need to look at 2, 3, ..., s, where s is the square root of n, before you can conclude that n is prime. Unfortunately, if n is a 100 digit number, that still takes more time than the lifetime of the computer!
Some algorithms work by trying to find witnesses to facts. A witness is some information that can be used to justify a fact. For example, you can show that a number is not prime by finding a factor of it. Since 3 is a factor of 15, you could say that 3 is a witness, in this sense, that 15 is not prime. Similarly, 11 is a witness that 143 is not prime, since 11 is a factor of 143.
A witness testifies to a fact, by providing evidence for it. The way it testifies is by passing a kind of test. There are different kinds of witnesses, depending on the kind of test that they have to pass. For example, you can say that an integer k is a factor-witness that n is not prime provided the test
k > 1 and k < n and k is a factor of nis true. So 11 is a factor-witness to the fact that 143 is not prime because
11 > 1 and 11 < 143 and 11 is a factor of 143
Finding just one factor-witness is enough to convince you that a number is not prime. The obvious algorithm outlined above works by trying to find a factor-witness. It looks at 2, 3, 4, 5, ..., n-1, checking each one to see whether it is a factor-witness. Think of the algorithm as similar to a policeman searching door-to-door trying to find a witness to a crime.
Unfortunately, factors are a difficult kind of witness to find. For a large number n, there are a huge number of candidates for factor-witnesses, and very few of them are actually factor-witnesses. So the search for a factor-witness can take a long time.
For an efficient algorithm, we need a more abundant kind of witness. It turns out that abundant witnesses do exist, but you need to use a different way of having a witness testify. A witness is no longer a factor.
| Definition of a Fermat-witness |
|---|
|
Suppose that n is an integer where n > 1. Say that a positive integer w is a Fermat-witness to the fact that n is not prime if 0 < w < n and wn-1 mod n is not equal to 1. (Recall that A mod B is the remainder when you divide A by B, and is written A % B in Java.) |
For example, 3 is a Fermat-witness that 4 is not prime since 33 mod 4 = 27 mod 4 = 3 (not 1). Similarly, 2 is a Fermat-witness that 9 is not prime, since 28 mod 9 = 256 mod 9 = 4 (not 1).
(Pierre Fermat (1601-1665) was a French lawyer and government official whose hobby was the mathematics of integers. He proved a key result that is the basis for why Fermat-witnesses work. Fermat is is pronounced fair-mah.)
Here are some useful facts about Fermat-witnesses.
Fermat-witnesses cannot lie. If p is a prime number, then there do not exist any Fermat-witnesses that show p is not prime. (That is, when p is prime, wp-1 mod p = 1 for all w where 0 < w < p.) This is the fact that Pierre Fermat proved.
Fermat-witnesses are abundant. With some rarely occurring exceptions, if n is not prime, then at least half of the numbers w between 1 and n-1 are Fermat-witnesses that n is not prime. This fact was noticed in the 1970s.
To tell whether n is prime, you guess a random number w between 1 and n-1 and check whether w is a Fermat-witness that n is not prime. If it is, then you know for sure that n is not prime, since Fermat-witnesses cannot lie, so you can give an answer immediately.
If your random number w is not a Fermat-witness, then you can try another random number and see whether that is a Fermat-witness. You keep trying to find a Fermat-witness until either you find one or you have tried about 20 candidates. Since Fermat-witnesses are abundant, if you try 20 random numbers and none are Fermat-witnesses, it is very likely that no Fermat-witnesses exist. In that case, you claim that n is (probably) prime.
Copy the following static method, along with the comment, into your program. Use it for computing xk mod m. It goes inside the class, but not inside the main method.
//==============================================================
// powermod(x,k,m) produces (x to the k-th power) mod m.
//
// For example,
//
// powermod(2,3,7) = 1 since 2 to the 3 power is 8,
// and 8 mod 7 = 1.
//
// powermod(3,2,7) = 2 since 3 to the 2 power is 9,
// and 9 mod 7 = 2.
//
// IMPORTANT REQUIREMENT: This method only works if m is less
// than about 2 billion. If m is too large, it does not produce
// the correct result.
//==============================================================
public static long powermod(long x, long k, long m)
{
if(k == 0) return 1;
else if(k % 2 == 0) return powermod((x*x) % m, k/2, m);
else return (x * powermod(x, k-1, m)) % m;
}
You can get numbers that look like they are random by using the Java Random class. Add line
import java.util.*;to your program. Inside the main program, add a line to create a random number factory.
Random randomNumberFactory = new Random();Now, to get a long integer that appears to be random, and to put that apparently random number into variable r, use
r = randomNumberFactory.nextLong();Unfortunately, that will give you a number that is not in the desired range. Remember that you want a Fermat-witness for n to be larger than 0 and less than n. To get that, write
r = randomNumberFactory.nextLong(); r = (Math.abs(r) % (n-1)) + 1;
Note. Any method that needs the random number factory should have the factory passed to it as a parameter. The type of the factory is Random.
Write three static methods inside your class, one after another.
isWitness(w, n) should return a result of type boolean. It should return true if w is a Fermat-witness that n is not prime, according to the definition above, and should return false if w is not a Fermat-witness for n. Use the powermod method. Remember that w is a Fermat-witness if 0 < w and w < n and wn-1 mod n =/= 1. The heading for isWitness is as follows.
public static boolean isWitness(long w, long n)
Write a main method that just runs isWitness on a few pairs of numbers and shows the answer. Here is an example.
public static void main(String[] args)
{
System.out.println("isWitness(2,3) = " + isWitness(2,3) + " (should be false)");
System.out.println("isWitness(2,7) = " + isWitness(2,7) + " (should be false)");
System.out.println("isWitness(3,4) = " + isWitness(3,4) + " (should be true)");
System.out.println("isWitness(2,9) = " + isWitness(2,9) + " (should be true)");
}
Does it appear to work?
isPrime(n, randomNumberFactory) should return true if n is (probably) prime, and false if n is (surely) not prime.
This method is required to use the subtle algorithm outlined above, using Fermat-witnesses. It should use the random number factory that is passed to it to select numbers to try. It should use isWitness to test whether a number is a witness. If it finds a witness, it should return false without trying to find any more witnesses. It should try 20 candidates before it concludes that n is prime. The heading for isPrime is as follows.
public static boolean isPrime(long n, Random randomNumberFactory)
Modify the main method that so that it runs isPrime on a few numbers and shows the answer. Does isPrime appear to work?
Modify the main method so that it reads a number L from the user and prints all of the prime numbers that are less than or equal to L. Make it prompt the user for the number. Use the same way of reading an integer as in lab 2. Use your isprime method to tell whether a number is prime.
Test your program. Does it appear to work? Look at the results, and see whether they look right. Try a large enough L so that you will put some stress on your program. If you only use your program to test whether 2 and 3 are prime, you have hardly tested it at all. Do not just presume that it will work.
Print your program and turn it in. Be sure that your name is in the program, as a comment at the beginning.
The algorithm that you have implemented is very close to the one that is used in cryptographic applications for finding large prime numbers. To find a large prime number, an application just tries random numbers until it happens to choose one that is prime.
Recall that there are some rare exceptions for which Fermat-witnesses are not abundant. Those exceptions are called Carmichael numbers. The first three Carmichael numbers are 561, 1105 and 1729. Those numbers are not prime, but your program will probably report that they are prime because there not very many Fermat-witnesses for them. The actual algorithm that is employed in practice for testing whether a number is prime contains a patch that detects Carmichael numbers. We cannot go into that patch here. (For really large numbers, Carmichael numbers are so rare that the chance that you choose on is very tiny.)
An integer is not prime if there exists a factor for it (other than itself and 1). So you might expect that any algorithm that tells you that a number is not prime should do so by finding a factor of that number. But the algorithm that you have implemented can determine that a number is not prime without finding a factor. Somehow, it knows that a factor must exist without being able to find one.
It is generally believed that the problem of finding a factor of a number is much more difficult than just deciding whether a factor exists. It seems some things leave telltale signs, so you know they are there, but they are difficult to track down.
The world of algorithms is similar. There are lots of interesting and surprising algorithms waiting to be discovered. Just a few years ago a new algorithm was discovered for testing whether a number is prime without using any random numbers. The most surprising thing to most researchers was not that such an algorithm existed, but how short and simple it turned out to be. It can be written in half a page, provided you have some preexisting support for some standard mathematical operations, such as multiplication and division of polynomials.