모듈러 연산의 성질을 활용한 알고리즘 최적화 방법

백준 13172 Σ 문제를 풀면서, 재귀 호출을 사용한 거듭제곱 계산을 구현했다. 

문제는 풀렸지만, 문제의 의도가 역원을 계산하는 방법을 사용하여 모듈러 연산을 해야하는 것 같고

이에 대해 조금 더 깊게 공부해보고자 블로그를 작성한다.

 

모듈러 연산의 성질을 활용한 다양한 알고리즘 최적화 방법

1. 모듈러 거듭제곱 (Modular Exponentiation)

빠른 거듭제곱법(Exponentiation by Squaring)을 사용하여 큰 수의 거듭제곱을 모듈로 연산할 때 효율적으로 계산한다. 

백준 13172 문제를 풀이했던 방법이다. 

 

2. 모듈러 역원 (Modular Inverse)

유클리드 호제법을 사용한 확장 유클리드 알고리즘을 통해 모듈러 역원을 계산한다. 이는 주어진 수 'a'와 모듈러 'm'에 대해 $𝑎^{−1} \mod 𝑚$ 을 구하는 방법이다.

def extended_gcd(a, b):
	if a == 0:
    	return (b, 0, 1)
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return (gcd, x, y)
    
def modular_inverse(a, m):
	gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
    	raise Exception('Modular inverse does not exist')
    else:
    	return x % m

 

3. 모듈러 곱셈 역원 (Multiplicative Inverse)

페르마의 소정리를 사용하여 모듈러 역원을 구할 수 있다. 이는 모듈러 m이 소수일 때 사용 가능하다.

$$ a^{−1} \equiv a^{m-2}\mod  m$$

 

4. 합동 공식 (Congruence Properties)

모듈러 연산의 성질을 사용하여 합동 공식들을 이용하면 많은 계산을 단순화할 수 있다.

예를 들어, $(a + b) \mod m = ((a \mod m) + (b \mod m)) \mod m$ 와 같은 성질을 이용하면 큰 수의 연산을 줄일 수 있다.

 

5. 수론적 변환 (Number Theoretic Transform, NTT)

FFT(Fast Fourier Transform)의 수론적 변환 버전으로, 큰 정수 곱셈을 빠르게 수행할 수 있다. 이는 다항식 곱셈에 유용하다.

def ntt(A, mod, root):
    n = len(A)
    h = pow(root, (mod - 1) // n, mod)
    for i in range(n):
        j = int('{:0{w}b}'.format(i, w=math.ceil(math.log2(n)))[::-1], 2)
        if i < j:
            A[i], A[j] = A[j], A[i]
    m = 2
    while m <= n:
        z = pow(h, n // m, mod)
        for k in range(0, n, m):
            zi = 1
            for j in range(m // 2):
                u = A[k + j]
                v = A[k + j + m // 2] * zi % mod
                A[k + j] = (u + v) % mod
                A[k + j + m // 2] = (u - v) % mod
                zi = zi * z % mod
        m *= 2
    return A