Reductions among number theoretic problems

Many number theoretic problems such as integer factorization and the discrete logarithm problem have defied 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 φ(n), and a probabilistic polynomial time reduction from order modulo a prime power to discrete logarithm modulo a prime power.

Authors

• Heather Woll

Keywords

No keywords are indexed for this paper.