Divisors in residue classes, constructively

Don Coppersmith, Nick Howgrave-Graham, S. V. Nagaraj

Mathematics of Computation · 2007 · 14 citations · 4 references

DOIFull text

Open access

Concepts

Abstract

Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r comma s comma n"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>s</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">r,s,n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be integers satisfying <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="0 less-than-or-equal-to r greater-than s greater-than n"> <mml:semantics> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo> ≤ </mml:mo> <mml:mi>r</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mi>s</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">0 \leq r &gt; s &gt; n</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="s greater-than-or-equal-to n Superscript alpha"> <mml:semantics> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo> ≥ </mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi> α </mml:mi> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">s \geq n^{\alpha }</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="alpha greater-than 1 slash 4"> <mml:semantics> <mml:mrow> <mml:mi> α </mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>4</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\alpha &gt; 1/4</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="gcd left-parenthesis r comma s right-parenthesis equals 1"> <mml:semantics> <mml:mrow> <mml:mo movablelimits="true" form="prefix">gcd</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>s</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\gcd (r,s)=1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Lenstra showed that the number of integer divisors of <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> equivalent to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r left-parenthesis mod s right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mspace width="0.667em"/> <mml:mo stretchy="false">(</mml:mo> <mml:mi>mod</mml:mi> <mml:mspace width="0.333em"/> <mml:mi>s</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">r \pmod s</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is upper bounded by <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis left-parenthesis alpha minus 1 slash 4 right-parenthesis Superscript negative 2 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi> α </mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>4</mml:mn> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O((\alpha -1/4)^{-2})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We re-examine this problem, showing how to explicitly construct all such divisors, and incidentally improve this bound to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis left-parenthesis alpha minus 1 slash 4 right-parenthesis Superscript negative 3 slash 2 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi> α </mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>4</mml:mn> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>3</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow>

References

4