원시근 (Primitive Root)

한 줄 정의: 거듭제곱으로 법 n의 모든 기약잉여를 만들어 내는 수입니다.

쉽게 풀면

어떤 수를 계속 거듭제곱하면서 n으로 나눈 나머지를 적어 나갔을 때, n과 서로소인 나머지가 하나도 빠짐없이 모두 등장하는 경우가 있습니다. 이런 수를 법 n의 원시근이라고 합니다. 예를 들어 3은 법 7의 원시근이어서 3의 거듭제곱 나머지가 1부터 6까지 모두 나타납니다.

왜 중요한가

원시근이 있으면 곱셈이 지수의 덧셈으로 바뀌어 모듈러 산술이 크게 단순해지고, 이 지수를 이산로그라고 부릅니다. 디피-헬만 키 교환과 ElGamal 암호는 이산로그를 되돌리기 어렵다는 가정 위에 세워져 있어 정보보안 연구에서 핵심적입니다.

논문에서는 이렇게 쓰입니다

"법 p의 원시근을 생성원으로 선택하여 이산로그 기반 키 교환 프로토콜을 구성하였다."

조금 더 깊게 보면

원시근이 존재한다는 것은 기약잉여들의 곱셈군이 순환군이라는 말과 같습니다. 원시근은 모든 법에 대해 존재하지는 않으며, 홀수 소수의 거듭제곱과 그 두 배, 그리고 1, 2, 4인 경우에만 존재한다는 사실이 알려져 있습니다. 원시근이 존재할 때 그 개수는 오일러 파이 함수를 두 번 적용한 값과 같습니다. 어떤 수가 원시근인지 판정하려면 군의 크기의 소인수마다 거듭제곱이 1이 되는지를 확인하면 됩니다.

주의할 점

다항식의 근을 뜻하는 원시근이나 복소수의 1의 원시근과는 다른 개념이며, 정수론에서는 법에 대한 곱셈군의 생성원을 가리킵니다. 또 원시근은 여러 개 존재할 수 있어 유일하지 않습니다.