Divisors in residue classes
Author:
H. W. Lenstra
Journal:
Math. Comp. 42 (1984), 331340
MSC:
Primary 11Y05; Secondary 11A51, 11N69
MathSciNet review:
726007
Fulltext 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 , , . 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 . The algorithm treated in the paper has applications in computational number theory.
 [1]
H.
Alt, Square rooting is as difficult as multiplication,
Computing 21 (1978/79), no. 3, 221–232
(English, with German summary). MR 620210
(82m:68081), http://dx.doi.org/10.1007/BF02253055
 [2]
John
Brillhart, D.
H. Lehmer, and J.
L. Selfridge, New primality criteria and
factorizations of 2^{𝑚}±1, Math.
Comp. 29 (1975),
620–647. MR 0384673
(52 #5546), http://dx.doi.org/10.1090/S00255718197503846731
 [3]
H.
Cohen and H.
W. Lenstra Jr., Primality testing and Jacobi
sums, Math. Comp. 42
(1984), no. 165, 297–330. MR 726006
(86g:11078), http://dx.doi.org/10.1090/S0025571819840726006X
 [4]
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
(81i:10002)
 [5]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [6]
R.
Sherman Lehman, Factoring large integers, Math. Comp. 28 (1974), 637–646. MR 0340163
(49 #4919), http://dx.doi.org/10.1090/S00255718197403401632
 [7]
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
(84c:10002)
 [8]
F. J. MacWilliams & N. J. A. Sloane, The Theory of ErrorCorrecting Codes, NorthHolland, Amsterdam, 1978.
 [9]
R. Y. Pinter, Using Hyperbolic Tangents in Integer Factoring, thesis, M.I.T., Cambridge, Mass., 1980.
 [1]
 H. Alt, "Square rooting is as difficult as multiplication," Computing, v. 21, 1979, pp. 221232. MR 620210 (82m:68081)
 [2]
 J. Brillhart, D. H. Lehmer & J. L. Selfridge, "New primality criteria and factorizations of ," Math. Comp., v. 29, 1975, pp. 620647; pp. 112139 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. 297330. 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., AddisonWesley, Reading, Mass., 1981. MR 633878 (83i:68003)
 [6]
 R. S. Lehman, "Factoring large integers," Math. Comp., v. 28, 1974, pp. 637646. 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 ErrorCorrecting Codes, NorthHolland, 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
DOI:
http://dx.doi.org/10.1090/S00255718198407260071
PII:
S 00255718(1984)07260071
Keywords:
Divisors,
residue classes,
coding theory,
computational number theory
Article copyright:
© Copyright 1984
American Mathematical Society
