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
DOI:
https://doi.org/10.1090/S0025-5718-07-02007-8
Published electronically:
May 14, 2007
MathSciNet review:
2353965
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: Let be integers satisfying
,
,
, and let
. Lenstra showed that the number of integer divisors of
equivalent to
is upper bounded by
. We re-examine this problem, showing how to explicitly construct all such divisors, and incidentally improve this bound to
.
- 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. 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, https://doi.org/10.1007/3-540-49649-1_3
- 3. John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of 2^{𝑚}±1, Math. Comp. 29 (1975), 620–647. MR 384673, https://doi.org/10.1090/S0025-5718-1975-0384673-1
- 4. 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, https://doi.org/10.1007/3-540-68339-9_16
- 5. 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
- 6. 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, https://doi.org/10.1007/BFb0024458
- 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. 42 (1984), no. 165, 331–340. MR 726007, https://doi.org/10.1090/S0025-5718-1984-0726007-1
- 9. 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, https://doi.org/10.1007/BF01457454
- 10. 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, https://doi.org/10.1007/978-3-642-60408-9_15
- 11. Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158
- 12. V. Shoup, NTL: A Library for doing Number Theory (version 4.0a), www.shoup.net
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
Email:
dcopper@idaccr.org
Nick Howgrave-Graham
Affiliation:
NTRU Cryptosystems, 35 Nagog Park, Acton, Massachusetts 01720
Email:
nhowgravegraham@ntru.com
S. V. Nagaraj
Affiliation:
66 Venkatrangam Street, Triplicane, Chennai 600 005, India
Email:
svn1999@eth.net
DOI:
https://doi.org/10.1090/S0025-5718-07-02007-8
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