Artykuły w formacie PDF dostępne są dla subskrybentów, którzy zapłacili za dostęp online, po podpisaniu licencji Licencja użytkownika instytucjonalnego. Czasopisma do 2009 są ogólnodostępne (bezpłatnie).

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

Tom 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 Opublikowany online: 28 November 2019


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


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

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek