Instytut Matematyczny Polskiej Akademii Nauk / Institute of Mathematics / Publishing house / Banach Center Publications / All volumes

Abstract

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.