Gerhard Niklasch on Fri, 9 Apr 1999 14:40:04 +0200 (MET DST)
Re: ECM code in PARI  In response to: > Message-Id: <> > Date:
Thu, 08 Apr 1999 19:30:24 -0400 > From: (Bill Daly)  > 1.
Computing (n)P > The code uses Peter Montgomery's PRAC algorithm
to create a Lucas chain > for the purpose of computing (n)P.
However, this algorithm was designed > to handle calculations
based on a recursion of the form >   x[m+n] = f(x[m], x[n],
x[m-n]) > on the assumption that all three parameters are
required to calculate f.  And the implementation heavily
exploits the fact that we can get by with just the first two
parameters in the present context -- there are rather fewer
subcases, several subcases need fewer operations, etc.  > Since
in general an addition chain is slightly shorter > than a Lucas
chain, it would make sense to switch to an addition chain >
approach.  Yep, but do we want to go to great lengths to either
store precomputed addition chains for thousands of multipliers,
or re-establish them on the fly?  PRAC a