이산로그

이산로그(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{array}{c}b=c^x\\ a=b^y\\ a=c^z\end{array}$

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

알고리즘 목록

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