Divisors in residue classes, constructively
Don Coppersmith, Nick Howgrave-Graham, S. V. Nagaraj · Mathematics of Computation · 2007
Let r , s , n r,s,n be integers satisfying 0 ≤ r > s > n 0 \leq r > s > n , s ≥ n α s \geq n^{\alpha } , α > 1 / 4 \alpha > 1/4 , and let gcd ( r , s ) = 1 \gcd (r,s)=1 . Lenstra showed that the number of integer divisors of n n equivalent to r ( mod s ) r \pmod s is upper bounded by O ( ( α − 1 / 4 ) − 2 ) O((\alpha -1/4)^{-2}) . We re-examine this problem, showing how to explicitly construct all such divisors, and incidentally improve this bound to O ( ( α − 1 / 4 ) − 3 /