CS13002 Programming and Data Structures
Section: 4/D, Spring 2005
It is known that if p is an odd prime, then2p-1 = 1 (mod p).
The converse of this statement is not true, i.e., there exist composite integers n satisfying2n-1 = 1 (mod n).
An integer n satisfying the last relation is called a (base-2) pseudoprime.
In this exercise, you are asked to report all composite pseudoprimes n in the range 3 <= n <= 33333. You are advised to proceed in the following manner.
- Write a function mulmod that takes three integer arguments a,b,m and returns the product of a and b modulo m.
- Write a function expmod that takes three integer arguments a,e,m and returns the value of ae(mod m). This function should call mulmod repeatedly. Note that (a(mod m))(b(mod m))=(ab(mod m)).
- Write a function that checks if its argument is a pseudoprime.
- Write a function that checks if its argument is prime.
- Solve the original problem in the main() function using invocations of the functions defined earlier.
Note: For computing 2n-1(mod n) you must not first compute 2n-1 and then take remainder modulo n. The reason is that except for few small values of n the integer 2n-1 is too big to fit in any built-in integer or floating point variable. Every time you multiply, you should reduce the product modulo n. For example, take n = 27. Then 210 reduced modulo n is 25, since 210 = 1024 = 37 x 27 + 25. Multiplying by another 2 gives 50 which is 23 modulo 27. We also have 211= 2048 = 75 x 27 + 23.
Historical note: This method of checking primality (more correctly, pseudoprimality) of integers is a practical algorithm for detecting primes. One typically employs several bases (in addition to 2) and if for all these bases one gets 1(mod n) as the exponentiated value, one certifies n to be prime. The algorithm may occassionally give wrong answers (i.e., it may certify some composite integers as primes), as this experiment exemplifies. But the density of the integers for which the algorithm fails is pretty low.
There are, however, composite integers n which let the algorithm fail for every base a coprime to n. These integers are called Carmichael numbers. 561 is the smallest Carmichael number. Though not very common, there are infinitely many Carmichael numbers. An improved version of the above primality test, popularly known as the Miller-Rabin primality test, overcomes the difficulty posed by Carmichael numbers. This test is still probabilistic, i.e., it may give incorrect outputs at certain times, but the error probability can be made extremely low, say, much smaller than the probability that the computer explodes while performing the computation. Till date, the Miller-Rabin test is the most practical primality testing algorithm.