파이썬으로 ((a^b)^(c^d)) mod n 값 구하는 프로그램

다섯 개의 정수 a, b, c, d, n이 주어졌다고 가정해 봅시다. 이때 구해야 할 값은 ((a^b)^{(c^d)}) mod n이며, 결과는 정수여야 합니다.

예를 들어 입력이 a = 2, b = 3, c = 2, d = 4, n = 10이라면 출력은 6이 됩니다.

2^3 = 8
2^4 = 16
8^16 = 281474976710656
281474976710656 mod 10 = 6

문제 해결 접근 방법

거듭제곱 위에 또 거듭제곱이 있는 형태는 숫자가 기하급수적으로 커지기 때문에 직접 계산하는 것은 불가능합니다. 이 문제는 오일러 피 함수(Euler's Totient Function)와 모듈러 지수 법칙을 활용하면 효율적으로 해결할 수 있습니다.

해결 단계는 다음과 같습니다.

helper() 함수 정의: 오일러 피 함수 값을 계산합니다.
- p := n으로 초기화하고, i := 2부터 시작합니다.
- i * i <= n인 동안 반복합니다.
  - n mod i == 0이면 p := p - floor(p / i)로 갱신합니다.
  - n mod i == 0인 동안 n := floor(n / i)로 나누어 소인수를 제거합니다.
  - i가 2가 아니면 i를 2씩 증가시키고, 그렇지 않으면 1씩 증가시킵니다(짝수 건너뛰기 최적화).
- n > 1이면 p := p - floor(p / n)으로 갱신합니다.
- p를 반환합니다.
b == 0 또는 (c == 0이고 d != 0)이면 (a^0) mod n을 반환합니다.
c == 1 또는 d == 0이면 (a^b) mod n을 반환합니다.
a == 0 또는 a mod n == 0이면 0을 반환합니다.
d == 1이면 (a^(b*c)) mod n을 반환합니다.
p := helper(n)으로 오일러 피 함수 값을 구합니다.
e := (c^d) mod p + p를 계산합니다.
(((a^b) mod n)^e) mod n을 반환합니다.

예제 코드

아래 파이썬 구현을 통해 더 자세히 이해할 수 있습니다.

def helper(n):
    p = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            p -= p // i
        while n % i == 0:
            n = n // i
        if i != 2:
            i += 2
        else:
            i += 1
    if n > 1:
        p -= p // n
    return p

def solve(a, b, c, d, n):
    if b == 0 or (c == 0 and d != 0):
        return pow(a, 0, n)
    if c == 1 or d == 0:
        return pow(a, b, n)
    if a == 0 or a % n == 0:
        return 0
    if d == 1:
        return pow(a, b * c, n)
    p = helper(n)
    e = pow(c, d, p) + p
    return pow(pow(a, b, n), e, n)

print(solve(2, 3, 2, 4, 10))

입력

2, 3, 2, 4, 10