Discrete Logarithms and Factoring

Eric Bach

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-84-186

, 1984

http://www2.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},
    Year= {1984},
    Month= {Jun},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5973.html
%F Bach:CSD-84-186