Talk:Lucas-Lehmer-Riesel test

From Wikipedia, the free encyclopedia

'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 Penné' —Preceding unsigned comment added by Fivemack (talk • contribs) 17:26, 23 January 2008 (UTC)