Divisors in residue classes, constructively

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

doi:10.1090/S0025-5718-07-02007-8

Divisors in residue classes, constructively
HTML articles powered by AMS MathViewer

by Don Coppersmith, Nick Howgrave-Graham and S. V. Nagaraj;

Math. Comp. 77 (2008), 531-545

DOI: https://doi.org/10.1090/S0025-5718-07-02007-8

Published electronically: May 14, 2007

PDF | Request permission

Abstract:

Let $r,s,n$ be integers satisfying $0 \leq r < s < n$, $s \geq n^{\alpha }$, $\alpha > 1/4$, and let $\gcd (r,s)=1$. Lenstra showed that the number of integer divisors of $n$ equivalent to $r \pmod s$ is upper bounded by $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((\alpha -1/4)^{-3/2})$.

References

D. J. Bernstein, Reducing lattice bases to find small-height values of univariate polynomials, in “Surveys in algorithmic number theory”, Mathematical Sciences Research Institute Publications, Vol. 44, Cambridge University Press (to appear).
Dan Boneh, Glenn Durfee, and Yair Frankel, An attack on RSA given a small fraction of the private key bits, Advances in cryptology—ASIACRYPT’98 (Beijing), Lecture Notes in Comput. Sci., vol. 1514, Springer, Berlin, 1998, pp. 25–34. MR 1726151, DOI 10.1007/3-540-49649-1_{3}
John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^{m}\pm 1$, Math. Comp. 29 (1975), 620–647. MR 384673, DOI 10.1090/S0025-5718-1975-0384673-1
Don Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known, Advances in cryptology—EUROCRYPT ’96 (Saragossa, 1996) Lecture Notes in Comput. Sci., vol. 1070, Springer, Berlin, 1996, pp. 178–189. MR 1421585, DOI 10.1007/3-540-68339-9_{1}6
Henri Cohen, Diviseurs appartenant à une même classe résiduelle, Seminar on number theory, 1982–1983 (Talence, 1982/1983) Univ. Bordeaux I, Talence, 1983, pp. Exp. No. 16, 12 (French). MR 750317
Nicholas Howgrave-Graham, Finding small roots of univariate modular equations revisited, Cryptography and coding (Cirencester, 1997) Lecture Notes in Comput. Sci., vol. 1355, Springer, Berlin, 1997, pp. 131–142. MR 1660500, DOI 10.1007/BFb0024458
N. A. Howgrave-Graham, Computational mathematics inspired by RSA, Ph.D. thesis, University of Bath, UK. 1999.
H. W. Lenstra Jr., Divisors in residue classes, Math. Comp. 42 (1984), no. 165, 331–340. MR 726007, DOI 10.1090/S0025-5718-1984-0726007-1
A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
Sergei Konyagin and Carl Pomerance, On primes recognizable in deterministic polynomial time, The mathematics of Paul Erdős, I, Algorithms Combin., vol. 13, Springer, Berlin, 1997, pp. 176–198. MR 1425185, DOI 10.1007/978-3-642-60408-9_{1}5
Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158, DOI 10.1007/978-1-4684-9316-0
V. Shoup, NTL: A Library for doing Number Theory (version 4.0a), www.shoup.net