Assignment 3

It is known that if p is an odd prime, then

   2p-1 = 1 (mod p).

The converse of this statement is not true, i.e., there exist composite integers n satisfying

   2n-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 a^e(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 2^n-1(mod n) you must not first compute 2^n-1 and then take remainder modulo n. The reason is that except for few small values of n the integer 2^n-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 2¹⁰ reduced modulo n is 25, since 2¹⁰ = 1024 = 37 x 27 + 25. Multiplying by another 2 gives 50 which is 23 modulo 27. We also have 2¹¹= 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.

---

[Submission site] [Lab home] [Course home]