Speeding the Pollard and elliptic curve methods of factorization

Abstract

Since 1974, several algorithms have been developed that attempt to factor a large number <italic>N</italic> by doing extensive computations modulo <italic>N</italic> and occasionally taking GCDs with <italic>N</italic>. These began with Pollard’s <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p minus 1"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p - 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and Monte Carlo methods. More recently, Williams published a <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p plus 1"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p + 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p plus-or-minus 1"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>±</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p \pm 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and ECM, looking for a match. Polynomial preconditioning lets us search a fixed table of size <italic>n</italic> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n slash 2 plus o left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">n/2 + o(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> multiplications. A parametrization of elliptic curves lets Step 1 of ECM compute the <italic>x</italic>-coordinate of <italic>nP</italic> from that of <italic>P</italic> in about 9.3 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="log Subscript 2"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>log</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\log _2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> <italic>n</italic> multiplications for arbitrary <italic>P</italic>.