Montgomery, Peter L. Speeding the Pollard and elliptic curve methods of factorization. (English) Zbl 0608.10005 Math. Comput. 48, 243-264 (1987). Summary: Since 1974, several algorithms have been developed that attempt to factor a large number \(N\) by doing extensive computations modulo \(N\) and occasionally taking GCDs with \(N\). These began with Pollard’s \(p-1\) and Monte Carlo methods. More recently, Williams published a \(p+1\) method, and Lenstra discovered an elliptic curve method (ECM). We present ways to speed all of these. One improvement uses two tables during the second phases of \(p\pm 1\) and ECM, looking for a match. Polynomial preconditioning lets us search a fixed table of size \(n\) with \(n/2+o(n)\) multiplications. A parametrization of elliptic curves lets Step 1 of ECM compute the \(x\)-coordinate of \(nP\) from that of \(P\) in about \(9.3\, \log_2n\) multiplications for arbitrary \(P\). Cited in 8 ReviewsCited in 159 Documents MSC: 11Y05 Factorization 11A51 Factorization; primality 11Y16 Number-theoretic algorithms; complexity 14H52 Elliptic curves Keywords:factorization; polynomial evaluation; computational number theory; Lucas functions; elliptic curve PDFBibTeX XMLCite \textit{P. L. Montgomery}, Math. Comput. 48, 243--264 (1987; Zbl 0608.10005) Full Text: DOI