Alexander Kruppa <[EMAIL PROTECTED]> observes:
> Hi,
>
> the Lucas-Lehmer iteration
>
> L_0 = 4
> L_{n+1} = L_n ^2 -2
>
> looks suspiciously like an iteration used in Pollard-Rho:
>
> x_0 = a
> x_{n+1} = x_n ^2 +b
>
> Can this be used to do a LL test and Pollard-rho factoring attempt at
> once?
> I remember faintly having read something that b=-2 is not a good choice
> for Pollard-rho, but I don't remember any explanation why.. would it
> work here?
If L_0 = alpha + 1/alpha (where alpha = 2 + sqrt(3) is found
by solving a quadratic) then
L_n = alpha^(2^n) + alpha^(-2^n)
L_m - L_n = alpha^(2^m) + alpha^(-2^m) - alpha^(2^n) - alpha^(-2^n)
= (alpha^(2^m) - alpha^(2^n)) + (1 - alpha^(-2^m - 2^n))
If p is a factor of the number we are trying to factor, then
the order of alpha will divide one of p+1 and p-1
(depending upon whether alpha is in the base field GF(p)
or the extension field GF(p^2)).
The size of this order will be O(p).
m and n will usually need to have size O(p) before we achieve
alpha^(2^m) == alpha^(+- 2^n) (mod p)
(which is the same as 2^m == +- 2^n (mod (order of alpha)) ).
When b <> 0, -2, we know no such formula for the iterates of Pollard
Rho. x -> x^2 + b (mod p) seems to behave like a pseudorandom function
modulo p, and Pollard Rho takes O(sqrt(p)) iterations rather than O(p).
For Lucas-Lehmer, when p = 2^q - 1 is a Mersenne prime, p+1 is
divisible by a very high :-) power of 2. The L_n values collapse to
0, -2, 2, 2, ... as alpha^(2^n) becomes sqrt(-1), -1, 1 in GF(p^2).
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
