Z_p 를 곱셈군으로 보면 p-1 order 짜리 cyclic group입니다
만약 Z_p 의 generator 를 하나라도 찾아내서 그걸 x라고 표시한다면
f(n)=x^n
f: (Z_p,+) → (Z_p-{0}, \dot)
위 f가 group isomorphism 이기 때문에 (Z_p,+) 의 generator 를 구해서 그 함숫값을 찾으면 모든 generator 를 다 찾을 수 있습니다.
제가 궁금한 것은 결국 어떻게 "첫번째" generator 를 찾을것이냐 하는 겁니다
결국 하나 찍어서 다 확인을 해봐야하는데 이게 너무 현타가 와서 좀 멋진 방법이 없을까 찾아보니 다음 방법이 있다고 합니다.
p-1 을 소인수분해 할수만 있다면
이렇게 나타내고, 아무거나 a를 하나 잡아서 a^(p-1)/f_i (mod p) 를 계산해보는데 (당연히) 그 중 하나라도 1과 mod p 합동이면 a는 generator 가 아니겠죠
그리고 반대로 만약 a^(p-1)/f_i (mod p) 가 "모두" 1이 아니면 a가 generator 가 된다고 하는데 이것의 증명이 궁금합니다
문제를 정리하면 1이상 p-1 이하 자연수 a, 그리고 p-1의 소인수분해 에 대해
a^(p-1)/f_i (mod p) 가 모두 1이 아니라면 a^k ≡1 (mod p) 이도록 하는 0<k<p-1 가 존재하지 않는다.
라그랑지에 정리에 의해 거의 자명한 얘기일거같긴 한데 증명을 어떻게 써야될지 모르겠어요
a로 생성된 group은 Zp^*의 subgroup이니까 group의 order p-1을 나눔. 한편 a로 생성된 group의 order가 m이면 a^m = 1 mod p고 m은 p-1을 나누면서 p-1은 아님.
이제 어떤 자연수 x의 약수중 x가 아닌 수는 다 어떤 x의 소인수 q에 대해서 x/q의 약수가 됨. 마찬가지로 p-1을 나누는 m은 p-1의 어떤 소인수 f에 대해서 p-1/f를 나눔. 그럼 a^(p-1)/f = 1 mod p임. 이제 대우취하면 만약 모든 소인수에서 앞서 식이 성립하지 않으면 a의 order는 p-1이 되는걸 암
감사합니다 매우 깔끔하네요
물론 필산으로 계산할때 계산량을 줄여주는거간 한데 일반적으로 계산복잡도를 떨어트리는 계산법은 아님. 우선 p-1의 소인수분해를 빠르게 할 수 없기때문. (p=2q+1꼴 소수이거나 2qr+1꼴 소수일 수도 있으니까) 다만 확률적으로 치면 대부분의 값은 생상자이고 심지어 대부분 2 3 5중 하나 선에서 걸림. 다만 일반적으로 큰 수에 대해서 찾는거면 아마 해법이 없을거임. p-1의 소인수분해를 알면 말한방법으로 test하먼 확률적으로 작은 수에서 얻어걸리게 되어있음
답변을 해주는 것은 아니라 미안한데 본문에서 Z_p의 덧셈군과 Z_(p-1) 곱셈군이 동형인 것이 아니라 Z_(p-1)덧셈군과 Z_p \{0} 곱셈군이 동형 아님? Z_n의 부분 곱셈군(단원군) 과 Z_pi(n) 덧셈군과 동형이잖음
글쓴사럼인데 제가 잘못썼네요 (Z_(p-1) ,+) 이랑( Z-{0},•) 이 동형이죠