CS21003 Algorithms I CS29003 Algorithms Laboratory Autumn 2011, L-T-P: 3-1-0 L-T-P: 0-0-3

## Programming Assignment 0

Let m > 5 be an odd integer which is not a multiple of 5. The following algorithm determines whether m is prime or composite.
If m is of the form 5k+1 or 5k-1, set l = 1.
If m is of the form 5k+2 or 5k-2, set l = -1.
Set n = m - l.
Compute the Fibonacci number F = Fn modulo m.
If F = 0, return "m is prime", else return "m is composite".

If m is prime, the test detects it. On the other hand, if m is composite, the test may still declare m as prime. The composite numbers for which this test makes a mistake are rather rare. For example, there are only 5780 composite numbers less than 231 that are certified as prime by the above test. The smallest such number is 323. In this assignment, you are asked to implement this test, known as the Fibonacci primality test. The most time-consuming task in the test is the computation of Fn modulo m.

### Part 1

Implement arithmetic modulo m. Write functions to add, subtract and multiply two integers modulo m.

Let a and b be two operands in the range 0, 1, ...m-1.

• In order to compute a + b modulo m, add a and b as integers, and if the sum is larger than m - 1, subtract m from the sum.
• In order to compute a - b modulo m, first check whether a >= b. If so, return the integer difference a - b, else return a + m - b.
• The modular product of a and b is computed as (a * b) % m.

You have to work with values of m as large as about 232, so you may plan to use a 64-bit integer variable (unsigned long long int) for storing your integers.

### Part 2

Write a recursive function to compute Fn modulo m. The function should use the standard formula Fi = Fi - 1 + Fi - 2 (mod m). Run the test for m = 29 and m = 43. Measure the times taken by the test on these two input values.

### Part 3

Write an iterative function to compute Fn modulo m. The function should start with F0 = 0 and F1 = 1, and subsequently compute Fi using the formula Fi = Fi - 1 + Fi - 2 (mod m). for i = 2, 3, 4, ..., n. Measure the times taken by the test for the input values m = 33554393 and m = 1073741789.

### Part 4

Consider the binary expansion of n = (nsns - 1...n1n0)2. Denote Ni = (nsns - 1...ni)2. With this notation, Ns + 1 = 0, and N0 = n. Iteratively compute FNi and FNi + 1 for i = s + 1, s..., 1, 0. For i = s + 1, we have the initialization FNs+1 = F0 = 0, and FNs+1 + 1 = F1 = 1. Subsequently, for i = ss - 1, ..., 1, 0, use the following doubling formulas to compute FNi and FNi + 1 from FNi+1 and FNi+1 + 1 as follows.

F2k = Fk (2Fk+1 - Fk) (mod m),
F2k+1 = Fk+12 + Fk2 (mod m),
F2k+2 = Fk+1 (Fk+1 + 2Fk) (mod m).

If the i-th bit ni of n is 0, then Ni = 2Ni+1 and Ni + 1 = 2Ni+1 + 1, so use the first two of the above doubling formulas. On the other hand, if ni = 1, then Ni = 2Ni+1 + 1 and Ni + 1 = 2Ni+1 + 2, so use the last two of the above doubling formulas. When the loop terminates, return FN0. Report the times taken by the Fibonacci test with this function for computing Fn modulo m for m = 2147483647 and m = 4294967291.

Note that you can test whether the i-th bit of an unsigned int n is 0 or 1 by checking whether (n & (1U << i)) is zero or non-zero.

Remark: The recursive function of Part 2 takes time (roughly) proportional to rm, where r = [1 + sqrt(5)] / 2 = 1.618... is the golden ratio. The iterative function of Part 3 takes time proportional to m. Finally, the iterative function of Part 4 takes time proportional to log m.