[정수론](20)[원시근의 지표]

원시근과 지표

g가 소수 p의 원시근이라면
g, g^2, ..., g^(p-1) ≡ 1, 2, ..., p-1 (mod p)의 재배열
즉 g의 지수와 1~p-1 사이의 값이 일대일대응이다.
이때 g^(e) ≡ a (mod p)의 e를 mod p에 대한 a의 지표라고 정의한다.
$$g^{I_{p, \ g}(a)} \equiv a \ (mod \ p)$$
만약 p, g가 명확한 경우, I(a)로 간략화할 수 있다.

성질

• 곱셈법칙: I(a) + I(b) ≡ I(ab) (mod p-1)
  g^I(ab) ≡ ab
  ≡ g^I(a) * g^I(b) ≡ g^(I(a) + I(b)) (mod p)
  이때 지수는 1~p-1사이의 값이므로,
  I(a) + I(b) ≡ I(ab) (mod p-1)
• 거듭제곱 법칙: I(a^k) ≡ kI(a) (mod p-1)
  g^I(a^k) ≡ a^k
  ≡ (g^I(a))^k ≡ g^kI(a)
  이때 지수는 1~p-1사이의 값이므로,
  I(a^k) ≡ kI(a) (mod p-1)

특수 경우

• I(1) = p-1
  g^e ≡ 1 (mod p)에서
  g는 원시근이므로 e = p-1 = I(1)
• I(g) = 1
  g^1 ≡ 1 (mod p)
  1 = I(g)
• p>2일때, I(p-1) = (p-1)/2
  g^(p-1) ≡ 1 (mod p)
  (g^((p-1)/2) - 1)(g^((p-1)/2) + 1) ≡ 0 (mod p)
  g는 원시근이고 위수의 성질에 의해 p-1보다 작은 1이 나오는 지수는 없다
  따라서 g^((p-1)/2) !≡ 1 (mod p)이므로,
  g^((p-1)/2) + 1) ≡ 0 (mod p)이다.
  따라서, g^(p-1)/2) ≡ -1 ≡ p-1 (mod p)이다.
  즉, I(p-1) = (p-1)/2

예) p=7, g=3인 지표
    3^1 ≡ 3 (mod 7)
    3^2 ≡ 9 ≡ 2 (mod 7)
    3^3 ≡ 27 ≡ 6 (mod 7)
    3^4 ≡ 81 ≡ 4 (mod 7)
    3^5 ≡ 243 ≡ 5 (mod 7)
    3^6 ≡ 729 ≡ 3 (mod 7)

a	1	2	3	4	5	6
I(a)	6	2	1	4	5	3

 

지표로 합동방정식을 빠르게 계산할 수 있다!
-> 단, 지표 구하는게 방정식 푸는 것보다 복잡할 수 있으니 반복 연산일때만 지표로 풀기