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