이 메시지는 외부 자료를 칸아카데미에 로딩하는 데 문제가 있는 경우에 표시됩니다.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

주요 내용

모듈로 역수

역수란 ?

어떤 수를 자신의 역수로 곱하면 1이 된다는 사실을 상기시켜 봅시다.  매우 기본적인 연산입니다.
  • A * 1/A = 1이므로 A의 역수는 1/A입니다(e.g. 5의 역수는 1/5).
  • 0이 아닌 모든 실수는 역수를 가집니다
  • A의 역수에 수를 곱하는 것은 그 수로 A를 나누는 것과 같습니다(e.g. 10/5 = 10* 1/5).

모듈러 역수(modular inverse)란?

모듈러 연산에 나누기 연산은 없지만 모듈러 역수는 있습니다.
  • A (mod C) 의 모듈러 역수는 A^-1입니다
  • (A * A^-1) ≡ 1 (mod C) 또는 (A * A^-1) mod C = 1
  • C와 서로소인 수(C와 공통 소인수가 없는 수) 만 모듈러 역수 (mod C) 를 가집니다

모듈러 역수를 구하는 방법

A (mod C)의 모듈러 역수를 구하는 단순한 방법은 다음과 같습니다.
1단계. 0에서 C-1까지의 B값에 대해 A * B mod C 를 계산합니다
2단계. A mod C의 모듈러 역수는 A * B mod C = 1을 만족하는 B값입니다
B mod C 항은 0에서 C-1까지의 정수값만 가질 수 있으므로 더 큰 값을 테스트하지 않아도 됩니다.

예제: A=3, C=7

1단계. 0에서 C-1까지의 B값에 대해 A * B mod C를 계산합니다

3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7)   <------ 역수를 찾았습니다!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

2단계. A mod C의 모듈러 역수는 A * B mod C = 1를 만족하는 B값입니다.

5*3 mod 7 = 1이므로 3 mod 7의 역수는 5입니다.
간단하죠!
역수를 찾을 수 없는 연습 문제 하나를 더 보도록 합시다.

예제: A=2 C=6

1단계. 0에서 C-1까지의 B값에 대해 A * B mod C를 계산합니다.

2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)

2단계. A mod C의 모듈러 역수는 A * B mod C = 1을 만족하는 B값입니다.

어떤 B값도 A * B mod C = 1을 만족시키지 않습니다. 그러므로 A는 모듈러 역수 (mod 6)를 갖지 않습니다.
2는 6과 서로소가 아니기 때문입니다.(두 수는 2라는 인수를 공통으로 가집니다)

이 방법은 좀 느려보이는군요...

A (mod C)의 역수를 알아내는 훨씬 빠른 방법이 있는데 이는 확장된 유클리드 호제법을 다루는 다음 글에서 알아도록 하겠습니다.