선생님 홀수인 경우가 살짝 이해가 안됩니다.

Question

홀수일 경우 2^5 = 2^2 * 2^2 * 2^1 이됩니다.   아래 코드를 보시면 조금 다른 것 같습니다 ret = (ret * ret ) % c; if(b % 2) ret = ( ret * a)% c;   하지만 위의 홀수일때의 계산을 풀어보면 ret = ( (ret * ret) % c * a) %c가 됩니다. 이를 다시 풀어보면 ret % c %c * ret %c %c * a %c 됩니다. 이러면 모듈러 연산이 두번씩 이루어지는 부분이 생기기 때문에 맞지 않는거 아닌가요?

큰돌 · Answer

안녕하세요. 정Logan님 ㅎㅎ 일단, 정수론 - 모듈러 연산의 특징은 하나의 특징인 것이지, 그걸 꼭 지킬 필요는 없습니다. 예를 들어 (a * b) %c = a % b * a % b 라고 해서 한번에 c로 모듈러 연산을 하지 않고 각각 할 필요는 없다. 라는 것이죠. 자, 그러면 왜 2번이 들어갔을까요? 오버플로를 생각하면 됩니다. ret이 반환될 때 모듈러연산 c를 한 값이 반환됩니다. 자 그러면 이 ret은 c보다 작은 값이 나오는게 자명하죠? 자, 근데 이 ret을 2번 곱한다? ret * ret을 하면 c보다 더 큰 값을 가질 수도 있겠죠? 그래서 c로 나누는 겁니다. 자, 그다음, ret에 a를 곱합니다. ret * a를 하면 c보다 더 큰 값을 가질 수도 있겠죠? 그래서 또 c로 나누는 겁니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 감사합니다. 강사 큰돌 올림.