Handed out: 9/13/04
This is an exercise in using functions and loops.
Every function is required to have a clear and concise contract. A contract is a comment that describes what a function does. Use the following guidelines for writing contracts.
A contract describes what a function does, not how a function works.
Use complete sentences. A contract should be readable.
Please write a contract before the function definition. Normally, you read the contract before you read the function definition.
A contract is not merely a hint. A contract must provide enough detail to explain what a function does. Someone who wants to use a function should be able to read only the contract and the function heading, and know enough to use the function.
A contract is not a road map to the function body. Do not refer to lines in the body. The idea is that the contract makes sense even to someone who cannot see the function body.
A contract should mention every parameter by name, and explain its significance. Someone reading the contract should understand what to pass as the parameters.
Two functions are supplied for you, along with contracts. You will write two other functions, with contracts.
An algorithm is a method of solving a problem. Many algorithms are obvious enough that an experienced algorithm designer can be expected to find them without too much work. Typically, those algorithms correspond closely to how you would solve a problem by hand.
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, 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 C++ on a 32-bit computer, you can only use 9 digit numbers. Larger numbers are managed by using packages that can handle very large integers. We will only use small integers, for simplicity, but the algorithms will work well for very large integers.
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. 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. For example, you could show that a number is not prime by finding a factor of it. That is just what the obvious algorithm does. Since 3 is a factor of 15, you could say that 3 is a witness, in this sense, that 15 is not prime, and 11 is a witness that 143 is not prime. The witness testifies to a fact, by providing evidence for it. Finding just one witness is enough to convince you that a number is not prime.
Unfortunately, factors are a difficult kind of witness to find, since there tend not to be very many of them. 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 witness |
|---|
|
Suppose that n is an integer where n > 1.
Say that a number x is a
witness to the fact that n is not
prime if 0 < x < n and
xn-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 C++.) For example, 3 is a witness that 4 is not prime since 33 mod 4 = 27 mod 4 = 3 (not 1). and 2 is a witness that 9 is not prime, since 28 mod 9 = 256 mod 9 = 4 (not 1). |
Here are some useful facts about these witnesses.
If p is a prime number, then there do not exist any witnesses that p is not prime. That is, xp-1 = 1 for all x where 0 < x < p. So witnesses cannot lie.
If n is not prime, then (with the exception of some rarely occurring numbers called Carmichael numbers) at least half of the numbers x between 1 and n-1 are witnesses that n is not prime. So witnesses are abundant.
So, to tell whether n is prime, the idea is to guess a random number x between 1 and n-1, and to check whether x is a witness that n is not prime. If it is, then you know for sure that n is not prime, and can give an answer immediately.
If your random number x is not a witness, then you can try another random number, and see whether that is a witness. You keep trying witnesses until you have tried about 20. Since witnesses are abundant, if you try 20 random numbers and none are witnesses, it is very likely that no witnesses exist. So you claim that n is (probably) prime.
Copy the following functions, along with their contracts, into your program. You will find them useful.
//=========================================================================
// 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: This function requires that x*m < 2 billion. You can
// assure that by making x < 32,767 and m < 32,767.
//=========================================================================
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;
}
}
//=========================================================================
// random(n) returns a pseudo-random number between 1 and n. Each
// time you run random(n), it returns a different number, as long
// as you do not run it more than a few thousand times.
//
// A pseudo-random number appears to be random, but is not really
// random at all. Each time you run the program, you will get the
// same first result, the same second result, etc.
//=========================================================================
long random(long n)
{
//--------------------------------------------------------------
// Note: This function needs to remember some information from
// one call to the next. It uses an old but simple style of doing
// that, one that is not highly recommended in modern design.
// Object-oriented programming, which we will look at later,
// provides a better (but more involved) approach.
//--------------------------------------------------------------
double r;
static long seed = 31771;
const long modulus = 31957;
seed = (seed*14723 + 13) % modulus;
r = double(seed)/double(modulus);
return ((long) (r*n)) + 1;
}
Write two functions.
iswitness(x,n) should return a result of type bool. It should return true if x is a witness that n is not prime, according to the definition above, and should return false if x is not a witness for n. Use the powermod function.
isprime(n) should return true if n is (probably) prime, and false if n is (surely) not prime. This function is required to use the subtle algorithm outlined above. It should use the random function to select numbers to try, and the iswitness function to test whether a number is a witness.
Now write a main program 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 function to tell whether a number is prime.
Print your program and turn in the printed version. Command
lpr prog2.cppwill print prog2.cpp.
The algorithm that you have implemented is very close to the one that is used in cryptographic applications for finding large prime numbers. The applications just choose random large numbers and test whether they are prime, until they eventually hit on one that is prime.
The actual algorithm 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). The algorithm that you have implemented can determine that a number is not prime, but it does not find 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. Some things leave telltale signs but are difficult to track down.
The world of algorithms is similar. There are lots of interesting and surprising algorithms waiting to be discovered.