Paul Zimmermann on Fri, 9 Apr 1999 12:21:13 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: ECM code in PARI |
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