Modular exponentiation

Modular exponentiation

a의 b승을 n으로 나눈 나머지를 구하는 연산(a, b, n은 양의 정수)

우선 나머지를 구하는 연산을 구현해본다.

a를 n으로 나눈 나머지를 구하려면 n보다 작아질때까지 a에서 n을 빼면 된다.

while (a > n) {
    a = a - n;
}

while문을 빠져나온 a가 나머지가 된다.

그런데 a가 n보다 훨씬 크면 계산하는데 시간이 오래 걸린다.

a에서 a보다 작은 n의 배수를 빼면 시간을 줄일 수 있다.

이진수에서 왼쪽으로 bit shift를 1번 할때마다 2배의 숫자가 되는것을 이용하여 빠르게 계산 할 수 있다. (왼쪽으로 bit shift 할 때 최하위에 추가되는 bit는 0으로 한다.)

while (a > n) {
    n_temp = n;
    while (true) {
        if (a < (n_temp << 1)) {
            break;
        }
        n_temp = n_temp << 1;
    }
    a = a – n_temp;
}

이제 a의 b승을 n으로 나눈 나머지를 구하는 연산을 구현해 본다.

나머지연산의 곱셈의 성질에 의해 아래 연산이 성립한다.

이진수에서 오른쪽으로 1번 bit shift 할 때마다 1/2배가 되는것을 이용하여 빠르게 계산 할 수 있다.

이때 최하위 bit는 0 이어야 한다. (오른쪽으로 bit shift 할 때 최하위 bit가 사라진다. 오른쪽으로 bit shift 할 때 최상위에 추가되는 bit는 0으로 한다.)

이번에는 b의 bit shift를 이용한다. (b가 1이면 bit shift를 사용할 필요가 없다.)

b의 최하위 bit 가 1이면 1을 먼저 빼주고 오른쪽으로 bit shift 해야 한다.

오른쪽 bit shift 할 때 최하위 bit가 사라지기 때문에 지수의 (b-1)>>1을 b>>1로 바꿔도 동일하다.

b의 최하위 bit가 1일때 :

b의 최하위 bit 가 0이면 바로 오른쪽으로 bit shift 한다.

b의 최하위 bit가 0일때 :

b의 최하위 bit가 0일때와 1일때 둘다 형태의 항(term)이 있다.

이것은 제일 처음 구하고자 했던 와 비슷한 형태이다.

(a를 로, b를 2로 치환)

따라서 를 재귀함수로 구현 할 수 있다.

modPow (a, b, n) {
    if (b == 1) {
        return mod(a, n);
    }
    temp = modPow(a, b >> 1, n);
    temp2 = mod(temp * temp, n);
    if (b의 최하위 bit가 0) {
        return temp2;
    }
    if (b의 최하위 bit가 1) {
        return mod(mod(a, n) * temp2), n);
    }
}

mod (a, n) {
    while (a > n) {
        n_temp = n;
        while (true) {
            if (a < (n_temp >> 1)) {
                break;
            }
            n_temp = n_temp >> 1;
        }
        a = a – n_temp;
    }
    return a;
}

실행파일

리눅스 aarch64 : https://drive.google.com/file/d/12dvyH6kfPCt7gHFdWtoEEkMuiiq6dwud/view?usp=share_link 

리눅스 amd64 : https://drive.google.com/file/d/1zoumq9i2KbUPPPJ-vgDqT8-wpQ5-cmDr/view?usp=share_link

윈도우 amd64 : https://drive.google.com/file/d/10FZYGpA2fwOuff-j8X-cpd8aTzqreluB/view?usp=share_link