Generation of elements with small modular squares and provably fast integer factoring algorithms
HTML articles powered by AMS MathViewer
- by Brigitte Vallée PDF
- Math. Comp. 56 (1991), 823-849 Request permission
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 $\bmod n$ are small enough, less than $O({n^{2/3}})$. 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.References
- Tom M. Apostol, Modular functions and Dirichlet series in number theory, Graduate Texts in Mathematics, No. 41, Springer-Verlag, New York-Heidelberg, 1976. MR 0422157, DOI 10.1007/978-1-4684-9910-0
- 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, DOI 10.1007/978-1-4757-5927-3
- John D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), no. 153, 255–260. MR 595059, DOI 10.1090/S0025-5718-1981-0595059-1
- Michael A. Morrison and John Brillhart, A method of factoring and the factorization of $F_{7}$, Math. Comp. 29 (1975), 183–205. MR 371800, DOI 10.1090/S0025-5718-1975-0371800-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
- 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
- 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, DOI 10.1007/3-540-39757-4_{1}7
- Brigitte Vallée, Marc Girault, and Philippe Toffin, How to guess $l$th roots modulo $n$ 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, DOI 10.1007/3-540-51083-4_{7}8 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.
Additional Information
- © Copyright 1991 American Mathematical Society
- 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