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
