## CS13002 Programming and Data Structures | ## Section: 4/D, Spring 2005 |

## Assignment 3

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

2^{p-1}= 1 (mod p).The converse of this statement is not true, i.e., there exist composite integers n satisfying

2^{n-1}= 1 (mod n).An integer

nsatisfying 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
mulmodthat takes three integer argumentsa,b,mand returns the product ofaandbmodulom.- Write a function
expmodthat takes three integer argumentsa,e,mand returns the value ofa. This function should call^{e}(mod m)mulmodrepeatedly. 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 computing2you must^{n-1}(mod n)notfirst compute2and then take remainder modulo^{n-1}n. The reason is that except for few small values ofnthe integer2is too big to fit in any built-in integer or floating point variable. Every time you multiply, you should reduce the product modulo^{n-1}n. For example, taken = 27. Then2reduced modulo^{10}nis 25, since2. Multiplying by another 2 gives 50 which is 23 modulo 27. We also have^{10}= 1024 = 37 x 27 + 252.^{11}= 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 gets1(mod n)as the exponentiated value, one certifiesnto 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

nwhich let the algorithm fail for every baseacoprime ton. These integers are calledCarmichael 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 theMiller-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.