원시근과 지표
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
반응형
'정수론' 카테고리의 다른 글
[정수론](22)[사각-삼각수] (0) | 2025.06.03 |
---|---|
[정수론](21)[무한강하법 & 페르마의 마지막 정리] (0) | 2025.06.02 |
[정수론](19)[위수 & 원시근] (0) | 2025.05.29 |
[정수론](18)[약수들의 ϕ의 합] (0) | 2025.05.27 |
[정수론](17)[이차상호법칙] (0) | 2025.05.26 |