Factoring using multiplicative relations modulo n: a subexponential algorithm inspired by the index calculus

ePrint Report: Factoring using multiplicative relations modulo n: a subexponential algorithm inspired by the index calculus

Katherine E. Stange

We demonstrate that a modification of the classical index calculus algorithm can be used to factor integers. More generally, we reduce the factoring problem to finding an overdetermined system of multiplicative relations in any factor base modulo $n$, where $n$ is the integer whose factorization is sought. The algorithm has subexponential runtime $\exp(O(\sqrt{\log n \log \log n}))$ (or $\exp(O( (\log n)^{1/3} …

algorithm eprint report factoring