Mersenne: LL and Pollar-rho in one?

[Alexander Kruppa]

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?

Ciao,
  Alex.
_
Unsubscribe  list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers

Re: Mersenne: LL and Pollar-rho in one?

[Alexander Kruppa]

Jason Stratos Papadopoulos wrote:
 
 On Thu, 28 Oct 1999, Alexander Kruppa wrote:
 
  Hi,
 
  the Lucas-Lehmer iteration [...]
  looks suspiciously like an iteration used in Pollard-Rho: [...]
  Can this be used to do a LL test and Pollard-rho factoring attempt at
  once?
 
 Except that every once in a while you'd have to perform a GCD, and
 a GCD on million-digit size numbers takes about a day (no kidding!
 There seems to be no fast way to do one!)

Thats true (btw, I keep hearing of a n*log(n) gcd - how long would that
take then? Where can I read up on it - Knuth vol.2 ?) but doing the
Pollard-Rho along a LL test would not be particularly efficient,
anyways. For every 2 LL iterations, you'd have to do another one for the
cycle find algorithm and a multiply to store up any factor you find -
thats 9 transforms instead of 4, so your test time will more than
double. And Pollard-Rho is probably not very well suited for finding
Mersenne factors as it cannot exploit the fact that these factor are 1
mod (2p) as P-1 can.
I'm mostly asking for curiosity, whether the LL iteration really makes a
proper Pollard-Rho iteration, especially with the -2.

Ciao,
  Alex.
_
Unsubscribe  list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ  -- http://www.tasam.com/~lrwiman/FAQ-mers