이산로그

정의

법 [math]\displaystyle{ m }[/math]에 대한 원시근 [math]\displaystyle{ g }[/math]가 존재할 때, [math]\displaystyle{ (a,m)=1 }[/math]인 정수 [math]\displaystyle{ a }[/math]에 대해

[math]\displaystyle{ g^i \equiv a\pmod m }[/math]

인 정수 [math]\displaystyle{ i\;(0\le i \lt \phi(m)) }[/math]를 이산로그(discrete logarithm) 또는 지수(index)라고 하고 [math]\displaystyle{ \operatorname{ind}_g a }[/math], 또는 [math]\displaystyle{ \log_g a }[/math]로 표기한다. 이때 [math]\displaystyle{ \phi(m) }[/math]은 오일러 피 함수를 나타낸다. 이산로그라 부르는 이유는, 이게 로그함수와 비슷한 성질을 가지기 때문이다.

존재성과 유일성

법 [math]\displaystyle{ m }[/math]에 대한 원시근 [math]\displaystyle{ g }[/math]가 존재할 때, [math]\displaystyle{ (a,m)=1 }[/math]인 정수 [math]\displaystyle{ a }[/math]에 대해 이산로그 [math]\displaystyle{ \operatorname{ind}_g a }[/math]는 존재하고 유일하다. 이는 위수의 성질에 의한 것이다.

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

성질

1. [math]\displaystyle{ \operatorname{ind}_g 1 = 0 }[/math], [math]\displaystyle{ \operatorname{ind}_g g =1 }[/math]

   [math]\displaystyle{ g^0\equiv 1\pmod m }[/math]이고 [math]\displaystyle{ g^1\equiv g\pmod m }[/math]이므로 자명하다.

2. [math]\displaystyle{ a\equiv b\pmod m }[/math]일 필요충분조건은 [math]\displaystyle{ \operatorname{ind}_g a = \operatorname{ind}_g b }[/math]이다.

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

3. [math]\displaystyle{ \operatorname{ind}_g ab\equiv \operatorname{ind}_g a + \operatorname{ind}_g b\pmod{\phi(m)} }[/math]

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

4. [math]\displaystyle{ \operatorname{ind}_g a^n \equiv n\operatorname{ind}_g a\pmod{\phi(m)} }[/math]

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

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

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]을 만족하는 [math]\displaystyle{ x }[/math]를 모두 찾아라.

  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]을 만족하는 [math]\displaystyle{ x }[/math]가 존재하기 위한 조건을 찾아라 (단, [math]\displaystyle{ a }[/math]와 [math]\displaystyle{ m }[/math]은 서로소, [math]\displaystyle{ r }[/math]은 [math]\displaystyle{ m }[/math]의 한 원시근).

  양변에 이산로그를 씌우자. 그럼, [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].

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

이산로그 표

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

같이 보기

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