Search:

Labs

Homeworks

# Lab3: Primality Testing Due: Feb 7th, During Lab Section

## Part 1

Implement the modexp function in Figure 1.4 for modular exponentiation. It should take as input three integers x, y, and N and return $$x^y \mod N$$.

## Part 2

Implement the randomized primality testing algorithm in Fig 1.8 using the modexp from part 1 as a subroutine. Given inputs N and k, you should determine whether N is prime or not using k trails. Print N "is prime" or N "is not prime".

## What to turn in

You can test your code on arbitrary integers N to test if they are prime or not. In general, with k trials the probability of returning a wrong answer is $$\frac{1}{2^k}$$.

However, Carmichael numbers are composite numbers that pass fermat's little theorem for all integers $$a$$ relatively prime to $$N$$. For each of the following Carmichael numbers determine the probability of failure in k trials, using k=1000. That is, the probability that the number is determined to be a prime when in fact it is not. The first 32 Carmichael numbers are: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881.

Verify that these probabilities are much higher than $$\frac{1}{2^k}$$.