이산로그

정의

법 \(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\)는 존재하고 유일하다. 이는 위수의 성질에 의한 것이다.

좀 더 자세히 설명하자면, \(g\)의 위수를 \(n\)이라 할 때, [math]\displaystyle{ g^1,\,g^2,\,\cdots,\,g^n }[/math]는 법 \(m\)에 대해 모두 다르다. 특히, \(g\)가 원시근이므로, 총 [math]\displaystyle{ \phi\left(m\right) }[/math]개의 서로다른 \(g^i\)가 존재하고, \(m\)과 서로소인 정수의 개수는 [math]\displaystyle{ \phi\left(m\right) }[/math]개이다. 그렇기 때문에 [math]\displaystyle{ \gcd\left(a,m\right)=1 }[/math]인 \(a\)에 대해 정확히 하나의 \(g^i\)에 대응하는 것.

성질

1. \(\operatorname{ind}_g 1 = 0\), \(\operatorname{ind}_g g =1\)

   \(g^0\equiv 1\pmod m\)이고 \(g^1\equiv g\pmod m\)이므로 자명하다.

2. \(a\equiv b\pmod m\)일 필요충분조건은 \(\operatorname{ind}_g a = \operatorname{ind}_g b\)이다.

   \(i=\operatorname{ind}_g a,\; j=\operatorname{ind}_g b\)라고 하자. 그러면 이산로그의 정의에 의해 \(g^i\equiv a\pmod m\)이고 \(g^j\equiv b\pmod m\)이다. \(a\equiv b\pmod m\)이면 \(\equiv\)의 추이성에 의해 \(g^i \equiv g^j\pmod m\)이고, 그러면 위수의 성질과 원시근의 정의에 의해 \(i\equiv j\pmod{\phi(m)}\)이다. 이때 \(0\le i,j < \phi(m)\)이므로 \(i-j=0\), 즉 \(i=j\)이다. 이제 \(\operatorname{ind}_g a = \operatorname{ind}_g b\)이라고 하자. \(i=\operatorname{ind}_g a = \operatorname{ind}_g b\)라 하면, \(g^i\equiv a\pmod m\)이고 \(g^i \equiv b\pmod m\)이므로 \(\equiv\)의 추이성에 의해 \(a\equiv b \pmod m\)이다.

3. \(\operatorname{ind}_g ab\equiv \operatorname{ind}_g a + \operatorname{ind}_g b\pmod{\phi(m)}\)

   \(i=\operatorname{ind}_g a,\; j=\operatorname{ind}_g b\)라고 하자. 그러면 이산로그의 정의에 의해 \(g^i\equiv a\pmod m\)이고 \(g^j\equiv b\pmod m\)이므로 [math]\displaystyle{ g^{i+j}\equiv g^i g^j \equiv ab \pmod m }[/math]이다. 이때 \(\operatorname{ind}_g ab = k\)라 하면 \(g^k \equiv ab \pmod m\)이다. 즉 \(g^{i+j}\equiv g^k\pmod m\)이므로 위수의 성질과 원시근의 정의에 의해 \(i+j \equiv k\pmod{\phi(m)}\)이고, \(i,j,k\)를 풀어쓰면 원하는 결론을 얻는다.

4. \(\operatorname{ind}_g a^n \equiv n\operatorname{ind}_g a\pmod{\phi(m)}\)

   \(\operatorname{ind}_g ab\equiv \operatorname{ind}_g a + \operatorname{ind}_g b\pmod{\phi(m)}\)임과 수학적 귀납법을 이용해 쉽게 증명할 수 있다.

수학적인 감각이 있는 사람은 이 네 성질들이 전부 로그와 비슷하다는 것을 알 수 있다. 각각 대응하는 로그의 성질은 다음과 같다.

1. [math]\displaystyle{ \log_g1=0,\,\log_gg=1 }[/math]
2. [math]\displaystyle{ a=b\gt 0 }[/math]이면 [math]\displaystyle{ \log_ga=\log_gb }[/math]이다. 역도 성립.
3. [math]\displaystyle{ \log_g\left(ab\right)=\log_ga+\log_gb }[/math]
4. [math]\displaystyle{ \log_g\left(a^n\right)=n\log_ga }[/math]

실수에서의 로그와 다른점은, 이산로그를 취할 때, 법 [math]\displaystyle{ \phi\left(m\right) }[/math]에 대해 계산을 해줘야한다는 것 뿐.

예제

• [math]\displaystyle{ 4x^4\equiv2\pmod7 }[/math]을 만족하는 \(x\)를 모두 찾아라.

  3이 7의 원시근임은 쉽게 보일 수 있다. 합동식에 이산로그를 씌우면, [math]\displaystyle{ \operatorname{ind}_3\left(4x^4\right)\equiv\operatorname{ind}_32\pmod{\phi\left(7\right)=6} }[/math]. 이산로그와 합동식의 성질을 사용하여 간단히 정리하면 [math]\displaystyle{ 4\operatorname{ind}_3x\equiv4\pmod6 }[/math]이고, 곧 [math]\displaystyle{ 2\operatorname{ind}_3x\equiv2\pmod3 }[/math]이다. 따라서, [math]\displaystyle{ \operatorname{ind}_3x\equiv1\pmod3 }[/math], 혹은 [math]\displaystyle{ \operatorname{ind}_3x\equiv1,\,4\pmod6 }[/math]. 이산로그표를 참조하거나, 직접 계산을 통해 [math]\displaystyle{ x\equiv3,\,4\pmod7 }[/math]임을 알 수 있다.

• [math]\displaystyle{ x^k\equiv a\pmod m }[/math]을 만족하는 \(x\)가 존재하기 위한 조건을 찾아라 (단, \(a\)와 \(m\)은 서로소, \(r\)은 \(m\)의 한 원시근).

  양변에 이산로그를 씌우자. 그럼, [math]\displaystyle{ k\operatorname{ind}_rx\equiv\operatorname{ind}_ra\pmod{\phi\left(m\right)} }[/math]. 이 [math]\displaystyle{ \operatorname{ind}_rx }[/math]을 한 변수로 생각할 때, 저 합동식이 해가 존재하기 위한 필요충분조건은 [math]\displaystyle{ d=\gcd\left(k,\phi\left(m\right)\right)\mid\operatorname{ind}_ra }[/math]인 것이다. 다르게 표현하면, [math]\displaystyle{ \operatorname{ind}_ra=ld }[/math]. 따라서, [math]\displaystyle{ \frac{\phi\left(m\right)}{d}\operatorname{ind}_ra\equiv l\phi\left(m\right)\equiv0\pmod{\phi\left(m\right)} }[/math]이다. 여기서 이산로그의 성질을 사용하면, [math]\displaystyle{ \operatorname{ind}_r\left(a^{\frac{\phi\left(m\right)}{d}}\right)\equiv0\pmod{\phi\left(m\right)} }[/math]. 이산로그를 벗겨주면, [math]\displaystyle{ a^{\frac{\phi\left(m\right)}{d}}\equiv1\pmod m }[/math].

  만약 \(a\)가 이 조건만 만족하면, \(x\)는 법 \(m\)에 대해 \(a\)의 \(k\) 제곱근과 비슷한 개념이 된다. 정확하게는, \(a\)를 \(k\)th power residue of modulo m이라 부른다. 특히, \(k=2\)인 경우에는 이차잉여가 된다.

이산로그 표

이산로그를 찾는것은 매우 어렵다는 것이 알려져있다. 수학적으로 이산로그를 찾는 것과 소인수분해를 하는 것의 계산 시간은 거의 비슷하다고. 사실 굳이 수학적 이론을 들이댈 필요 없이, 두 자리 수의 이산로그 표를 직접 만들어 보자. 원시근을 찾는 것 부터 고역일 것이다 아마. 그렇기 때문에 이산로그를 효율적으로 계산하기 위해서는 이산로그 표를 이용하는데, 이 이산로그 표도 작은 수에 대해서만 채워져있다. 대부분의 정수론 책 뒤에는 표가 있으니 직접 확인해 보자.

같이 보기

• 디피-헬만 열쇠 교환 프로토콜
• 로그 (수학)
• 이차잉여