# 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$$.

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