Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



A probabilistic factorization algorithm with quadratic forms of negative discriminant

Author: Martin Seysen
Journal: Math. Comp. 48 (1987), 757-780
MSC: Primary 11Y05; Secondary 11E32, 68Q25
MathSciNet review: 878705
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We propose a probabilistic algorithm for factorization of an integer N with run time ${(\exp \sqrt {\log N\log \log N} )^{\sqrt {5/4} + o(1)}}$. Asymptotically, our algorithm will be as fast as the well-known factorization algorithm of Morrison and Brillhart. The latter algorithm will fail in several cases and heuristic assumptions are needed for its run time analysis. Our new algorithm will be analyzed under the assumption of the Extended Riemann Hypothesis and it will be of Las Vegas type. On input N, the new algorithm will factor N with probability $\geqslant \frac {1}{2}$. In case of prime N the algorithm will prove the primality of N with probability $\geqslant \frac {1}{2}$.

References [Enhancements On Off] (What's this?)

Similar Articles

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

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

Additional Information

Article copyright: © Copyright 1987 American Mathematical Society