Programming Praxis

We have seen the n−1 primality prover in one previous exercise and the n+1 primality prover in another previous exercise. In today’s exercise we combine the two tests. There are two versions, one using a factoring bound and one without. The basic idea of both provers is to express n − 1 = f1 * r1 and n + 1 = f2 * r2 with r1 and r2 odd, gcd(f1, r1) = gcd(f2, r2) = 1 and the prime factorizations of f1 and f2 known, then perform various tests if the partial factorizations are sufficient. This is often called the BLS primality prover because the 1975 paper by John Brillhart, Derrick Lehmer and John Selfridge proves all the necessary theorems.

For the unbounded version of the test, factor n−1 and n+1 by any convenient method until max(f1*f1*f2/2, f1*f2*f2/2) > n. Then n is prime if all the factors of f1 and f2 are prime and the following conditions hold:

Condition 1: For each prime p dividing f1 there is an integer a such that a^(n−1) = 1 (mod n) and gcd(a^((n−1)/p)−1, n) = 1. A different a may be used for each prime p.

Condition 2: For each prime p there is a Lucas sequence U(P,Q) with discriminant D = P^2 – 4Q 0 and the jacobi symbol (D/N) = −1 such that U(n+1) = 0 (mod n) and gcd(U((n+1)/p), n) = 1. The same discriminant D must be used for each prime p, but P and Q may vary. Given P and Q, a new P‘ and Q‘ with the same D can be calculated as P‘ = P + 2 and Q‘ = P + Q + 1.

The bounded version is similar. Factor n−1 and n+1 by trial division until max(b*f1+1, b*f2−1) * (b*b*f1*f2/2 + 1) > n, where b is the smallest number that is known to be a factor of neither r1 nor r2; if you’re clever, you can perform the two trial divisions simultaneously, looking for remainders of either 0 or 2 when dividing n+1 by the current prime. Then n is prime if Condition 1 and Condition 2 and the following additional conditions hold:

Condition 3: There is an integer a such that a^(n−1) = 1 (mod n) and gcd(a^((n−1)/R1)-1, n) = 1.

Condition 4: There is a Lucas sequence U(P,Q) with the same discriminant D as in Condition 2 above such that U(n+1) = 0 (mod n) and gcd(U((n+1)/R2), n) = 1.

In practice, it is common to write a single program that includes both versions. First perform trial division up to some convenient limit, using the bounded formula to determine if you have enough factors. If that is unsuccessful, use some other method (Pollard rho or elliptic curves work well, because they are good at finding small factors of large numbers) to find more factors, recursively prove any such factors prime, and continue until you have enough.

Your task is to implement the BLS primality prover. 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