Generation of elements with small modular squares and provably fast integer factoring algorithms
Author:
Brigitte Vallée
Journal:
Math. Comp. 56 (1991), 823849
MSC:
Primary 11Y05; Secondary 68Q25
MathSciNet review:
1068808
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Finding small modular squares, when the modulus is a large composite number of unknown factorization, is almost certainly a computationally hard problem. This problem arises in a natural way when factoring the modulus by the use of congruences of squares. We study here, with the help of lattices, the set of elements whose squares are small enough, less than . We obtain a precise description of the gaps between such elements, and we develop two polynomialtime algorithms that find elements with small modular squares. The first is a randomized algorithm that generates such elements in a near uniform way. We use it to derive a class of integer factorization algorithms, the fastest of which provides the best rigorously established probabilistic complexity bound for integer factorization algorithms. The second algorithm is deterministic and often finds, amongst the neighbors of a given point, the nearest one that has a small modular square.
 [1]
Tom
M. Apostol, Modular functions and Dirichlet series in number
theory, SpringerVerlag, New YorkHeidelberg, 1976. Graduate Texts in
Mathematics, No. 41. MR 0422157
(54 #10149)
 [2]
Harold
Davenport, Multiplicative number theory, 2nd ed., Graduate
Texts in Mathematics, vol. 74, SpringerVerlag, New YorkBerlin, 1980.
Revised by Hugh L. Montgomery. MR 606931
(82m:10001)
 [3]
John
D. Dixon, Asymptotically fast factorization of
integers, Math. Comp. 36
(1981), no. 153, 255–260. MR 595059
(82a:10010), http://dx.doi.org/10.1090/S00255718198105950591
 [4]
Michael
A. Morrison and John
Brillhart, A method of factoring and the
factorization of 𝐹₇, Math.
Comp. 29 (1975),
183–205. Collection of articles dedicated to Derrick Henry Lehmer on
the occasion of his seventieth birthday. MR 0371800
(51 #8017), http://dx.doi.org/10.1090/S00255718197503718005
 [5]
C.
Pomerance, Analysis and comparison of some integer factoring
algorithms, Computational methods in number theory, Part I, Math.
Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982,
pp. 89–139. MR 700260
(84i:10005)
 [6]
Carl
Pomerance, Fast, rigorous factorization and discrete logarithm
algorithms, Discrete algorithms and complexity (Kyoto, 1986)
Perspect. Comput., vol. 15, Academic Press, Boston, MA, 1987,
pp. 119–143. MR 910929
(88m:11109)
 [7]
Carl
Pomerance, The quadratic sieve factoring algorithm, Advances
in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209,
Springer, Berlin, 1985, pp. 169–182. MR 825590
(87d:11098), http://dx.doi.org/10.1007/3540397574_17
 [8]
Brigitte
Vallée, Marc
Girault, and Philippe
Toffin, How to guess 𝑙th roots modulo 𝑛 by reducing
lattice bases, Applied algebra, algebraic algorithms and
errorcorrecting codes (Rome, 1988), Lecture Notes in Comput. Sci.,
vol. 357, Springer, Berlin, 1989, pp. 427–442. MR 1008518
(90k:11168), http://dx.doi.org/10.1007/3540510834_78
 [9]
B. Vallée, Provably fast integer factoring with quasiuniform small quadratic residues, Proc. 21st ACM Sympos. on Theory of Computing, Seattle, 1989, pp. 98106.
 [1]
 T. M. Apostol, Modular functions and Dirichlet series in number theory, Springer, New York, 1976. MR 0422157 (54:10149)
 [2]
 H. Davenport, Multiplicative number theory, 2nd ed., SpringerVerlag, New York, 1980. MR 606931 (82m:10001)
 [3]
 J. D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), 255260. MR 595059 (82a:10010)
 [4]
 M. A. Morrison and J. Brillhart, A method of factoring and the factorization of , Math. Comp. 29 (1975), 183205. MR 0371800 (51:8017)
 [5]
 C. Pomerance, Analysis and comparison of some integer factoring algorithms, Computational Methods in Number Theory: Part I, Math. Centre Tract, no. 154, 1982, pp. 89139. MR 700260 (84i:10005)
 [6]
 C. Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Proc. JapanU.S. Joint Seminar, Discrete Algorithms and Complexity, Academic Press, 1987, pp. 119143. MR 910929 (88m:11109)
 [7]
 , The quadratic sieve factoring algorithm, Advances in Cryptology, Proc. Eurocrypt 84, Paris 1984 (T. Beth, N. Cot, and I. Ingemarsson, eds.), Lecture Notes in Comput. Sci., vol. 209, Springer, 1985, pp. 6779. MR 825590 (87d:11098)
 [8]
 B. Vallée, M. Girault, and Ph. Toffin, How to guess lth roots modulo n by reducing lattice bases, Proc. AAECC6, Roma 1988, Lecture Notes in Comput. Sci., vol. 357, Springer, 1989, pp. 427442. MR 1008518 (90k:11168)
 [9]
 B. Vallée, Provably fast integer factoring with quasiuniform small quadratic residues, Proc. 21st ACM Sympos. on Theory of Computing, Seattle, 1989, pp. 98106.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11Y05,
68Q25
Retrieve articles in all journals
with MSC:
11Y05,
68Q25
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718199110688082
PII:
S 00255718(1991)10688082
Article copyright:
© Copyright 1991
American Mathematical Society
