A Probabilistic Factorization Algorithm with Quadratic Forms of Negative Discriminant

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}$.