Factorization, malleability and equivalent problems
Tom 126 / 2023
Banach Center Publications 126 (2023), 41-51
MSC: Primary 11A51; Secondary 11G07
DOI: 10.4064/bc126-3
Streszczenie
This paper describes recent results on the factorization of integers proving, on one hand, that factorization is a malleable problem, i.e. the factorization of a given $n$ is easier when the factorization of another related number is known and, on the other hand, that factorization is polynomial time equivalent to counting points on elliptic curves modulo $n$. It also includes a new result on the equivalence between factoring $n$ and computing $\varphi (n)$ when $n$ has three prime factors.
