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 = F_n 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 2³¹ 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 F_n 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 2³², 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 F_n modulo m. The function should use the standard formula F_i = F_i - 1 + F_i - 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 F_n modulo m. The function should start with F₀ = 0 and F₁ = 1, and subsequently compute F_i using the formula F_i = F_i - 1 + F_i - 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 = (n_s, n_s - 1, ..., n₁, n₀)₂. Denote N_i = (n_s, n_s - 1, ..., n_i)₂. With this notation, N_s + 1 = 0, and N₀ = n. Iteratively compute F_Ni and F_Ni + 1 for i = s + 1, s, ..., 1, 0. For i = s + 1, we have the initialization F_Ns+1 = F₀ = 0, and F_Ns+1 + 1 = F₁ = 1. Subsequently, for i = s, s - 1, ..., 1, 0, use the following doubling formulas to compute F_Ni and F_Ni + 1 from F_Ni+1 and F_Ni+1 + 1 as follows.

F_2k = F_k (2F_k+1 - F_k) (mod m),
F_2k+1 = F_k+1² + F_k² (mod m),
F_2k+2 = F_k+1 (F_k+1 + 2F_k) (mod m).

If the i-th bit n_i of n is 0, then N_i = 2N_i+1 and N_i + 1 = 2N_i+1 + 1, so use the first two of the above doubling formulas. On the other hand, if n_i = 1, then N_i = 2N_i+1 + 1 and N_i + 1 = 2N_i+1 + 2, so use the last two of the above doubling formulas. When the loop terminates, return F_N0. Report the times taken by the Fibonacci test with this function for computing F_n 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 r^m, 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.

How to measure time in C programs?

---

Back | Home