Reductions among number theoretic problems (Q1091136): Difference between revisions

Many number theoretic problems such as integer factorization and the discrete logarithm problem have defined all attempts to classify their complexities. Thirteen such problems are considered, none of which is known either to have a deterministic polynomial time solution, or to be complete for any natural complexity class. Failing this, the next best goal is to determine which among these are the ''easiest'' and which are the ''hardest'' problems. Toward this end, this paper gives an overview of reductions among the problems. Two reductions are new: a deterministic polynomial time reduction from squarefreeness to Euler's function \(\phi\) (n), and a probabilistic polynomial time reduction from order modulo a prime power to discrete logarithm modulo a prime power.