A Monte Carlo factoring algorithm with linear storage

Abstract

We present an algorithm which will factor an integer <italic>n</italic> quite efficiently if the class number <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h left-parenthesis negative n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>h</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mo>−<!-- − --></mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">h( - n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is free of large prime divisors. The running time <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>T</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">T(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> (number of compositions in the class group) satisfies <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p r o b left-bracket upper T left-parenthesis m right-parenthesis less-than-or-slanted-equals n Superscript 1 slash 2 r Baseline right-bracket greater-than-or-equivalent-to left-parenthesis r minus 2 right-parenthesis Superscript minus left-parenthesis r minus 2 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>prob</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mo stretchy="false">[</mml:mo> <mml:mi>T</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>m</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>⩽<!-- ⩽ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mi>r</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo stretchy="false">]</mml:mo> <mml:mo>≳<!-- ≳ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>r</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>2</mml:mn> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>r</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>2</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\operatorname {prob}[T(m) \leqslant {n^{1/2r}}] \gtrsim {(r - 2)^{ - (r - 2)}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for random <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m element-of left-bracket n slash 2 comma n right-bracket"> <mml:semantics> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mo stretchy="false">[</mml:mo> <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>n</mml:mi> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">m \in [n/2,n]</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r greater-than-or-slanted-equals 2"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>⩾<!-- ⩾ --></mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">r \geqslant 2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. So far it is unpredictable which numbers will be factored fast. Running the algorithm on all discriminants - <italic>ns</italic> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="s less-than-or-slanted-equals r Superscript r"> <mml:semantics> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>⩽<!-- ⩽ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>r</mml:mi> <mml:mi>r</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">s \leqslant {r^r}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r equals StartRoot ln n slash ln ln n EndRoot"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>=</mml:mo> <mml:msqrt> <mml:mi>ln</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>ln</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>ln</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>n</mml:mi> </mml:msqrt> </mml:mrow> <mml:annotation encoding="application/x-tex">r = \sqrt {\ln n/\ln \ln n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, every composite integer <italic>n</italic> will be factored in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="o left-parenthesis exp StartRoot ln n ln ln n EndRoot right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>exp</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:msqrt> <mml:mi>ln</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>n</mml:mi> <mml:mi>ln</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>ln</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>n</mml:mi> </mml:msqrt> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">o(\exp \sqrt {\ln n\ln \ln n} )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> bit operations. The method requires an amount of storage space which is proportional to the length of the input <italic>n</italic>. In our analysis we assume a lower bound on the frequency of class numbers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h left-parenthesis negative m right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>h</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mo>−<!-- − --></mml:mo> <mml:mi>m</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">h( - m)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m less-than-or-slanted-equals n"> <mml:semantics> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>⩽<!-- ⩽ --></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">m \leqslant n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, which are free of large prime divisors.

Keywords

Related Publications