Re: ECM code in PARI

[Paul.Zimmermann@loria.fr (Paul Zimmermann)]

	Dear Bill,

Guillaume Hanrot forwarded your mail to me. Computing (n)P is useful when
one uses precisely homogeneous coordinates. In that case the formulas
without inversion require that one knows also x[m-n]. See formulas (6) and
(7) in:

@Article{Brent99,
  author = 	 "Richard P. Brent",
  title = 	 "Factorization of the tenth {F}ermat number",
  journal =	 MC,
  year =	 1999,
  volume =	 68,
  number =	 225,
  month =	 jan,
  pages =	 "429--451"
}

This also solves your second remark (Avoiding invmod). All this, with
a few other improvements, is implemented in gmp-ecm [1] and is described
in the file all.ps.gz in the same directory.

As an example, gmp-ecm on a PII-450 takes about 115s for step 1 with 
B1=10^6 and 48s for step 2 with B2=10^8, for a c120:

jouy% ecm -e 1 1000000 < c120
GMP-ECM 3b, by P. Zimmermann (Inria), 17 Nov 1998, with contributions from
T. Granlund, P. Leyland, C. Curry, A. Stuebinger, G. Woltman, JC. Meyrignac.
... and the invaluable help from P.L. Montgomery.
Input number is 265535466579688604805851295242389350646124229512840469920696404242681668380354424870495084413250865968329058772250534133 (120 digits)
Using B1=1000000, B2=100000000, polynomial x^1, sigma=2102745767
Step 1 took 115370ms for 12982265 muls, 3 gcdexts
Step 2 took 48340ms for 4921535 muls, 8195 gcdexts

The 'gcdexts' are modular inversion (only 3 in step 1).

Regards,
Paul

[1] http://www.loria.fr/~zimmerma/records/ecmnet.html