Generation of elements with small modular squares and provably fast integer factoring algorithms

Author:
Brigitte Vallée

Journal:
Math. Comp. **56** (1991), 823-849

MSC:
Primary 11Y05; Secondary 68Q25

DOI:
https://doi.org/10.1090/S0025-5718-1991-1068808-2

MathSciNet review:
1068808

Full-text PDF

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 polynomial-time 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]**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., Springer-Verlag, New York, 1980. MR**606931 (82m:10001)****[3]**J. D. Dixon,*Asymptotically fast factorization of integers*, Math. Comp.**36**(1981), 255-260. MR**595059 (82a:10010)****[4]**M. A. Morrison and J. Brillhart,*A method of factoring and the factorization of*, Math. Comp.**29**(1975), 183-205. 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. 89-139. MR**700260 (84i:10005)****[6]**C. Pomerance,*Fast, rigorous factorization and discrete logarithm algorithms*, Proc. Japan-U.S. Joint Seminar, Discrete Algorithms and Complexity, Academic Press, 1987, pp. 119-143. 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. 67-79. MR**825590 (87d:11098)****[8]**B. Vallée, M. Girault, and Ph. Toffin,*How to guess l-th roots modulo n by reducing lattice bases*, Proc. AAECC-6, Roma 1988, Lecture Notes in Comput. Sci., vol. 357, Springer, 1989, pp. 427-442. MR**1008518 (90k:11168)****[9]**B. Vallée,*Provably fast integer factoring with quasi-uniform small quadratic residues*, Proc. 21st ACM Sympos. on Theory of Computing, Seattle, 1989, pp. 98-106.

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y05,
68Q25

Retrieve articles in all journals with MSC: 11Y05, 68Q25

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1991-1068808-2

Article copyright:
© Copyright 1991
American Mathematical Society