인프런 커뮤니티 질문&답변
작성한 질문수
선생님 홀수인 경우가 살짝 이해가 안됩니다.
작성
·
353
0
홀수일 경우 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 됩니다. 이러면 모듈러 연산이 두번씩 이루어지는 부분이 생기기 때문에 맞지 않는거 아닌가요?
답변 1
0
큰돌
지식공유자
안녕하세요. 정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로 나누는 겁니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
감사합니다.
강사 큰돌 올림.