View Single Post
Old 2003-06-05, 19:05   #1

243410 Posts
Default Math of LLR(written by Jean Penne)

Jean writes,
The algorithm used by LLR is a generalization of the Lucas-Lehmer algorithm, used to test the primality of the Mersenne numbers. I name this algorithm the Lucas-Lehmer-Riesel algorithm because it is explained and demonstrated in an article by Hans Riesel : "Lucasian Criteria for the Primality of N=h*2^n-1" Mathematics of Computation, Vol. 23 #108, pp. 869-875, Oct. 1969

The main theoretical fact is contained in the Theorem 5
(Lucas'Criteria for h*2^n-1) :

Suppose that n=2, h is odd
A =( (a+b*sqrt(D))^2)/r, Jacobi(D,N) = -1, and Jacobi(r,N)*sign(a^2-b^2*D) = -1. Then, a necessary and sufficient condition that N shall be prime is that

u(n-2) == 0 (mod. N)

if u(n) = u^2(n-1) - 2 with u(0) = A^h + A^-h.

How to use that ?

The number u(0) can be computed using a well known recursion formula :

v(0) = 2, v(1) = A+A^-1, v(k) = v(1)*v(k-1) - v(k-2).
so, we obtain u(0) = v(h) .

The remaining problem is to found a value for v(1) .

The numbers A and A^-1 are units of the quadratic field K(sqrt(D))
(that is to say units of the ring of the integers of this field...).
So, they are powers of the fundamental unit of the field.
Instead of choosing a square free integer D and searching for units
satisfying the conditions of theorem 5, Riesel takes increasing values
for v(1), and, remarking that A and A^-1 are the roots of the
equation :
A^2 - v(1)*A + 1 = 0

computes D as the square free part of v^2(1) - 4.

It remains to verify that the resulting D, a, b and r values
satisfy the conditions of theorem 5. The value of v(1)
so found is the smallest possible.


Chris Nash on the subject