## Combined N±1 Primality Prover

### March 7, 2014

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 = *f*1 * *r*1 and *n* + 1 = *f*2 * *r*2 with *r*1 and *r*2 odd, gcd(*f*1, *r*1) = gcd(*f*2, *r*2) = 1 and the prime factorizations of *f*1 and *f*2 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(*f*1**f*1**f*2/2, *f*1**f*2**f*2/2) > *n*. Then *n* is prime if all the factors of *f*1 and *f*2 are prime and the following conditions hold:

Condition 1: For each prime

pdividingf1 there is an integer a such thata^(n−1) = 1 (modn) and gcd(a^((n−1)/p)−1,n) = 1. A differentamay be used for each primep.

Condition 2: For each prime

pthere is a Lucas sequenceU(P,Q) with discriminantD=P^2 – 4Q0 and the jacobi symbol (D/N) = −1 such thatU(n+1) = 0 (modn) and gcd(U((n+1)/p),n) = 1. The same discriminantDmust be used for each primep, butPandQmay vary. GivenPandQ, a newP‘ andQ‘ with the sameDcan be calculated asP‘ =P+ 2 andQ‘ =P+Q+ 1.

The bounded version is similar. Factor *n*−1 and *n*+1 by trial division until max(*b***f*1+1, *b***f*2−1) * (*b***b***f*1**f*2/2 + 1) > *n*, where *b* is the smallest number that is known to be a factor of neither *r*1 nor *r*2; 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

asuch thata^(n−1) = 1 (modn) and gcd(a^((n−1)/R1)-1, n) = 1.

Condition 4: There is a Lucas sequence

U(P,Q) with the same discriminantDas in Condition 2 above such thatU(n+1) = 0 (modn) 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.