| [ QuizWit ] in KIDS 글 쓴 이(By): whiz (!논문쓰자!) 날 짜 (Date): 1998년 7월 14일 화요일 오후 08시 52분 50초 제 목(Title): Re: [요청!] 도와주세요! 이 수식의 계산좀. P가 소수이거나, 소인수분해를 모른다면 역시 도움이 안 되겠지만... 먼저 정의를 하나 합시다. varphi(P) = 1부터 P까지의 수 중에서 P와 서로 소인 수의 개수 라고 하면, P = x_1^r_1 x_2^r_2 ... x_n^r_n 이 소인수분해일 때, varphi(P) = P (1 - 1/x_1) (1 - 1/x_2) ... (1 - 1/x_n) 이 됩니다. 어쨌거나, G^(varphi(P)) = 1 (mod P) 이므로, X를 varphi(P)로 나눈 나머지 Y 에 대하여 G^Y (mod P)를 구하면 되겠습니다. 이 방법을 써서 계산이 간편하게 되려면, 1. P에 대하여 잘 알고 있어야 하고 2. 될 수 있는 한 P가 서로 다른 인수를 많이 갖고 있어야 합니다. 도움이 안 될 것 같네요. -- 그대 아직도 꿈꾸는가. |