Talk:Lucas–Lehmer–Riesel test

'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)

Finding b & u_0 See the paper "PRIMALITY TESTS FOR NUMBERS OF THE FORM k * 2^m +/- 1" by Zhi-Hong Sun in The Fibonacci Quarterly 44(2006), no.2, 121-130. b can be found by testing integers sequentially until one is found that satisfies Jacobi(2+b, p) = Jacobi(2-b, p) = -1 Then the starting value for u (u_0) can be computed by the Sum from 0 to k - 2 of binary-coefficient(k-r, r) * b^(k-2r) * ((-1) ^ r) * k / (k - r). — Preceding unsigned comment added by 24.6.172.74 (talk) 19:24, 21 September 2011 (UTC)

Essentially the same result was shown 12 years earlier by Rödseth. I believe his paper and method to be easier to follow and has some similarities with the method Riesel suggests in his book. Sun's use of a binomial sum rather than a Lucas sequence is interesting though would seem to be much less efficient. DAJ NT (talk) 09:22, 24 May 2015 (UTC)