Publishing house / Journals and Serials / Colloquium Mathematicum / All issues

Abstract

We investigate the reduction of factoring of squarefree positive integers coprime to 6 to computing exponents of points on an elliptic curve $E(\mathbb Z _n)$ over the ring $\mathbb Z _n$. We contribute to an accurate estimate for the error probability of the already known randomized reduction with as much detail as appropriate.

Secondly we contribute to deterministic polynomial time reduction of factorization to computing the order of the group $E(\mathbb Z _n)$ based on different principles, which does not use the elliptic curve point multiplication. In particular we prove that if the traces of the family of elliptic curves $E(b){\ \rm mod\ } p: y^2=x^3+x+b$, $ b\le \log ^\beta p$, $ \beta \gt 3$ divisible by $d\mid p+1$, are uniformly distributed in the interval $[-2\sqrt p, 2\sqrt p] $, then the related reduction to computing the orders $|E(\mathbb Z _n)|$ runs in deterministic polynomial time (depending on $\beta $) for all RSA numbers $n=p_1p_2$, with at most $o(x\log \log x/\!\log x )$ exceptions.

Finally, we prove a result in the opposite direction: there are at least $x^{1-\varepsilon }$ numbers $n= p_1 \ldots p_s\le x$ for which more general heuristic arguments related to analogous deterministic reductions may not work. Here $\varepsilon =\varepsilon (s)=cs\log s/\!\log \log x$ for some positive constant $c$.