이산로그

이산로그(Discrete logarithm)는 군 $G$에서 $a,b\in G$에 대하여 $a^{x}=b$를 만족하는 $x$를 의미한다. 또한, 일반적인 로그처럼 $x=\log _{a}{b}$로 표기하기도 한다.

현재 이산로그 문제는 RSA등의 일부 공개키 암호(Public-key cryptography)에서 기반이 되고 있고, 이 문제를 다항 시간 안에 해결 하는 것은 미해결 문제로 남아있다.

양자 컴퓨터의 경우에는 쇼어 알고리즘(Shor's algorithm)을 통해서 다항 시간에 해결할 수 있다.

성질

정리 1

군 $G$에서 $a,b,c\in G$에 대하여 $\log _{c}{a}=\log _{c}{b}\log _{b}{a}$가 성립한다.

증명

${\begin{cases}b=c^{x}\\a=b^{y}\\a=c^{z}\end{cases}}$

와 같이 놓았을 때 $a=c^{xy}=c^{z}$에서 $z=xy$를 얻는다.

알고리즘 목록

• Baby-step Giant-step 알고리즘
• 폴라드-로 알고리즘
• 쇼어 알고리즘