모듈 식 산술의 오른쪽에서 왼쪽 바이너리 방법에 대한 설명?

Question

나는 Modulo의 Wikipedia 에서이 링크를 많이 연구하고 있습니다. 여기에 의사 코드가 있습니다.

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

나는 wiki에 주어진 설명을 이해하지 못한다. 왜 exp%2가 균등한지 또는 홀수인지 확인해야합니다. 또한 왜 세 가지 작업을 수행하고 있습니까?

Answer 1

이 알고리즘은 그 조합입니다 사각형에 의한 지수 알고리즘 및 모듈로 산술.

무슨 일이 일어나고 있는지 이해하려면 먼저 상황을 고려하십시오. exponent 의 힘입니다 2. 그런 다음 그것을 가정합니다 exponent = 2 ^ k, 결과는 결과를 제곱하여 계산할 수 있습니다. k 시간, 즉

res = (...((base ^ 2) ^2 ) ... ) ^2))
              ---------------------
                     k times

언제 exponent 힘이 아닙니다 2, 우리는 추가 곱셈을 만들어야합니다. 우리가 분열 할 수 있다면 밝혀졌습니다 exponent 나머지가없는 2 씩, 우리는베이스를 제곱하고 지수를 나눌 수 있습니다. 그러나 나머지가 있으면 중간 결과에 전류 값을 추가로 곱해야합니다. base.

당신이 보는 것은 모듈로 곱셈에 적용된 사각형에 의한 동일한 지수화입니다. 이 알고리즘은 정수 분할을 2 개 사용으로 나타냅니다 exponent >> 1 동일한 작동 floor(exponent / 2).