Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

A probabilistic factorization algorithm with quadratic forms of negative discriminant
HTML articles powered by AMS MathViewer

by Martin Seysen PDF
Math. Comp. 48 (1987), 757-780 Request permission

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
Similar Articles
Additional Information
  • © Copyright 1987 American Mathematical Society
  • Journal: Math. Comp. 48 (1987), 757-780
  • MSC: Primary 11Y05; Secondary 11E32, 68Q25
  • DOI: https://doi.org/10.1090/S0025-5718-1987-0878705-X
  • MathSciNet review: 878705