# Discrete Logarithms and Factoring

### Eric Bach

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-84-186

June 1984

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186.pdf

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.

BibTeX citation:

@techreport{Bach:CSD-84-186, Author = {Bach, Eric}, Title = {Discrete Logarithms and Factoring}, Institution = {EECS Department, University of California, Berkeley}, Year = {1984}, Month = {Jun}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1984/5973.html}, Number = {UCB/CSD-84-186}, 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.} }

EndNote citation:

%0 Report %A Bach, Eric %T Discrete Logarithms and Factoring %I EECS Department, University of California, Berkeley %D 1984 %@ UCB/CSD-84-186 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1984/5973.html %F Bach:CSD-84-186