원시근이 존재하는 법에서는 모든 invertible residue를 하나의 원시근의 거듭제곱으로 표현할 수 있다. 이때 지수를 index라고 하며, 곱셈 문제를 덧셈 합동식으로 바꾼다. 현대 용어로는 discrete logarithm이다.
Index의 정의
modulo 의 primitive root를 라 하자. 이면 유일한 가 존재하여
이다. 이 를
라고 한다. 지수는 modulo 에서 결정된다.
Index의 기본 성질
첫 번째 성질은 , 를 곱하면 가 되는 것에서 바로 나온다.
Index Table
작은 법에서는 원시근의 거듭제곱을 나열하여 표를 만들 수 있다. 예를 들어 modulo 13에서 2는 primitive root이고
이다. 큰 법에서는 이 표를 만드는 것 자체가 discrete logarithm problem이므로 쉽지 않다.
Power Congruence
다음 합동식을 생각하자.
양변의 index를 취하면
가 된다. 즉 고차 합동식이 하나의 linear congruence로 바뀐다.
라 하면 선형합동식 이론에 의해 해가 존재할 필요충분조건은
이고, 존재하면 modulo 에서 서로 다른 index 해가 정확히 개이다. 따라서 원래 합동식도 reduced residue system 안에서 개의 해를 가진다.
Index를 사용하지 않는 판정식
가 크기 인 cyclic group이고 라 하자. 가 제곱일 조건은 이다. 이는 다음과 동치이다.
실제로 가 1일 조건은 , 즉 이다.
소수 에서는 이므로
이다.
예제:
4의 역원은 10이므로
이다. 원시근 2를 사용하면 이므로
이다. 이고 이므로 해가 3개 있다. 3으로 나누면
즉 이다. modulo 12에서 index는 이고
이다.
Quadratic Residue와의 연결
, 가 홀수 소수이면 이다. 따라서 가 풀릴 조건은
이다. 이것이 다음 글에서 다룰 Euler’s Criterion이다.
원시근이 바뀌면 Index는 어떻게 변하는가
가 또 다른 primitive root이면 이다. 이므로
즉
이다. Index 값은 원시근에 따라 바뀌지만 power congruence의 해 존재 여부는 바뀌지 않는다.
정리
Index는 cyclic multiplicative group의 곱셈을 지수의 덧셈으로 변환한다. 는 index에 대한 linear congruence가 되며, 이 해의 존재 조건과 개수를 결정한다.
연습 문제
- modulo 11에서 원시근 2에 대한 을 구한다.
- 의 해 존재 여부를 판정한다.
- 의 모든 해를 구한다.
풀이
1번
이므로 index는 7이다.
2번
이고
이므로 해가 없다.
3번
이므로
이다. 나누면 이고 index는 이다. 따라서
이다.