정수론

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

황올뱀 2025. 5. 30. 13:40

원시근과 지표

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

 

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

728x90
반응형