수학(mathematics), 특히 산술(arithmetic)의 영역에서, 정수(integer) a의 모듈러 곱셈 역(modular multiplicative inverse)은 곱 ax가 모듈러스 m에 관련하여 1에 합동(congruent)임을 만족하는 정수 x입니다. 모듈러 산술(modular arithmetic)의 표준 표기법에서, 이 합동은 다음으로 쓰입니다:
\(\quad\displaystyle ax \equiv 1 \pmod{m},\)
이는 m이 양 ax − 1을 (고르게) 나누거나, 또 다른 방법에 넣으면, ax를 정수 m으로 나눈 나머지는 1이라는 명제를 쓰는 약식 방법입니다. 만약 a가 역 모듈로 m을 가지면, 이 모듈러에 관련하여 합동 클래스(congruence class)를 형성하는 이 합동의 무한 숫자의 해가 있습니다. 더욱이, a에 합동인 임의의 정수 (즉, a의 합동 클래스에서)는 x의 합동 클래스의 임의의 원소를 모듈러 곱셈 역으로 가집니다. w를 포함하는 합동 클래스를 나타내기 위해 \(\displaystyle \overline{w}\) 표기법을 사용하여, 이것은 합동 클래스 \(\displaystyle \overline{a}\)의 모듈로 곱셈 역은 다음을 만족하는 합동 클래스 \(\displaystyle \overline{x}\)임을 말함으로써 표현될 수 있습니다:
\(\quad\displaystyle \overline{a} \cdot_m \overline{x} = \overline{1},\)
여기서 기호 \(\displaystyle \cdot_m\)는 동치 클래스 모듈로 m의 곱셈을 나타냅니다. 이런 방법으로 쓰인, 유리수(rational) 또는 실수(real number)의 집합에서 곱셈 역(multiplicative inverse)의 보통의 개념을 갖는 아날로그는 명확하게 표현되며, 그 숫자를 합동 클래스로 대체하고 적절하게 이항 연산(binary operation)을 변경합니다.
실수 위에 유사한 연산과 마찬가지로, 이 연산의 기본적인 용도는, 가능할 때, 다음 형식의 선형 합동을 푸는 것에 있습니다:
\(\quad\displaystyle ax \equiv b \pmod{m}.\)
모듈러 곱셈 역원을 찾는 것은 암호화(cryptography)의 분야, 즉 공개-키 암호화(public-key cryptography)와 RSA 알고리듬(RSA algorithm)에 실용적인 응용을 가집니다. 이들 응용의 컴퓨터 구현에 대해 이점은 모듈러 곱셈 역의 계산에 사용될 수 있는 매우 빠른 알고리듬 (확장된 유클리드 알고리듬(extended Euclidean algorithm))이 있다는 것입니다.
Modular arithmetic
주어진 양의 정수 m에 대해, 두 정수, a와 b는 만약 m이 그것들의 차이를 나누면 합동 모듈로 m이라고 불립니다. 이 이항 관계(binary relation)는 다음에 의해 표시됩니다:
\(\quad\displaystyle a \equiv b \pmod{m}.\)
이것은 정수의 집합, ℤ 위에 동치 관계(equivalence relation)이고, 동치 클래스는 합동 클래스 모듈로 m 또는 잔여 클래스 모듈로 m이라고 불립니다. \(\displaystyle \overline{a}\)가 정수 a를 포함하는 합동 클래스를 나타낸다고 놓으면,
\(\quad\displaystyle \overline{a} = \{b \in \mathbb{Z} \mid a \equiv b \pmod{m} \}.\)
선형 합동(linear congruence)은 다음 형식의 모듈러 합동입니다:
\(\quad\displaystyle ax \equiv b \pmod{m}.\)
실수에 걸쳐 선형 방정식과 달리, 선형 합동은 영, 일, 또는 여러 해를 가질 수 있습니다. 만약 x가 선형 합동의 하나의 해이면 \(\displaystyle \overline{x}\)에서 모든 각 원소는 역시 해이고, 따라서, 선형 합동의 해의 개수를 말할 때 우리는 해를 포함하는 다른 합동 클래스의 개수를 참조합니다.
만약 d가 a와 m의 최대 공통 약수(greatest common divisor)이면, 선형 합동 ax ≡ b (mod m)이 해를 가지는 것과 d가 b를 나누는 것은 필요충분 조건입니다. 만약 d가 b를 나누면, 정확하게 d개의 해가 있습니다.
모듈러스 {{mvar|m}}에 관한 정수 {{mvar|a}}의 모듈러 곱셈 역은 다음 선형 합동의 해입니다:
\(\quad\displaystyle ax \equiv 1 \pmod{m}.\)
이전 결과는 하나의 해가 존재하는 것과 gcd(a, m) = 1, 즉, a와 m이 상대적 소수(relatively prime) (즉, 서로소)여야 하는 것은 필요충분 조건이라고 말합니다. 게다가, 이 조건이 유지될 때, 정확하게 하나의 해가 존재하며, 즉, 그것이 존재할 때, 모듈러 곱셈 역은 고유합니다: 만약 b와 b'이 둘 다 모듈러스 m에 관한 a의 모듈러 곱셈 역이면,
\(\quad\displaystyle ab \equiv ab' \equiv 1 \pmod{m} ,\)
그러므로
\(\quad\displaystyle a(b-b') \equiv 0 \pmod{m}.\)
만약 a ≡ 0 (mod m)이면, gcd(a, m) = a이고, a는 모듈러 곱셈 역을 심지어 가지지 않을 것입니다. 따라서, b ≡ b' (mod m)입니다.
ax ≡ 1 (mod m)가 하나의 해를 가질 때 그것은 종종 다음 방법에서 표현됩니다 −
\(\quad\displaystyle x \equiv a^{-1} \pmod{m},\)
그러나 이것은 표기법의 남용(abuse of notation)으로 고려될 수 있는데 왜냐하면 그것은 \(a\)의 역수(reciprocal)로 잘못 해석될 수 있기 때문입니다 (이것은, 모듈러 곱셈 역과 반대로, a가 1 또는 −1일 때를 제외하고 정수가 아닙니다). 그 표기법은 만약 a가 합동 클래스 \(\displaystyle \overline{a}\)를 나타내는 토큰으로 해석되면 적절하게 될 것인데, 왜냐하면 합동 클래스의 곱셈 역은 다음 섹션에서 정의된 곱셈과 합동 클래스이기 때문입니다.
Integers modulo m
합동 관계, 모듈로 m은 정수 집합을 m 합동 클래스로 분할합니다. 덧셈과 곱셈 연산은 이들 m 대상 위에 다음 방법으로 정의될 수 있습니다: 두 개의 합동 클래스를 더하거나 곱하기 위해, 먼저 각 클래스에서 (어떤 방식으로든) 하나의 대표를 선택하고, 그런-다음 두 대표 위에 정수에 대해 보통 연산을 수행하고 마지막으로 정수 연산의 결과가 합동 클래스 위에 연산의 결과로 놓이는 합동 클래스를 취합니다. 기호에서, 합동 클래스 위에 연산을 나타내는 \(\displaystyle +_m\)와 \(\displaystyle \cdot_m\)와 함께, 이들 정의는 다음과 같습니다:
\(\quad\displaystyle \overline{a} +_m \overline{b} = \overline{a + b}\)
그리고
\(\quad\displaystyle \overline{a} \cdot_m \overline{b} = \overline{ab}.\)
이들 연산은 잘-정의(well-defined)되어 있으며, 최종 결과가 그 결과를 얻을 수 있도록 했던 대표의 선택에 의존하지 않음을 의미합니다.
이들 두 정의된 연산을 갖는 m 합동 클래스는 정수 모듈로 m의 링(ring of integers modulo )이라고 불리는 링(ring)을 형성합니다. 이들 대수적 대상에 대해 사용되는 몇 가지 표기법이 있으며, 가장 자주 \(\displaystyle \mathbb{Z}/m\mathbb{Z}\) 또는 \(\displaystyle \mathbb{Z}/m\)이지만, 몇몇 기본 텍스트와 응용 분야에서는 다른 대수 객체와 혼동될 가능성이 낮을 때 단순화된 표기법 \(\displaystyle \mathbb{Z}_m\)을 사용합니다.
정수 모듈로 m의 합동 클래스는 전통적으로 잔여 클래스 모듈로 m(residue classes modulo m)으로 알려져 있으며, 합동 클래스의 모든 원소가 m에 의해 나뉠 때 같은 나머지 (즉, "잔여")를 갖는다는 사실을 반영합니다. 각각이 다른 합동 클래스 모듈로 m에서 나오도록 선택된 m 정수의 임의의 집합은 잔여 모듈로 m의 완비 시스템(complete system of residues modulo m)이라고 불립니다. 나눗셈 알고리듬(division algorithm)은 정수의 집합 {0, 1, 2, ..., m − 1} 이 최소 잔여 시스템 모듈로 m(least residue system modulo m)으로 알려진 잔여 모듈로 m의 완비 시스템을 형성함을 보여줍니다. 산술 문제를 다룰 때, 때때로 잔여의 완비 시스템으로 작업하고 합동의 언어를 사용하는 것이 더 편리하지만 다른 때에는 링 \(\displaystyle \mathbb{Z}/m\mathbb{Z}\)가 더 유용합니다.
Multiplicative group of integers modulo m
완비 잔여 시스템 모듈로 m의 모든 각 원소가 모듈러 곱셈 역을 가지는 것은 아니며, 예를 들어, 영은 절대 그렇지 않습니다. m에 대한 상대적인 소수가 아닌 완비 잔여 시스템의 원소를 제거한 후, 남은 것은 축소된 잔여 시스템(reduced residue system)이라고 불리며, 그것의 모든 원소는 모듈러 곱셈 역을 가집니다. 축소된 잔여 시스템의 원소의 개수는 \(\displaystyle \phi(m)\)이며, 여기서 \(\displaystyle \phi\)는 오일러 토션트 함수(Euler totient function), 즉, m에 대한 상대적인 소수인 m보다 작은 양의 정수의 개수입니다.
일반적인 단위를 갖는 링(ring with unity)에서, 모든 각 원소가 곱셈 역(multiplicative inverse)을 가지는 것은 아니고 그것을 가지는 그것들은 단위(units)라고 불립니다. 두 단위의 곱이 단위이기 때문에, 링의 단위는 하나의 그룹(group), 링의 단위의 그룹(group of units of the ring)을 형성하고 만약 R이 링의 이름이면 종종 \(R^x\)로 표시됩니다. 정수 모듈로 m의 링의 단위의 그룹은 정수 모듈로 m의 곱셈 그룹(multiplicative group of integers modulo m)이라고 하고, 그것은 축소된 잔여 시스템과 동형(isomorphic)입니다. 특히, 그것은 차수(order) (크기), \(\displaystyle \phi(m)\)을 가집니다.
m이 소수(prime), 말하자면 p이라는 경우에서, \(\displaystyle \phi(p) = p-1\)와 \(\displaystyle \mathbb{Z}/p\mathbb{Z}\)의 모든 비-영 원소는 곱셈 역을 가지고, 따라서 \(\displaystyle \mathbb{Z}/p\mathbb{Z}\)는 유한 필드(finite field)입니다. 이 경우에서, 정수 모듈로 p의 곱셈 그룹은 p − 1 차수의 순환 그룹(cyclic group)을 형성합니다.
Example
임의의 정수 \(\displaystyle n>1\)에 대해, 항상 \(\displaystyle n^2-n+1\)이 모듈러스 \(\displaystyle n^2\)에 관한 \(\displaystyle n+1\)의 모듈러 곱셈 역인 경우인데, 왜냐하면 \(\displaystyle (n+1)(n^2-n+1)=n^3+1\)이기 때문입니다. 예제는 \(\displaystyle 3\times3 \equiv 1 \pmod{4}\), \(\displaystyle 4\times7 \equiv 1 \pmod{9}\), \(\displaystyle 5\times13 \equiv 1 \pmod{16}\), 등입니다.
다음 예제는 모듈러스 10을 사용합니다: 두 정수가 합동 mod 10인 것과 그것들의 차이가 10으로 나눌 수 있는 것은 필요충분 조건입니다. 예를 들어,
\(\quad\displaystyle 32 \equiv 2 \pmod{10}\) 왜냐하면 10은 32 − 2 = 30을 나눕니다, 그리고
\(\quad\displaystyle 111 \equiv 1 \pmod{10}\) 왜냐하면 10은 111 − 1 = 110을 나눕니다.
이 모듈러스에 관한 10가지 합동 클래스 중 일부는 다음과 같습니다:
\(\quad\displaystyle \overline{0} = \{ \cdots, -20, -10, 0, 10, 20, \cdots \}\)
\(\quad\displaystyle \overline{1} = \{ \cdots, -19, -9, 1, 11, 21, \cdots \}\)
\(\quad\displaystyle \overline{5} = \{ \cdots, -15, -5, 5, 15, 25, \cdots \}\) and
\(\quad\displaystyle \overline{9} = \{ \cdots, -11, -1, 9, 19, 29, \cdots \}.\)
선형 합동 4x ≡ 5 (mod 10)는 해를 가지지 않는데 왜냐하면 5와 합동인 정수 (즉, \(\bar{5}\)에서 그것들)는 모두 홀수이지만 4x는 항상 짝수이기 때문입니다. 어쨌든, 선형 합동 4x ≡ 6 (mod 10)는 두 개의 해, 즉, x = 4와 x = 9를 가집니다. gcd(4, 10) = 2와 2는 5를 나누지 않지만, 6은 나눕니다.
gcd(3, 10) = 1이기 때문에, 선형 합동 3x ≡ 1 (mod 10)은 해를 가질 것이며, 즉, 3 모듈로 10의 모듈러 곱셈 역은 존재할 것입니다. 사실, 7은 이 합동을 만족합니다 (즉, 21 − 1 = 20). 어쨌든, 다른 정수도 합동을 만족합니다. 예를 들어 17과 −3 (즉, 3(17) − 1 = 50 및 3(−3) − 1 = −10)입니다. 특히, \(\bar{7}\)에 있는 모든 정수는 합동을 만족할 것인데, 왜냐하면 이들 정수는 일부 정수 r에 대해 7 + 10r 형식을 가지고 다음은
\(\quad\displaystyle 3(7 + 10 r) - 1 = 21 + 30 r -1 = 20 + 30 r = 10(2 + 3r), \)
10에 의해 나뉘기 때문입니다. 이 합동은 오직 하나의 해의 합동 클래스를 가집니다. 이 경우에서 해는 모든 가능한 경우를 확인함으로써 얻을 수 있었지만, 더 큰 모듈러스에 대해 시스템적인 알고리듬이 필요하고 이것들은 다음 섹션에서 설명될 것입니다.
합동 클래스 \(\displaystyle \overline{5}\)와 \(\displaystyle \overline{8}\)의 곱은 \(\displaystyle \overline{5}\)의 원소, 말하자면 25와 \(\displaystyle \overline{8}\)의 원소, 말하자면 −2를 선택하고 그것들의 곱 (25)(−2) = −50이 합동 클래스 \(\displaystyle \overline{0}\)에 있음을 관찰함으로써 얻을 수 있습니다. 따라서, \(\displaystyle \overline{5} \cdot_{10} \overline{8} = \overline{0}\)입니다. 덧셈은 같은 방법으로 정의됩니다. 십 합동 클래스와 함께 합동 클래스의 덧셈과 곱셈의 이들 연산은 정수 모듈로 10의 링, 즉, \(\displaystyle \mathbb{Z}/10\mathbb{Z}\)을 형성합니다.
완비 잔여 시스템 모듈로 10은 집합 {10, −9, 2, 13, 24, −15, 26, 37, 8, 9}일 수 있으며, 여기서 각 정수는 다른 합동 클래스 모듈로 10에 있습니다. 고유한 최소 잔여 시스템 모듈로 10은 {0, 1, 2, ..., 9}입니다. 축소된 잔여 시스템 모듈로 10은 {1, 3, 7, 9}일 수 있습니다. 이들 숫자에 의해 표현되는 임의의 두 합동 클래스의 곱은 다시 이들 네 가지 합동 클래스 중 하나입니다. 이것은 이들 네 개의 합동 클래스가 그룹을 형성한다는 것을 의미하며, 이 경우에서 3 또는 7을 (곱셈) 생성기로 가지는 차수 4의 순환 그룹입니다. 표시된 합동 클래스는 링의 단위 그룹, \(\displaystyle \mathbb{Z}/10\mathbb{Z}\)을 형성합니다. 이들 합동 클래스는 정확하게 모듈러 곱셈 역을 가지는 클래스입니다.
Computation
Extended Euclidean algorithm
a 모듈러 m의 모듈러 곱셈 역은 확장된 유클리드 알고리듬을 사용하여 구할 수 있습니다.
유클리드 알고리듬(Euclidean algorithm)은 두 정수, 말하자면 a와 m의 최대 공통 약수 (gcd)를 결정합니다. 만약 a가 곱셈 역 모듈로 m를 가지면, 이 gcd는 1이어야 합니다. 알고리듬에 의해 생성된 여러 방정식 중 마지막 방정식은 이 gcd에 대해 풀릴 수 있습니다. 그런-다음, "역 치환"이라는 방법을 사용하여, 원래 매개변수와 이 gcd를 연결하는 표현식이 구할 수 있습니다. 다시 말해서, 정수 x와 y는 베주의 항등식(Bézout's identity)을 만족시키기 위해 구할 수 있으며,
\(\quad\displaystyle ax + my = \gcd(a, m)= 1.\)
다시 쓰이면, 이것은 다음입니다:
\(\quad\displaystyle ax - 1 = (-y)m,\)
즉,
\(\quad\displaystyle ax \equiv 1 \pmod{m},\)
따라서, a의 모듈러 곱셈 역은 계산되었습니다. 알고리듬의 더 효율적인 버전은, 보조 방정식을 사용함으로써, 알고리듬을 통한 두 개의 패스를 단 하나로 줄이는 확장된 유클리드 알고리듬입니다 (역 치환은 알고리듬을 역으로 통과하는 것으로 생각될 수 있습니다.).
큰 O 표기법(big O notation)에서, 이 알고리듬은 |a| < m을 가정하여 시간 \(\text{O}(\log^2(m))\) O(log2(m))에서 실행하고, 그 대안, 지수화보다 매우 빠르고 일반적으로 더 효율적인 것으로 여겨집니다.
Using Euler's theorem
확장된 유클리드 알고리듬의 대안으로, 오일러의 정리는 모듈러 역을 계산하기 위해 사용될 수 있습니다.
오일러의 정리(Euler's theorem)에 따르면, 만약 a가 m과 서로소(coprime), 즉, gcd(a, m) = 1이면,
\(\quad\displaystyle a^{\phi(m)} \equiv 1 \pmod{m},\)
여기서 \(\displaystyle \phi\)는 오일러의 토션트 함수(Euler's totient function)입니다. 이것은 a가 곱셈 그룹 \(\displaystyle (\mathbb{Z}/m\mathbb{Z})^{\times}\)에 속하는 것과 a가 m과 서로소(coprime)인 것은 필요충분 조건이라는 사실에서 비롯됩니다. 그러므로, 모듈러 곱셈 역은 직접 구할 수 있습니다:
\(\quad\displaystyle a^{\phi(m)-1} \equiv a^{-1} \pmod{m}.\)
m이 서로소인 특별한 경우에서, \(\displaystyle \phi (m) = m - 1\)이고 모듈러 역은 다음에 의해 제공됩니다:
\(\quad\displaystyle a^{-1} \equiv a^{m-2} \pmod{m}.\)
이 방법은 일반적으로 확장된 유클리드 알고리듬보다 느리지만, 모듈러 지수화에 대한 구현이 이미 사용 가능한 경우에 가끔 사용됩니다. 이 방법의 몇 가지 단점은 다음과 같습니다:
- 값 \(\displaystyle \phi (m)\)이 알려져 있어야 하고 가장 효율적인 알려진 계산은 m의 인수분해(factorization)를 요구합니다. 인수분해는 계산적으로 어려운 문제로 널리 알려져 있습니다. 어쨌든, \(\displaystyle \phi (m)\)을 계산하는 것은 m의 소수 인수분해가 알려져 있을 때 간단합니다.
- 지수의 상대 비용. 비록 그것이 모듈러 지수(modular exponentiation)를 사용하여 더 효율적으로 구현될 수 있을지라도, m의 큰 값이 포함될 때 이것은 몽고메리 감소(Montgomery reduction) 방법으로 가장 효율적으로 계산됩니다. 이 알고리듬 자체는 모듈러 역 mod m을 필요로 하며, 이는 처음 위치에 계산되어야 했던 것입니다. 몽고메리 방법 없이, 모든 각 단계에서 나눗셈 mod m을 요구하는 표준 이항 지수(binary exponentiation)는 m이 클 때 느린 연산입니다.
이 기법의 한 가지 주목할만한 장점은 a의 값에 의존하는 조건부 분기가 없고, 따라서 공개 키 암호화(public-key cryptography)에서 중요한 비밀일 수 있는 a의 값은 부-채널 공격(side-channel attacks)으로부터 보호될 수 있다는 것입니다. 이러한 이유로, Curve25519의 표준 구현은 역을 계산하기 위해 이 기법을 사용합니다.
Multiple inverses
유클리드 알고리듬의 단일 호출과 추가 입력당 세 개의 곱셈을 갖는 여러 숫자 ai의 역수, 모듈로 공통 m의 계산하는 것이 가능합니다. 기본 아이디어는 모든 \(a_i\)의 곱을 형성하고, 그것을 반전하고, 그린-다음 모든 j ≠ i에 대해 \(a_j\)를 곱하여 원하는 \(a_i^{-1}\)만 남기는 것입니다.
보다 구체적으로, 그 알고리듬은 다음입니다 (모듈로 m을 수행된 모든 산술):
- 모든 i ≤ n에 대해 접두 곱(prefix products) \(\displaystyle b_i = \prod_{j=1}^i a_j = a_i b_{i-1}\)을 계산하십시오.
- 임의의 사용 가능한 알고리듬을 사용하여 \(b_n^{-1}\)를 계산하십시오.
- n에서 2로 내려가며 i에 대해, 계산하십시오
- \(a_i^{-1} = b_i^{-1}b_{i-1}\) 그리고
- \(b_{i-1}^{-1} = b_i^{-1}a_{i}\)
- 마지막으로, \(a_1^{-1} = b_1^{-1}\)
병렬 컴퓨팅(parallel computing)을 활용하기 위해 선형이 아닌 트리 구조에서 곱셈을 수행하는 것이 가능합니다.
Applications
모듈러 곱셈 역을 찾는 것은 모듈러 산술 이론에 의존하는 알고리듬에 많은 응용을 가집니다. 예를 들어, 암호화에서 모듈러 산술의 사용은 일부 연산을 더 적은 저장 요구 사항으로 더 빠르게 수행될 수 있지만, 다른 연산은 더 어렵게 됩니다. 이들 두 가지 기능 모두 이점을 가지고 사용될 수 있습니다. 특히, RSA 알고리듬에서, 메시지 암호화화 암호 해독은 신중하게 선택한 계수에 대해 곱셈 역인 숫자 쌍을 사용하여 수행됩니다. 이들 숫자 중 하나는 공개되어 빠른 암호화 절차에 사용될 수 있고, 다른 하나는 암호 해독 절차에 사용되는 동안 숨겨져 있습니다. 공개 숫자에서 숨겨진 숫자를 결정하는 것은 계산적으로 불가능한 것으로 고려되고 이것이 시스템이 개인 정보를 보장하기 위해 작동하게 하는 것입니다.
다른 상황의 또 다른 예로서, 각각 k로 나누어지는 홀수-단어 크기의 숫자 목록을 가지고 그것들을 모두 k로 나누기를 원하는 컴퓨터 과학에서 정확한 나눗셈 문제를 생각해 보십시오:
- \(k^{-1}, k\mbox{ mod } 2^w\)의 모듈러 곱셈 역을 계산하기 위해 확장된 유클리드 알고리듬을 사용하십시오. 여기서 w는 단어에서 비트의 개수입니다. 그 숫자가 홀수이고 모듈러스가 홀수 인수를 가지지 않기 때문에 이 역은 존재할 것입니다.
- 목록에서 각 숫자에 대해, \(k^{-1}\)을 곱하고 결과의 최하위 단어를 취합니다.
많은 기계, 특히 나눗셈에 대한 하드웨어 지원이 없는 기계에서, 나눗셈은 곱셈보다 느린 연산이므로, 이 접근 방식은 상당한 속도 향상을 가져올 수 있습니다. 첫 번째 단계는 상대적으로 느리지만 한 번만 수행하면 됩니다.
모듈러 곱셈 역은 중국의 나머지 정리(Chinese Remainder Theorem)에 의해 보장되는 선형 합동 시스템의 해를 얻기 위해 사용됩니다.
예를 들어, 다음 시스템은
- X ≡ 4 (mod 5)
- X ≡ 4 (mod 7)
- X ≡ 6 (mod 11)
공통 해를 가지는데 왜냐하면 5,7, 및 11은 쌍별 서로소(coprime)이기 때문입니다. 하나의 해는 다음에 의해 제공됩니다:
- \(X=t_1 (7\times 11) \times 4 + t_2 (5\times 11) \times 4+ t_3(5\times 7)\times 6\)
여기서
- \(t_1=3\)는 7 × 11 (mod 5)의 모듈러 곱셈 역이고,
- \(t_2=6\)는 5 × 11 (mod 7)의 모듈러 곱셈 역이고
- \(t_3=6\)는 5 × 7 (mod 11)의 모듈러 곱셈 역입니다.
따라서,
- \(X=3 \times (7\times 11) \times 4 + 6 \times (5\times 11) \times 4+ 6 \times (5\times 7)\times 6 = 3504\)
그리고 그것의 고유한 축소된 형식에서
\(\quad X \equiv 3504 \equiv 39 (\mbox{mod } 385)\)
왜냐하면 385는 5,7, 및 11의 LCM이기 때문입니다.
역시, 모듈러 곱셈 역은 크로스투만 합(Kloosterman sum)의 정의에서 두드러지게 나타납니다.
References
- Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2nd ed.), Springer-Verlag, ISBN 0-387-97329-X
- Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, ISBN 978-0-201-57889-8
- Schumacher, Carol (1996). Chapter Zero: Fundamental Notions of Abstract Mathematics. Addison-Wesley. ISBN 0-201-82653-4.
- Trappe, Wade; Washington, Lawrence C. (2006), Introduction to Cryptography with Coding Theory (2nd ed.), Prentice-Hall, ISBN 978-0-13-186239-5
External links
- Weisstein, Eric W. "Modular Inverse". MathWorld.
- Guevara Vasquez, Fernando provides a solved example of solving the modulo multiplicative inverse using Euclid's Algorithm
