primitive root 증명하기

소수 p와 primitive root g가 있을 때 g가 p의 primitive root라는 것을 어떻게 밝혀낼 수 있을까요?

g를 exponent한 값들을 moduler p를 했을 때 그 결과 값이 1부터 p-1까지 나오는 것을 보이면 됩니다.

간단히 예를 들어서 설명하겠습니다.

g = 7, p = 11일 경우

7^0(mod 11) = 1, 7^1(mod 11) = 7, 7^2(mod 11) = 5, 7^3(mod 11) = 2 ... 이런식으로 확인을 해보면 됩니다.

참 쉽죠?