On factoring and power divisor problems via rank-3 lattices and the second vector

We propose a deterministic algorithm based on Coppersmith’s method that employs a rank-3 lattice to address factoring-related problems. An interesting aspect of our approach is that we utilize the second vector in the Lenstra–Lenstra–Lovász (LLL)-reduced basis to avoid trivial collisions in the Baby-step Giant-step method, rather than the shortest vector as is commonly used in the literature. Our results are as follows: - Compared to the result by Harvey and Hittmeir [Math. Comp. 91 (2022), pp. 1367–1379], who achieved a complexity of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis StartFraction upper N Superscript 1 slash 5 Baseline log Superscript 16 slash 5 Baseline upper N Over left-parenthesis log log upper N right-parenthesis Superscript 3 slash 5 Baseline EndFraction right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mfrac> <mml:mrow> <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>5</mml:mn> </mml:mrow> </mml:msup> <mml:msup> <mml:mi>log</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>16</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>5</mml:mn> </mml:mrow> </mml:msup> <mml:mo> ⁡ </mml:mo> <mml:mi>N</mml:mi> </mml:mrow> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>N</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>3</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>5</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mfrac> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">O\left ( \frac {N^{1/5} \log ^{16/5} N}{(\log \log N)^{3/5}} \right )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for factoring a semiprime <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N equals p q"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> <mml:mi>q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">N = pq</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , we demonstrate that in the balanced <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p"> <mml:semantics> <mml:mi>p</mml:mi> <mml:annotation encoding="application/x-tex">p</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="q"> <mml:semantics> <mml:mi>q</mml:mi> <mml:annotation encoding="application/x-tex">q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> case, the complexity can be improved to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis StartFraction upper N Superscript 1 slash 5 Baseline log Superscript 13 slash 5 Baseline upper N Over left-parenthesis log log upper N right-parenthesis Superscript 3 slash 5 Baseline EndFraction right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mfrac> <mml:mrow> <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>5</mml:mn> </mml:mrow> </mml:msup> <mml:msup> <mml:mi>log</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>13</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>5</mml:mn> </mml:mrow> </mml:msup> <mml:mo> ⁡ </mml:mo> <mml:mi>N</mml:mi> </mml:mrow> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>N</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>3</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>5</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mfrac> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">O\left ( \frac {N^{1/5} \log ^{13/5} N}{(\log \log N)^{3/5}} \right )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . - For factoring sums and differences of powers, i.e., numbers of the form