Discrete Logarithms and Factoring

Abstract

This note discusses the relationship between the two problems of the title. We present probabilistic polynomial-time reductions that show: <br />1) To factor <i>n</i>, it suffices to be able to compute discrete logarithms modulo <i>n</i>. <br />2) To compute a discrete logarithm modulo a prime power <i>p^(e)</i>, it suffices to know it mod <i>p</i>. <br />3) To compute a discrete logarithm modulo any <i>n</i>, it suffices to be able to factor and compute discrete logarithms modulo primes. <p>To summarize: solving the discrete logarithm problem for a composite modulus is exactly as hard as factoring and solving it modulo primes