Handed out: 1/26/05
This is an exercise in using static methods and loops, and in expressing algorithms in Java.
For this course, every method is required to have a clear and concise contract. A contract is a comment that describes what a method does. Use the following guidelines for writing contracts.
A contract describes what a method does, not how the method works.
Use complete sentences. A contract should be readable.
Please write a contract in front of the method definition. Normally, you read the contract before you read the method definition.
A contract is not merely a hint. A contract must provide enough detail to explain what a method does. Someone who wants to use a method should be able to read only the contract and the method heading, and know enough to be able to use the method, without looking at the body.
A contract is not a road map to the method body. Do not refer to lines in the body. The idea is that the contract makes sense even to someone who cannot see the method body.
A contract should mention every parameter by name, and explain its significance. Someone reading the contract should understand what to pass as the arguments.
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.
A positive integer n is prime if n > 1 and the only divisors 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 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. Programs can use larger numbers by making use of classes that support them. For simplicity, we will use smaller integers, of type long, but the algorithms will work well for very large integers, up to thousands of digits.
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.
If p is a prime number, then there do not exist any Fermat-witnesses that show p is not prime. That is, wp-1 mod p = 1 for all w where 0 < x < p. So Fermat-witnesses cannot lie. This is the fact that Pierre Fermat proved.
If n is not prime, then (with the exception of some rarely occurring numbers called Carmichael numbers) at least half of the numbers w between 1 and n-1 are Fermat-witnesses that n is not prime. So witnesses are abundant. This fact was noticed in the 1970s.
So, to tell whether n is prime, the idea is to guess a random number w between 1 and n-1, and to 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 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 its contract, into your program. You will find it useful. 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)
{
long p = powermod(x, k/2, m);
return (p*p) % 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.lang.*; 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 two static methods in the same class as main.
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.
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, and the iswitness method to test whether a number is a witness, and it should try 20 candidates before it concludes that n is prime.
Now write a main method that reads a number L from the user and prints all of the prime numbers that are less than or equal to L. 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.
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.
The actual algorithm for testing whether a number is prime contains a patch that detects Carmichael numbers. Those numbers are so rare, however, that the patch is almost never needed in practice.
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.