모듈러 역수

모듈러 역수란?

\(A (mod M)\)을 A를 M으로 나눈 나머지라고 할 때, A을 \(B (mod M)\)한 결과 값을 C, B을 \(B (mod M)\)한 결과 값을 D라고 했을시, 다음을 만족합니다.

\(A+B\equiv C+D(mod M)\)
\(A-B\equiv C-D(mod M)\)
\(A\times B\equiv C\times D(mod M)\)

\(\equiv\) 란?
예를 들어, \(A\equiv B(mod M)\)이라고 할 때, A를 M으로 나눈 나머지와 B를 M으로 나눈 나머지가 같음을 의미합니다.
\(A=M\times Q_a+r\)
\(B=M\times Q_b+r\)
여기서 \(Q_{a,b}\)는 미지수 이고, r이 나머지입니다.

이러한 이유로 식을 모두 계산 후 나머지를 구하는 것이 아닌, 계산 이전부터 나머지를 구하고 계산후 나머지를 구하게 된다면 컴퓨터가 계산하지 못하는 단위의 계산도 가능하게 됩니다.

하지만 나누기에 대해서는 이가 성립하지 않습니다.

그러하기에 나눗셈은 다음의 예시와 같은 절차로 풀게됩니다.
ex)\(8\div 2=4(mod M)\) -> \(2\times 4=8(modM)\)
다음의 과정을 거친다면, 나눗셈이 아닌 곱셈을 계산하는 것이 되기에 모듈러 역수를 구할수 있게 됩니다. 이를 식으로 나타낸다면,
\(A\div B=C(mod M)\)
\(A\times B^{-1}=C(mod M)\)
\(A\times B\times B^{-2}=C(mod M)\)
\(A\times B=C\times B^{2}(mod M)\)

RSA 암호

1. 송신자가 수신자의 공개키를 얻는다.
2. 보내고자 하는 메일을 숫자로 변환한후, e의 제곱을 한 후 n으로 나눈 나머지를 수신자에게 보냅니다.
3. \(x^d\)을 n으로 나눈 나머지를 구하면 \(x^d=m^{ed} \equiv m(modn)\)이기에 원래 문장으로 복원 가능합니다.