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]**Tom M. Apostol,*Modular functions and Dirichlet series in number theory*, Springer-Verlag, New York-Heidelberg, 1976. Graduate Texts in Mathematics, No. 41. MR**0422157****[2]**Harold Davenport,*Multiplicative number theory*, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. MR**606931****[3]**John D. Dixon,*Asymptotically fast factorization of integers*, Math. Comp.**36**(1981), no. 153, 255–260. MR**595059**, https://doi.org/10.1090/S0025-5718-1981-0595059-1**[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**, https://doi.org/10.1090/S0025-5718-1975-0371800-5**[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****[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****[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**, https://doi.org/10.1007/3-540-39757-4_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 error-correcting codes (Rome, 1988) Lecture Notes in Comput. Sci., vol. 357, Springer, Berlin, 1989, pp. 427–442. MR**1008518**, https://doi.org/10.1007/3-540-51083-4_78**[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