Lucas-Lehmer-Riesel test

The Lucas-Lehmer-Riesel test is a deterministic primality test for numbers of the form N = k * 2^n - 1 where k is odd and smaller than 2^n. Hans Riesel developed it, building on the Lucas-Lehmer primality test used for Mersenne numbers, and it is the fastest deterministic algorithm known for numbers of that form. The test squares a sequence defined by u(i) = u(i-1)^2 - 2 and declares N prime exactly when N divides the term u(n-2). What differs from the plain Lucas-Lehmer test is the starting value u(0), which depends on k: for k not divisible by 3 it comes from a Lucas sequence with parameter 4, and for the harder case where 3 divides k a value found through Jacobi symbols, as described by Rodseth in 1994, can be used. The method is a special case of group-order primality testing in a quadratic extension of the integers modulo N. It is implemented in the LLR program by Jean Penne, used by prime-searching projects such as Riesel Sieve and PrimeGrid, with later revisions adding verifiable proof certificates.