이산로그(Discrete logarithm)는 위수가 N {\displaystyle N} 인 군 G {\displaystyle G} 에서 a , b ∈ G {\displaystyle a,b\in G} 에 대하여 a x ≡ b ( m o d N ) {\displaystyle a^{x}\equiv b\ (mod\ N)} 를 만족하는 x {\displaystyle x} 를 의미한다. 또한, 일반적인 로그처럼 x = log a b {\displaystyle x=\log _{a}{b}} 로 표기하기도 한다.
현재 이산로그 문제는 공개키 암호(Public-key cryptography)에서 기반이 되고 있고, 이 문제를 다항 시간 안에 해결 하는 것은 미해결 문제로 남아있다.
양자 컴퓨터의 경우에는 쇼어 알고리즘(Shor's algorithm)을 통해서 다항 시간에 해결할 수 있다.
군 G {\displaystyle G} 에서 a , b , c ∈ G {\displaystyle a,b,c\in G} 에 대하여 log c a = log c b log b a {\displaystyle \log _{c}{a}=\log _{c}{b}\log _{b}{a}} 가 성립한다.
{ b ≡ c x ( m o d N ) a ≡ b y ( m o d N ) a ≡ c z ( m o d N ) {\displaystyle {\begin{cases}b\equiv c^{x}\ (mod\ N)\\a\equiv b^{y}\ (mod\ N)\\a\equiv c^{z}\ (mod\ N)\end{cases}}}
와 같이 놓았을때 a ≡ c x y ≡ c z {\displaystyle a\equiv c^{xy}\equiv c^{z}} 에서 z ≡ x y {\displaystyle z\equiv xy} 를 얻는다.
