N+1 Primality Prover
February 7, 2014
In the previous exercise we used a Lucas sequence to determine if a number is probably prime. In today’s exercise we use a Lucas sequence to prove the primality of a number N, given the factors of N + 1. Today’s algorithm is similar to a previous exercise in which we proved the primality of a number N using the factors of N − 1.
Choose P and Q such that D = P2 − 4 Q is not a square modulo N. Let N + 1 = F · R with F > R, where R is odd and the prime factorization of F is known. If there exists a Lucas sequence of discriminant D with U(N+1) ≡ 0 (mod N) and gcd(U((N+1)/q), N) = 1 for each prime q dividing F, then N is prime; if no such sequence exists for a given P and Q, a new P‘ and Q‘ with the same D can be computed as P‘ = P + 2 and Q‘ = P + Q + 1 (the same D must be used for all the factors q).
Your task is to write a program that proves the primality of a number. 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.
Programming Praxis 