A rigorous time bound for factoring integers

Abstract

In this paper a probabilistic algorithm is exhibited that factors any positive integer<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"><mml:semantics><mml:mi>n</mml:mi><mml:annotation encoding="application/x-tex">n</mml:annotation></mml:semantics></mml:math></inline-formula>into prime factors in expected time at most<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Subscript n Baseline left-bracket one half comma 1 plus o left-parenthesis 1 right-parenthesis right-bracket"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>L</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mstyle displaystyle="false" scriptlevel="0"><mml:mfrac><mml:mn>1</mml:mn><mml:mn>2</mml:mn></mml:mfrac></mml:mstyle><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">{L_n}[\tfrac {1}{2},1 + o(1)]</mml:annotation></mml:semantics></mml:math></inline-formula>for<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n right-arrow normal infinity"><mml:semantics><mml:mrow><mml:mi>n</mml:mi><mml:mo stretchy="false">→</mml:mo><mml:mi mathvariant="normal">∞</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">n \to \infty</mml:annotation></mml:semantics></mml:math></inline-formula>, where<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Subscript x Baseline left-bracket a comma b right-bracket equals exp left-parenthesis b left-parenthesis log x right-parenthesis Superscript a Baseline left-parenthesis log log x right-parenthesis Superscript 1 minus a Baseline right-parenthesis"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>L</mml:mi><mml:mi>x</mml:mi></mml:msub></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>a</mml:mi><mml:mo>,</mml:mo><mml:mi>b</mml:mi><mml:mo stretchy="false">]</mml:mo><mml:mo>=</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mtext>exp</mml:mtext></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>b</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mi>x</mml:mi><mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mi>a</mml:mi></mml:msup></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mtext>log</mml:mtext></mml:mrow><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mi>x</mml:mi><mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mi>a</mml:mi></mml:mrow></mml:msup></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">{L_x}[a,b] = {\text {exp}}(b{(\log x)^a}{({\text {log}}\log x)^{1 - a}})</mml:annotation></mml:semantics></mml:math></inline-formula>. Many practical factoring algorithms, including the quadratic sieve and the elliptic curve method, are conjectured to have an expected running time that satisfies the same bound, but this is the first algorithm for which the bound can be rigorously proved. Nevertheless, this does not close the gap between rigorously established time bounds and merely conjectural ones for factoring algorithms. This is due to the advent of a new factoring algorithm, the number field sieve, which is conjectured to factor any positive integer<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"><mml:semantics><mml:mi>n</mml:mi><mml:annotation encoding="application/x-tex">n</mml:annotation></mml:semantics></mml:math></inline-formula>in time<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Subscript n Baseline left-bracket one third comma upper O left-parenthesis 1 right-parenthesis right-bracket"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>L</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mstyle displaystyle="false" scriptlevel="0"><mml:mfrac><mml:mn>1</mml:mn><mml:mn>3</mml:mn></mml:mfrac></mml:mstyle><mml:mo>,</mml:mo><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">{L_n}[\tfrac {1}{3},O(1)]</mml:annotation></mml:semantics></mml:math></inline-formula>. The algorithm analyzed in this paper is a variant of the class group relations method, which makes use of class groups of binary quadratic forms of negative discriminant. This algorithm was first suggested by Seysen, and later improved by A. K. Lenstra, who showed that the algorithm runs in expected time at most<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Subscript n Baseline left-bracket one half comma 1 plus o left-parenthesis 1 right-parenthesis right-bracket"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>L</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mstyle displaystyle="false" scriptlevel="0"><mml:mfrac><mml:mn>1</mml:mn><mml:mn>2</mml:mn></mml:mfrac></mml:mstyle><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">{L_n}[\tfrac {1}{2},1 + o(1)]</mml:annotation></mml:semantics></mml:math></inline-formula>if one assumes the generalized Riemann hypothesis. The main device for removing the use of the generalized Riemann hypothesis from the proof is the use of multipliers. In addition a character sum estimate for algebraic number fields is used, with an explicit dependence on possible exceptional zeros of the corresponding<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L"><mml:semantics><mml:mi>L</mml:mi><mml:annotation encoding="application/x-tex">L</mml:annotation></mml:semantics></mml:math></inline-formula>-functions. Another factoring algorithm using class groups that has been proposed is the random class groups method. It is shown that there is a fairly large set of numbers that this algorithm cannot be expected to factor as efficiently as had previously been thought.

Keywords

Affiliated Institutions

• University of California, Berkeley US
• University of Georgia US

Related Publications