Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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 $ \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 [Enhancements On Off] (What's this?)

Similar Articles

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

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

Additional Information

Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society