정의
법 \(m\)에 대한 원시근 \(g\)가 존재할 때, \((a,m)=1\)인 정수 \(a\)에 대해
- [math]\displaystyle{ g^i \equiv a\pmod m }[/math]
인 정수 \(i\;(0\le i < \phi(m))\)를 이산로그(discrete logarithm) 또는 지수(index)라고 하고 \(\operatorname{ind}_g a\), 또는 \(\log_g a\)로 표기한다. 이때 \(\phi(m)\)은 오일러 피 함수를 나타낸다.
존재성과 유일성
법 \(m\)에 대한 원시근 \(g\)가 존재할 때, \((a,m)=1\)인 정수 \(a\)에 대해 이산로그 \(\operatorname{ind}_g a\)는 존재하고 유일하다.
성질
- \(\operatorname{ind}_g 1 = 0\), \(\operatorname{ind}_g g =1\)
- \(a\equiv b\pmod m\)일 필요충분조건은 \(\operatorname{ind}_g a = \operatorname{ind}_g b\)이다.
- \(\operatorname{ind}_g ab\equiv \operatorname{ind}_g a + \operatorname{ind}_g b\pmod{\phi(m)}\)
- \(\operatorname{ind}_g a^n \equiv n\operatorname{ind}_g a\pmod{\phi(m)}\)