이산로그 편집하기



== 정의 ==
법 <math>m</math>에 대한 [[원시근 (정수론)|원시근]] <math>g</math>가 존재할 때, <math>(a,m)=1</math>인 정수 <math>a</math>에 대해
:<math>g^i \equiv a\pmod m</math>
인 [[정수]] <math>i\;(0\le i < \phi(m))</math>를 '''이산로그(discrete logarithm)''' 또는 '''지수(index)'''라고 하고 <math>\operatorname{ind}_g a</math>, 또는 <math>\log_g a</math>로 표기한다. 이때 <math>\phi(m)</math>은 [[오일러 피 함수]]를 나타낸다. 이산로그라 부르는 이유는, 이게 [[로그 (수학)|로그함수]]와 비슷한 성질을 가지기 때문이다.

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

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

== 성질 ==
#<math>\operatorname{ind}_g 1 = 0</math>, <math>\operatorname{ind}_g g =1</math>
#:<math>g^0\equiv 1\pmod m</math>이고 <math>g^1\equiv g\pmod m</math>이므로 자명하다.
#<math>a\equiv b\pmod m</math>일 필요충분조건은 <math>\operatorname{ind}_g a = \operatorname{ind}_g b</math>이다.
#:<math>i=\operatorname{ind}_g a,\; j=\operatorname{ind}_g b</math>라고 하자. 그러면 이산로그의 정의에 의해 <math>g^i\equiv a\pmod m</math>이고 <math>g^j\equiv b\pmod m</math>이다. <math>a\equiv b\pmod m</math>이면 <math>\equiv</math>의 추이성에 의해 <math>g^i \equiv g^j\pmod m</math>이고, 그러면 [[위수 (정수론)|위수]]의 성질과 원시근의 정의에 의해 <math>i\equiv j\pmod{\phi(m)}</math>이다. 이때 <math>0\le i,j < \phi(m)</math>이므로 <math>i-j=0</math>, 즉 <math>i=j</math>이다. 이제 <math>\operatorname{ind}_g a = \operatorname{ind}_g b</math>이라고 하자. <math>i=\operatorname{ind}_g a = \operatorname{ind}_g b</math>라 하면, <math>g^i\equiv a\pmod m</math>이고 <math>g^i \equiv b\pmod m</math>이므로 <math>\equiv</math>의 추이성에 의해 <math>a\equiv b \pmod m</math>이다.
#<math>\operatorname{ind}_g ab\equiv \operatorname{ind}_g a + \operatorname{ind}_g b\pmod{\phi(m)}</math>
#:<math>i=\operatorname{ind}_g a,\; j=\operatorname{ind}_g b</math>라고 하자. 그러면 이산로그의 정의에 의해 <math>g^i\equiv a\pmod m</math>이고 <math>g^j\equiv b\pmod m</math>이므로 <math>g^{i+j}\equiv g^i g^j \equiv ab \pmod m</math>이다. 이때 <math>\operatorname{ind}_g ab = k</math>라 하면 <math>g^k \equiv ab \pmod m</math>이다. 즉 <math>g^{i+j}\equiv g^k\pmod m</math>이므로 위수의 성질과 원시근의 정의에 의해 <math>i+j \equiv k\pmod{\phi(m)}</math>이고, <math>i,j,k</math>를 풀어쓰면 원하는 결론을 얻는다.
#<math>\operatorname{ind}_g a^n \equiv n\operatorname{ind}_g a\pmod{\phi(m)}</math>
#:<math>\operatorname{ind}_g ab\equiv \operatorname{ind}_g a + \operatorname{ind}_g b\pmod{\phi(m)}</math>임과 [[수학적 귀납법]]을 이용해 쉽게 증명할 수 있다.
수학적인 감각이 있는 사람은 이 네 성질들이 전부 [[로그 (수학)|로그]]와 비슷하다는 것을 알 수 있다. 각각 대응하는 로그의 성질은 다음과 같다.
#<math>\log_g1=0,\,\log_gg=1</math>
#<math>a=b>0</math>이면 <math>\log_ga=\log_gb</math>이다. 역도 성립.
#<math>\log_g\left(ab\right)=\log_ga+\log_gb</math>
#<math>\log_g\left(a^n\right)=n\log_ga</math>
실수에서의 로그와 다른점은, 이산로그를 취할 때, 법 <math>\phi\left(m\right)</math>에 대해 계산을 해줘야한다는 것 뿐.

== 예제 ==
*<math>4x^4\equiv2\pmod7</math>을 만족하는 <math>x</math>를 모두 찾아라.
*:3이 7의 원시근임은 쉽게 보일 수 있다. [[합동식]]에 이산로그를 씌우면, <math>\operatorname{ind}_3\left(4x^4\right)\equiv\operatorname{ind}_32\pmod{\phi\left(7\right)=6}</math>. 이산로그와 합동식의 성질을 사용하여 간단히 정리하면 <math>4\operatorname{ind}_3x\equiv4\pmod6</math>이고, 곧 <math>2\operatorname{ind}_3x\equiv2\pmod3</math>이다. 따라서, <math>\operatorname{ind}_3x\equiv1\pmod3</math>, 혹은 <math>\operatorname{ind}_3x\equiv1,\,4\pmod6</math>. 이산로그표를 참조하거나, 직접 계산을 통해 <math>x\equiv3,\,4\pmod7</math>임을 알 수 있다.
*<math>x^k\equiv a\pmod m</math>을 만족하는 <math>x</math>가 존재하기 위한 조건을 찾아라 (단, <math>a</math>와 <math>m</math>은 [[서로소]], <math>r</math>은 <math>m</math>의 한 [[원시근 (정수론)|원시근]]).
*:양변에 이산로그를 씌우자. 그럼, <math>k\operatorname{ind}_rx\equiv\operatorname{ind}_ra\pmod{\phi\left(m\right)}</math>. 이 <math>\operatorname{ind}_rx</math>을 한 변수로 생각할 때, 저 [[합동식]]이 해가 존재하기 위한 필요충분조건은 <math>d=\gcd\left(k,\phi\left(m\right)\right)\mid\operatorname{ind}_ra</math>인 것이다. 다르게 표현하면, <math>\operatorname{ind}_ra=ld</math>. 따라서, <math>\frac{\phi\left(m\right)}{d}\operatorname{ind}_ra\equiv l\phi\left(m\right)\equiv0\pmod{\phi\left(m\right)}</math>이다. 여기서 이산로그의 성질을 사용하면, <math>\operatorname{ind}_r\left(a^{\frac{\phi\left(m\right)}{d}}\right)\equiv0\pmod{\phi\left(m\right)}</math>. 이산로그를 벗겨주면, <math>a^{\frac{\phi\left(m\right)}{d}}\equiv1\pmod m</math>.
*:만약 <math>a</math>가 이 조건만 만족하면, <math>x</math>는 법 <math>m</math>에 대해 <math>a</math>의 ''<math>k</math> 제곱근''과 비슷한 개념이 된다. 정확하게는, <math>a</math>를 '''<math>k</math>th power residue of modulo m'''이라 부른다. 특히, <math>k=2</math>인 경우에는 [[이차잉여]]가 된다.

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

== 알고리즘 ==

== 같이 보기 ==
*[[디피-헬만 열쇠 교환 프로토콜]]
*[[로그 (수학)]]
*[[이차잉여]]

{{주석}}
[[분류:정수론]]