Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Divisors in residue classes

Author: H. W. Lenstra
Journal: Math. Comp. 42 (1984), 331-340
MSC: Primary 11Y05; Secondary 11A51, 11N69
MathSciNet review: 726007
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper the following result is proved. Let r, s and n be integers satisfying $ 0 \leqslant r < s < n$, $ s > {n^{1/3}}$, $ \gcd (r,s) = 1$. Then there exist at most 11 positive divisors of n that are congruent to r modulo s. Moreover, there exists an efficient algorithm for determining all these divisors. The bound 11 is obtained by means of a combinatorial model related to coding theory. It is not known whether 11 is best possible; in any case it cannot be replaced by 5. Nor is it known whether similar results are true for significantly smaller values of $ \log s/\log n$. The algorithm treated in the paper has applications in computational number theory.

References [Enhancements On Off] (What's this?)

  • [1] H. Alt, "Square rooting is as difficult as multiplication," Computing, v. 21, 1979, pp. 221-232. MR 620210 (82m:68081)
  • [2] J. Brillhart, D. H. Lehmer & J. L. Selfridge, "New primality criteria and factorizations of $ {2^m} \pm 1$," Math. Comp., v. 29, 1975, pp. 620-647; pp. 112-139 in: Selected Papers of D. H. Lehmer, Vol. I, Charles Babbage Research Centre, St. Pierre, Manitoba, 1981. MR 0384673 (52:5546)
  • [3] H. Cohen & H. W. Lenstra, Jr., "Primality testing and Jacobi sums," Math. Comp., v. 42, 1984, pp. 297-330. MR 726006 (86g:11078)
  • [4] G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, Oxford, 1979. MR 568909 (81i:10002)
  • [5] D. E. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [6] R. S. Lehman, "Factoring large integers," Math. Comp., v. 28, 1974, pp. 637-646. MR 0340163 (49:4919)
  • [7] H. W. Lenstra, Jr. & R. Tijdeman (editors), Computational Methods in Number Theory, Mathematical Centre Tracts 154/155, Amsterdam, 1982. MR 700254 (84c:10002)
  • [8] F. J. MacWilliams & N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1978.
  • [9] R. Y. Pinter, Using Hyperbolic Tangents in Integer Factoring, thesis, M.I.T., Cambridge, Mass., 1980.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05, 11A51, 11N69

Retrieve articles in all journals with MSC: 11Y05, 11A51, 11N69

Additional Information

Keywords: Divisors, residue classes, coding theory, computational number theory
Article copyright: © Copyright 1984 American Mathematical Society

American Mathematical Society