곱셈 역원 편집하기

'''곱셈 역원'''(乘法逆元, multiplicative inverse)은 어떤 수에 대해 곱했을 때 1이 되는 수를 말한다. 주로 모듈로 연산(modular arithmetic)에서 사용되며, 나눗셈을 곱셈으로 바꾸기 위해 활용된다.
==개요==
정수 a에 대해 어떤 수 x가 존재해서 다음을 만족하면, x는 a의 곱셈 역원이다.
 a * x ≡ 1 (mod m)
여기서 ≡ 기호는 "동치(congruence)"를 의미하며,  a * x를 m으로 나눈 나머지가 1과 같다는 뜻이다. 즉,
 a * x % m == 1
과 같은 의미이다.
==존재 조건==
곱셈 역원 x가 존재하려면 다음 조건이 충족되어야 한다.
*a와 m이 서로소여야 한다. 즉, gcd(a, m) = 1이어야 한다.
*이 조건이 성립할 때만 a의 역원이 (mod m)에서 존재한다.
==계산 방법==
*'''브루트포스 방법'''
:x = 1부터 m-1까지 순차적으로 대입하여 a * x % m == 1이 되는 x를 찾는다.
*'''확장 유클리드 알고리즘'''
:a * x + m * y = 1이 되는 정수 x, y를 구하고, x % m을 곱셈 역원으로 사용한다.
*'''페르마의 소정리''' (m이 소수일 경우)
:x = a^(m - 2) % m을 계산하여 곱셈 역원을 구할 수 있다.
==예시==
*a = 3, m = 7인 경우:
:3 * 5 = 15, 15 % 7 = 1 → 5는 3의 곱셈 역원이다.
*a = 4, m = 10인 경우:
:gcd(4, 10) = 2 → 서로소가 아니므로 역원이 존재하지 않는다.
==활용==
*모듈로 나눗셈 구현
*RSA 암호 알고리즘
*선형 합동 방정식 해법
*프로그래밍 대회나 수론 기반 알고리즘 문제 해결
==파이썬 구현==
<syntaxhighlight lang="python">
# 확장 유클리드 알고리즘을 이용한 곱셈 역원
def modinv(a, m):
    def egcd(a, b):
        if b == 0:
            return (1, 0)
        x1, y1 = egcd(b, a % b)
        x, y = y1, x1 - (a // b) * y1
        return (x, y)

    x, y = egcd(a, m)
    if (a * x + m * y) % m != 1:
        raise ValueError("No modular inverse exists")
    return x % m

# 예시
print(modinv(3, 7))  # 출력: 5
</syntaxhighlight>
==같이 보기==
*[[모듈로 연산]]
*[[확장 유클리드 알고리즘]]
*[[페르마의 소정리]]
*[[RSA 알고리즘]]
==참고 문헌==
*Rosen, K. H. (2011). ''Elementary Number Theory and Its Applications''. Pearson.
*Cormen, T. H. et al. (2009). ''Introduction to Algorithms''. MIT Press.