A+ CATEGORY SCIENTIFIC UNIT

PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

Integer factoring problem and elliptic curves over the ring $\mathbb Z_n$

Volume 159 / 2020

Robert Dryło, Jacek Pomykała Colloquium Mathematicum 159 (2020), 259-284 MSC: Primary 11Y05, 14H52, 11G07; Secondary 11A15, 11Y16. DOI: 10.4064/cm7661-2-2019 Published online: 28 November 2019

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

Authors

  • Robert DryłoInstitute of Mathematics and Cryptology
    Military University of Technology
    Urbanowicza 2
    00-908 Warszawa, Poland
    e-mail
  • Jacek PomykałaInstitute of Mathematics
    Warsaw University
    Banacha 2
    02-097 Warszawa, Poland
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image