zbMATH — the first resource for mathematics

Speeding the Pollard and elliptic curve methods of factorization. (English) Zbl 0608.10005
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\).

11Y05 Factorization
11A51 Factorization; primality
11Y16 Number-theoretic algorithms; complexity
14H52 Elliptic curves
Full Text: DOI