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