Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Divisors in residue classes, constructively

Authors: Don Coppersmith, Nick Howgrave-Graham and S. V. Nagaraj
Journal: Math. Comp. 77 (2008), 531-545
MSC (2000): Primary 11Y05, 11Y16, 68Q25; Secondary 11Y11, 68W40
Published electronically: May 14, 2007
MathSciNet review: 2353965
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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).
  • 2. D. Boneh, G. Durfee, Y. Frankel, An attack on RSA given a fraction of the private key bits, Proc. of Asiacrypt 98, Springer Lecture Notes in Comput. Sci., vol. 1514, pp. 25-34. MR 1726151
  • 3. J. Brillhart, D. H. Lehmer, J. L. Selfridge, New primality criteria and factorizations of $ 2^{m} \pm 1$, Math. Comp., vol. 29, 1975, pp. 620-647. MR 0384673 (52:5546)
  • 4. D. Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known, Proc. of Eurocrypt 96, Springer Lecture Notes in Comput. Sci., vol. 1070, pp. 178-189. MR 1421585 (97h:94009)
  • 5. H. Cohen, Diviseurs appartenant à une même classe résiduelle, Seminar on number theory, 1982-83, University of Bordeaux I, Talence, Exp. No. 16, 1982-1983, 12 pp. MR 750317 (85i:11002)
  • 6. N. A. Howgrave-Graham, Finding small roots of univariate modular equations revisited, Proc. of Cryptography and Coding, 1997, Springer Lecture Notes in Comput. Sci., vol. 1355, pp. 131-142. MR 1660500 (99j:94049)
  • 7. N. A. Howgrave-Graham, Computational mathematics inspired by RSA, Ph.D. thesis, University of Bath, UK. 1999.
  • 8. H. W. Lenstra, Jr., Divisors in Residue Classes, Math. Comp., vol. 42, no. 165, January 1984, pp. 331-340. MR 726007 (85b:11118)
  • 9. A. K. Lenstra, H. W. Lenstra and L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534. MR 0682664 (84a:12002)
  • 10. S. Konyagin, C. Pomerance, On primes recognizable in deterministic polynomial time, in ``The Mathematics of Paul Erdös'', Eds.: R.L. Graham, J. Nesetril, 1996. ISBN 3-540-61032-4. MR 1425185 (98a:11184)
  • 11. R. Crandall, C. Pomerance, Prime numbers: a computational perspective, Springer-Verlag, New York, NY, 2001. ISBN 0-387-94777-9. MR 1821158 (2002a:11007)
  • 12. V. Shoup, NTL: A Library for doing Number Theory (version 4.0a),

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y05, 11Y16, 68Q25, 11Y11, 68W40

Retrieve articles in all journals with MSC (2000): 11Y05, 11Y16, 68Q25, 11Y11, 68W40

Additional Information

Don Coppersmith
Affiliation: Institute for Defense Analyses, 805 Bunn Drive, Princeton, New Jersey 08540

Nick Howgrave-Graham
Affiliation: NTRU Cryptosystems, 35 Nagog Park, Acton, Massachusetts 01720

S. V. Nagaraj
Affiliation: 66 Venkatrangam Street, Triplicane, Chennai 600 005, India

Keywords: Divisors, residue classes
Received by editor(s): June 5, 2006
Received by editor(s) in revised form: November 14, 2006
Published electronically: May 14, 2007
Article copyright: © Copyright 2007 American Mathematical Society

American Mathematical Society