View Single Post
 2003-06-05, 19:05 #1 TTn   243410 Posts 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. Regards, Jean. Chris Nash on the subject MATH