Programming Praxis

As we know, it is difficult to prove that a number n is prime, so the usual recourse is a pseudoprimality test that is easy and fast but may possibly, though with very small probability, produce an incorrect answer. The most commonly used pseudoprimality test is doubtless the Miller-Rabin test, even though it is known to have errors in some circumstances. In today’s exercise we will examine the Frobenius test, which is an extension of and improvement on the Lucas test of a previous exercise.

Frobenius Pseudoprimality Test: Given an integer n greater than 2, determine with high probability if it is COMPOSITE or PROBABLY PRIME:

1. [Choose parameters] Set a and b to distinct random numbers uniformly distributed on the range 1 to n-1 inclusive. Set d = a^2 – 4b. If d is a perfect square or if gcd(2abd, n) ≠ 1 go to Step 1.

2. [Initialization] Set m = (n – (d/n)) / 2, where (d/n) is the jacobi symbol. Set w = a^2 * b^(-1) – 2 (mod n), where b^(-1) is the modular inverse of b with respect to n. Set u = 2. Set v = w. Set ms to a list of the bits in the binary representation of m, most significant bit first.

3. [Compute Lucas chain] If ms is empty, go to Step 4. If the first element of ms is 1, set u = u * v – w (mod n), set v = v * v – 2 (mod n), remove the first element of ms, and go to Step 3. If the first element of ms is 0, set v = u * v – w (mod n), set u = u * u – 2 (mod n), remove the first element of ms, and go to Step 3.

4. [Lucas test] If w * u ≠ 2 * v (mod n), report COMPOSITE and halt.

5. [Frobenius test] Set x = b ^ ((n-1)/2) (mod n). If x * u == 2 (mod n), report PROBABLY PRIME, otherwise report COMPOSITE. Halt.

A Frobenius test by itself isn’t perfect, so it is common to combine it with a Miller-Rabin pseudoprime test to just a few small bases.

Your task is to write a primality test based on Frobenius pseudoprimes. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2