## Divisors in residue classes

HTML articles powered by AMS MathViewer

- by H. W. Lenstra PDF
- Math. Comp.
**42**(1984), 331-340 Request permission

## 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

- H. Alt,
*Square rooting is as difficult as multiplication*, Computing**21**(1978/79), no. 3, 221–232 (English, with German summary). MR**620210**, DOI 10.1007/BF02253055 - 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 - H. Cohen and H. W. Lenstra Jr.,
*Primality testing and Jacobi sums*, Math. Comp.**42**(1984), no. 165, 297–330. MR**726006**, DOI 10.1090/S0025-5718-1984-0726006-X - G. H. Hardy and E. M. Wright,
*An introduction to the theory of numbers*, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR**568909** - Donald E. Knuth,
*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR**633878** - R. Sherman Lehman,
*Factoring large integers*, Math. Comp.**28**(1974), 637–646. MR**340163**, DOI 10.1090/S0025-5718-1974-0340163-2 - H. W. Lenstra Jr. and R. Tijdeman (eds.),
*Computational methods in number theory. Part I*, Mathematical Centre Tracts, vol. 154, Mathematisch Centrum, Amsterdam, 1982. MR**700254**
F. J. MacWilliams & N. J. A. Sloane,

*The Theory of Error-Correcting Codes*, North-Holland, Amsterdam, 1978. R. Y. Pinter,

*Using Hyperbolic Tangents in Integer Factoring*, thesis, M.I.T., Cambridge, Mass., 1980.

## Additional Information

- © Copyright 1984 American Mathematical Society
- Journal: Math. Comp.
**42**(1984), 331-340 - MSC: Primary 11Y05; Secondary 11A51, 11N69
- DOI: https://doi.org/10.1090/S0025-5718-1984-0726007-1
- MathSciNet review: 726007