제 2장 암호 수학 Part I: 모듈로 연산, 합동 및 행렬

Chapter 2 Objectives 가분성(divisibility), 유클리드(Euclidean) 알고리즘을 이용하여 최대 공약수를 찾는 방법과 관련 있는 정수 연산 확장 유클리드 알고리즘을 이용하여 일차 디오판투스 방정식 (Diophantine Equations), 일차 합동 방정식을 푸는 방법과 곱셈에 대한 역원을 찾는 방법 암호에서의 모듈로 연산의 중요성과 모듈로 연산자를 중점적으로 다룬다. 암호에 널리 이용되는 잉여행렬에 적용되는 행렬과 연산 잉여 행렬(residue matrices)을 이용하여 합동 방정식들을 푸는 방법

Topics discussed in this section: 2-1 정수 연산 (INTEGER ARITHMETIC) 정수 연산에서는 집합(set)과 몇 개의 연산을 사용한다. 독자들이 집합 및 관련 연산에 익숙하겠지만, 이 절에서는 모듈러 연산의 기본 지식을 학습하도록 하자. Topics discussed in this section: 2.1.1 정수의 집합 2.1.2 이진 연산 2.1.3 정수의 나눗셈 2.1.4 가분성 2.1.5 일차 디오판투스 방정식

2.1.1 정수의 집합 정수 집합, 는 음의 무한대에서부터 양의 무한대까지, (분수가 아닌) 모든 정수 2.1.1 정수의 집합 정수 집합, 는 음의 무한대에서부터 양의 무한대까지, (분수가 아닌) 모든 정수 Figure 2.1 정수 집합

2.1.2 이진연산 암호에서는 정수 집합에 적용되는 세 가지 이진 연산을 주로 사용한다. 이진 연산은 입력값 2 개에 대하여 하나의 결과값을 산출한다. Figure 2.2 정수 집합에 대한 세 가지 이진 연산

2.1.2 Continued Example 2.1 다음은 두 정수에 대한 세 가지 이진 연산의 결과를 나타낸다. 입력값 각각이 양수나 음수 이므로, 각 연산에 대하여 4가지 경우가 존재한다.

2.1.3 정수의 나눗셈 정수연산에서, a를 n으로 나누면, q와 r을 얻는다. 이 네 정수 사이의 관계는 다음과 같다. a = q × n + r

2.1.3 Continued Example 2.2 a = 255 이고 n = 11이라고 가정하면, 그림 2.3에 보이는 것처럼 나눗셈 알고리즘을 사용하여 q = 23 이고 r = 2 라는 것을 알 수 있다. Figure 2.3 예 2.2에서 몫과 나머지를 찾아내는 방법

2.1.3 Continued Figure 2.4 정수의 나눗셈 알고리즘

2.1.3 Continued Example 2.3 컴퓨터나 계산기를 사용하면, a가 음수 일 경우, q와 r은 음수이다. r이 양수여야 한다는 제약 사항을 어떻게 적용할 수 있을까? 답은 간단하다. q에서 1을 빼고, r에 n을 더하여 양수로 만든다.

2.1.3 Continued Figure 2.5 나눗셈 알고리즘의 그래프

2.1.4 가분성 a = q × n 나눗셈 관계식에서 a 가 0이 아니고, r = 0 이라고 하면, 다음의 식을 얻는다. 2.1.4 가분성 나눗셈 관계식에서 a 가 0이 아니고, r = 0 이라고 하면, 다음의 식을 얻는다. a = q × n 만약 나머지가 0이라면 만약, 나머지가 0이 아니라면

2.1.4 Continued Example 2.4 32 = 8 × 4 이기 때문에 4는 32를 나누고, 다음과 같이 표현한다 32 = 8 × 4 이기 때문에 4는 32를 나누고, 다음과 같이 표현한다 b. 42 = 5 × 8 + 2이기 때문에 8은 42를 나누지 않는다. 나머지가 2가 존재한다. 그러므로 나누지 못하는 것을 다음과 같이 표현한다

특성 2.1.4 Continued Property 1: 만약 a|1이라면 a = ±1. Property 2: 만약 a|b 이고 b|a 라면 a = ±b. Property 3: 만약 a|b 이고 b|c 라면 a|c. Property 4: 만약 a|b 이고 a|c 라면 a|(m × b + n × c)이 된다. 여기서 m 과 n 은 임의의 정수

2.1.4 Continued Example 2.5 b.

특성(properties) 다음은 나눗셈의 몇 가지 특성이다. 증명에 관심이 있는 독자는 부록 Q를 참조하여라. 속성 1: 만약 이면 속성 2: 만약 이고 이면 속성 3: 만약 이고 이면 속성 4: 만약 이고 이면 , 여기서 과 은 임의의 정수

2.1.4 Continued 3|15 이고, 15|45 이기 때문에, 3번째 속성에 의하여, 3|45이다. Example 2.6  3|15 이고, 15|45 이기 때문에, 3번째 속성에 의하여, 3|45이다. 3|15 이고 3|9이기 때문에, 4 번째 속성에 의하면, 3|(15 x 2 +9 x 4)이고, 따라서 3|66이다.

Fact 2: 모든 양의 정수는 최소 2개의 약수(1과 자기자신)를 가진다(2개 이상도 가능) 2.1.4 Continued Note Fact 1: 정수 1은 하나의 약수, 1만을 갖는다. Fact 2: 모든 양의 정수는 최소 2개의 약수(1과 자기자신)를 가진다(2개 이상도 가능)

최대공약수(Greatest Common Divisor) 암호에서는 때때로 두 양의 정수 최대공약수를 필요로 한다. 두 양의 정수는 많은 공약수를 가질 수 있지만 하나의 최대공약수를 가진다. 예를 들어, 12와 140의 공약수는 1, 2, 4 이다. 그러나 최대공약수는 4 이다. 그림 2.6을 참조하여라.

2.1.4 Continued Figure 2.6 두 정수의 공약수

두 양의 정수의 최대공약수는 두 정수를 나누는 가장 큰 정수 이다. 2.1.4 Continued Note 최대 공약수 두 양의 정수의 최대공약수는 두 정수를 나누는 가장 큰 정수 이다. Note 유클리드 알고리즘 Fact 1: gcd (a, 0) = a Fact 2: gcd (a, b) = gcd (b, r), 여기서 r 은 a 를 b 로 나눈 나머지이다.

2.1.4 Continued Figure 2.7 유클리드 알고리즘

서로소( relatively prime)라고 한다. 2.1.4 Continued Note gcd (a, b) = 1일 경우에, a 와 b 는 서로소( relatively prime)라고 한다. Note When gcd (a, b) = 1, we say that a and b are relatively prime.

2.1.4 Continued 2740과 1760의 최대공약수를 계산하시오. Example 2.7 Solution gcd (2740, 1760) = 20 이다.

2.1.4 Continued 25 와 60의 최대공약수를 계산하시오. Example 2.8 Solution gcd (25, 65) = 5 이다.

2.1.4 Continued 확장 유클리드 알고리즘 (Extended Euclidean Algorithm) 두 정수 a 와 b가 주어졌을 때, 다음 식을 만족하는 다른 두 정수 계산해야 할 필요가 있다. 확장 유클리드 알고리즘은 gcd (a, b) 를 계산할 수 있을 뿐만 아니라, 동시에 s 와 t 값을 계산할 수 있다.

2.1.4 Continued Figure 2.8.a 확장 유클리드 알고리즘 part a

2.1.4 Continued Figure 2.8.b 확장 유클리드 알고리즘 part b

2.1.4 Continued a = 161 이고 b = 28 일때, gcd (a, b)와 s, t 값을 계산하시오. Example 2.9 a = 161 이고 b = 28 일때, gcd (a, b)와 s, t 값을 계산하시오. Solution gcd (161, 28) = 7 이고, s = −1 이며 t = 6이다.

2.1.4 Continued a = 17 이고 b = 0 일때, gcd (a, b)와s, t의 값을 구하시오. Example 2.10 a = 17 이고 b = 0 일때, gcd (a, b)와s, t의 값을 구하시오. Solution gcd (17, 0) = 17이고, s = 1, t = 0이다.

2.1.4 Continued a = 0 이고 b = 45 일때, gcd (a, b)와 s, t의 값을 구하시오. Example 2.11 a = 0 이고 b = 45 일때, gcd (a, b)와 s, t의 값을 구하시오. Solution gcd (0, 45) = 45이고, s = 0 이며, t = 1이다.

2.1.4 Continued 2변수 일차 디오판투스 방정식은 ax + by = c 이다. Note 일차 디오판투스 방정식 (Linear Diophantine Equation) Note 2변수 일차 디오판투스 방정식은 ax + by = c 이다.

특수해 (Particular solution): x0 = (c/d)s 와 y0 = (c/d)t 2.1.4 Continued Linear Diophantine Equation Note 특수해 (Particular solution): x0 = (c/d)s 와 y0 = (c/d)t Note 일반해 (General solutions): x = x0 + k (b/d) 와 y = y0 − k(a/d) 이다. 여기서 k 는 정수이다.

2.1.4 Continued 방정식 21x + 14y = 35의 특수해와 일반해를 계산하여라. Example 2.12 Solution

2.1.4 Continued Example 2.13 다른 값을 갖는 물체의 여러 조합을 찾아내고자 할 때, 실생활에서 매우 흥미롭게 응용될 수 있다. 예를 들어, 100달러 수표를 20달러와 5달러짜리로 현금화한다고 가정하자. 많은 선택법이 있을 수 있는데, 이와 대응되는 디오판투스 방정식 20x + 5y = 100을 풀어 그 선택법들을 찾을 수 있다.

2.1.4 Continued Example 2.13 d = gcd (20, 5) = 5 이고 5 | 100이므로, 그 방정식은 많은 해를 갖는다. 그러나 이 경우 그 해 중 몇 개(x , y 가 모두 음의 정수가 아닌 답)만을 선택할 수 있다. 양변을 5로 나누면 4x + y = 20이 된다. 방정식 4s + t = 1을 확장 유클리드 알고리즘으로 풀면 s = 0, t = 1 을 얻는다. 특수해는 이고, x, y 가 음수가 아닌 일반해는 다음과 같다. (0, 20), (1, 16), (2, 12), (3, 8), (4, 4), (5, 0).

Topics discussed in this section: 2-2 모듈러 연산 (MODULAR ARITHMETIC) 앞 절에서 논의된 나눗셈 관계식 (a = q × n + r) 은 두 개의 입력값 (a, n)과 두 개의 출력값 (q, r)을 갖는다. 모듈러 연산에서는 하나의 결과값, 즉 나머지 r에만 관심이 있고 몫 q는 신경을 쓰지 않는다. Topics discussed in this section: 2.2.1 모듈러 연산자(Modular Operator) 2.2.2 잉여류(Set of Residues) 2.2.3 합동(Congruence) 2.2.4 Zn 에서의 연산( Operations in Zn ) 2.2.5 덧셈과 곱셈표(Addition and Multiplication Tables) 2.2.6 다른 두 집합(Different Sets)

2.2.1 모듈러 연산자(Modulo Operator) 두 번째 입력값 (n) 은 모듈러(modulus)라고 하고, 결과값 r 은 나머지(residue)라고 한다. Figure 2.9 나눗셈 관계식과 모듈러 연산자

2.1.4 Continued Example 2.14 다음의 연산값은? : a. 27 mod 5 b. 36 mod 12 c. −18 mod 14 d. −7 mod 10 Solution Dividing 27 by 5 results in r = 2 Dividing 36 by 12 results in r = 0. c. Dividing −18 by 14 results in r = −4. After adding the modulus r = 10 d. Dividing −7 by 10 results in r = −7. After adding the modulus to −7, r = 3.

2.2.2 잉여류(Set of Residues) 모듈러 을 이용하는 모듈러 연산의 결과는 항상 0과 n-1사이의 정수값이다. 즉, a mod n의 결과값은 항상 n보다 작은 음이 아닌 정수값이다. 모듈러 연산자는 하나의 집합을 생성하는데, 모듈러 연산에서 이 집합을 모듈러 의 최소 잉여 집합 또는 Zn 이라 한다. Figure 2.10 몇 가지 Zn 집합의 예

2.2.3 합동(Congruence) 두 정수가 합동임을 보이기 위해서는 합동 연산자()를 사용한다. 관계식을 성립하게 하는 모듈러 값을 표현하기 위하여 합동의 오른쪽에 ( ≡ )을 붙인다. 예를 들어, 다음과 같이 기록한다.

2.2.3 Continued Figure 2.11 합동의 개념

2.2.3 Continued 잉여류 (Residue Classes) 잉여류 [a] 나 [a]n 은 모듈로 n에 합동인 정수들로 이루어진 집합이다.

2.2.3 Continued Figure 2.12 그래프를 이용한 Z 와 Zn 의 비교

2.2.3 Continued Example 2.15 일상생활에서 모듈러 연산을 사용하는 예로 시계를 들 수 있다. 이것은 모듈러 12를 이용하고 0대신에 12를 사용한다. 따라서 시계 시스템은 0(또는 12)으로 시작하여 11까지 간다.

2.2.4 Zn 에서의 연산(Operation in Zn ) 집합 Z에서 논의했던 세 개의 이진 연산자 (덧셈, 뺄셈, 곱셈) 역시 집합 Zn 에 정의될 수 있다. 그림 2.13에 표현된 mod 연산자를 사용하여 결과값을 Zn 에 대응시켜야 한다. Figure 2.13 Zn에서의 이진 연산

2.2.4 Continued 다음 연산을 수행하여라. (입력값은 Zn 에서 선택됨): Example 2.16 다음 연산을 수행하여라. (입력값은 Zn 에서 선택됨): a. Z15 위에서 7 과 14 를 더하라. b. Z13 위에서 7 에서 11 을 빼라. c. Z20 위에서 7 과 11 을 곱하여라. Solution

2.2.4 Continued 다음 연산을 수행하여라. (입력값은 Z 나 Zn에서 선택됨): Example 2.17 다음 연산을 수행하여라. (입력값은 Z 나 Zn에서 선택됨): a. Z14 위에서 17 과 27 을 더하라. b. Z13 위에서 12 에서 43을 빼라. c. Z19 위에서 123 과 -10 을 곱하여라. Solution

2.2.4 Continued 특성 우리는 모듈러 연산에서 세 개의 이진 연산의 두 입력값은 Z 나 Zn 에서 선택될 수 있다는 것을 언급하였다. 다음 성질들은 세 개의 이진 연산(+,-,×)을 적용하기 전에, ( Z 에서 선택되었다면) 두 입력값을 Zn에 우선 대응시킬 수 있도록 해준다. 이 특성들에 대한 증명은 부록 Q에 수록되어 있다.

2.2.4 Continued 특성 1 3 2

2.2.4 Continued Figure 2.14 모드 연산자의 성질

2.2.4 Continued 다음은 위의 특성들을 응용한 예이다. Example 2.18 다음은 위의 특성들을 응용한 예이다. 1. (1,723,345 + 2,124,945) mod 11 = (8 + 9) mod 11 = 6 2. (1,723,345 − 2,124,945) mod 16 = (8 − 9) mod 11 = 10 3. (1,723,345 × 2,124,945) mod 16 = (8 × 9) mod 11 = 6

2.2.4 Continued 정수론에서, 때때로 10의 지수승을 정수로 나눌 때, 나머지를 계산해야 할 필요가 있다. Example 2.19 정수론에서, 때때로 10의 지수승을 정수로 나눌 때, 나머지를 계산해야 할 필요가 있다.

2.2.4 Continued Example 2.20 정수론에서, 정수를 으로 나눈 나머지는 그 정수의 각 자리수의 합을 나눈 나머지와 같다고 한다. 정수를 10의 지수승과 각 자리수를 곱한 것의 합으로 표현한다.

2.2.5 역원(Inverses) 모듈러 연산을 할 때, 종종 연산에 대한 어떤 수의 역원을 계산해야 할 경우가 있다. 일반적으로 덧셈에 대한 역원과 곱셈에 대한 역원을 계산한다.

2.2.5 Continue 덧셈에 대한 역원(Additive Inverse) Zn에서 두 개의 수 a 와 b 는 다음의 경우 서로가 덧셈에 대한 역원이 된다. Note 모듈러 연산에서, 각각의 정수는 덧셈에 대한 역원을 갖는다. 어떤 정수와 그 정수의 덧셈에 대한 역원의 합은 모듈러 n에 대하여 0과 합동이다.

2.2.5 Continued Z10 에서 모든 덧셈에 대한 역원 쌍을 찾아라. 덧셈에 대한 역원의 6개 쌍은 Example 2.21 Z10 에서 모든 덧셈에 대한 역원 쌍을 찾아라. Solution 덧셈에 대한 역원의 6개 쌍은 (0, 0), (1, 9), (2, 8), (3, 7), (4, 6), (5, 5) 이다.

2.2.5 Continue 곱셈에 대한 역원(Multiplicative Inverse) Zn에서 두 개의 수 a 와 b 가 다음을 만족하면 서로가 곱셈에 대한 역원이 된다. Note 모듈러 연산에서, 정수는 곱셈에 대한 역원이 있을 수도 있고 없을 수도 있다. 만약 곱셈에 대한 역원이 있다면, 그 정수와 해당하는 곱셈에 대한 역원의 곱은 모듈러 n에서 1과 합동이다.

2.2.5 Continued Z10에서 8의 곱셈에 대한 역원을 계산하여라. Solution Example 2.22 Z10에서 8의 곱셈에 대한 역원을 계산하여라. Solution gcd (10, 8) = 2 ≠ 1이기 때문에 역원이 존재하지 않는다. 즉, 8을 곱하여 그 결과가 1과 합동이 되는 수를 0부터 9사이에서 찾을 수 없다.

2.2.5 Continued Z10에서 곱셈에 대한 모든 역원을 찾아라. Solution Example 2.23 Z10에서 곱셈에 대한 모든 역원을 찾아라. Solution 다음과 같은 세 쌍의 역원, (1, 1), (3, 7) 와 (9, 9)이 존재한다. 0, 2, 4, 5, 6, 와 8 은 곱셈에 대한 역원을 갖지 않는다.

2.2.5 Continued Z11 에서 모든 곱셈에 대한 역원을 찾아라. Solution 다음의 7쌍의 역원 Example 2.24 Z11 에서 모든 곱셈에 대한 역원을 찾아라. Solution 다음의 7쌍의 역원 : (1, 1), (2, 6), (3, 4), (5, 9), (7, 8), (9, 9), 와 (10, 10) 이 존재한다.

확장 유클리드 알고리즘을 이용하면, n 과 b 가 주어지고, gcd (n, b) = 1일 때, 2.2.5 Continued Note 확장 유클리드 알고리즘을 이용하면, n 과 b 가 주어지고, gcd (n, b) = 1일 때, Zn에서 b의 곱셈에 대한 역원을 찾아낼 수 있다. b의 곱셈에 대한 역원은 t를 Zn 에대응시킨 값이다.

2.2.5 Continued Figure 2.15 확장 유클리드 알고리즘을 이용한 곱셈에 대한 역원 찾기

2.2.5 Continued Z26에서 11의 곱셈에 대한 역원을 계산하여라. Example 2.25 Z26에서 11의 곱셈에 대한 역원을 계산하여라. Solution gcd (26, 11) 는 1이다. 11의 역원은 -7 이거나 19이다.

2.2.5 Continued Z100 위에서 23의 곱셈에 대한 역원을 구하라 . Example 2.26 Z100 위에서 23의 곱셈에 대한 역원을 구하라 . Solution gcd (100, 23)=1이다. 23 의 역원은 -13 이거나 87이다.

2.2.5 Continued Z26위에서 12의 역원을 구하라. gcd (26, 12) 는 2이다. 역원은 존재하지 않는다. Example 2.27 Z26위에서 12의 역원을 구하라. Solution gcd (26, 12) 는 2이다. 역원은 존재하지 않는다.

2.2.6 Addition and Multiplication Tables Figure 2.16 Z10에 대한 덧셈과 곱셈표

2.2.7 Different Sets Figure 2.17 Zn 과 Zn* 에 대한 예

덧셈에 대한 역원이 필요할 때는 Zn을 사용해야 하지만, 곱셈에 대한 역원이 필요할 때는 Zn*를 사용해야 한다. 2.2.7 Different Sets Note 덧셈에 대한 역원이 필요할 때는 Zn을 사용해야 하지만, 곱셈에 대한 역원이 필요할 때는 Zn*를 사용해야 한다.

2.2.8 다른 두 집합(Two More Sets) 암호는 종종 두 개 이상의 집합, 즉, Zp 와 Zp*를 사용한다. 이 두 집합에서 모듈러는 소수이다. 이후의 장에서 논의되겠지만, 소수는 단지 두 개의 약수, 즉 과 자기 자신으로만 나눠진다는 것만 알면 충분하다.

Topics discussed in this section: 2-3 MATRICES 암호에서는 행렬 연산이 필요하다. 이 주제가 선형 대수라는 대수학의 특정 분야에 속해 있지만, 행렬에 대한 다음의 간단한 고찰은 암호 연구를 위해 필요한 기본사항이다. 이 주제에 익숙한 독자들은 이 절의 일부나 전부를 건너뛰어도 된다. Topics discussed in this section: 2.3.1 Definitions 2.3.2 Operations and Relations 2.3.3 Determinants 2.3.4 Residue Matrices

2.3.1 정의(Definition ) Figure 2.18 l × m 크기의 행렬

2.3.1 Continued Figure 2.19 매트릭스의 예

2.3.2 Operations and Relations Example 2.28 그림 2.20은 행렬의 덧셈과 뺄셈의 예를 보여준다. Figure 2.20 행렬의 덧셈과 뺄셈

2.3.2 Continued Example 2. 29 그림 2.21은 행 행렬 (1 × 3) 과 열 행렬 (3 × 1)의 곱을 나타낸다. 그 결과로 1 × 1크기의 행렬이 생성된다. Figure 2.21 행 행렬과 열 행렬의 곱

2.3.2 Continued Example 2. 30 그림 2.22는 2 × 3 행렬과 3 × 4 행렬의 곱을 나타낸다. 그 결과로 2 × 4 크기의 행렬이 생성된다. Figure 2.22 2 × 3 행렬과 3 × 4 행렬의 곱

2.3.2 Continued 그림 2.23에는 스칼라 곱의 예가 나타나 있다. Example 2. 31 Figure 2.23 스칼라 곱

2.3.3 Determinant 행렬식은 정방행렬에서만 정의된다. 크기가 m × m 인 정방행렬 A의 행렬식은 det (A)로 표기되며, 다음과 같이 귀납적으로 계산되는 스칼라 값이다. Note 행렬식은 정방행렬에서만 정의된다.

2.3.3 Continued Example 2. 32 그림 2.24는 위의 귀납적 정의를 이용하여, 어떻게 1 × 1 행렬의 행렬식에 근거하여 2 × 2 행렬의 행렬식을 계산하는지 보여준다. 이 예는 m이 1이거나 2일 때, 행렬의 행렬식을 매우 쉽게 계산할 수 있다는 것을 보여준다. Figure 2.24 2 ×2 행렬의 행렬식 계산

2.3.3 Continued 그림 2.25는 3 × 3 행렬의 행렬식 계산을 보여준다. Example 2. 33 Figure 3 × 3 행렬의 행렬식 계산

곱셈에 대한 역행렬은 정방행렬에서만 정의된다. 2.3.4 Inverses Note 곱셈에 대한 역행렬은 정방행렬에서만 정의된다.

2.3.5 잉여 행렬(Residue Matrices ) 암호는 잉여 행렬, 즉 모든 행렬의 원소가 Zn에 속하는 행렬을 사용한다. 잉여 행렬은 gcd (det(A), n) = 1이면 곱셈에 대한 역행렬을 갖는다. Example 2. 34 Figure 2.26 잉여행렬과 곱셈에 대한 역행렬

합동(Residue Matrices ) 합동 (Congruence) 두 행렬이 열과 행의 개수가 같고 모든 대응되는 원소가 모듈로 n에 대하여 합동이면, 그 두 행렬은 모듈로 n에 대하여 합동이라고 하고, A ≡ B mod n라고 표기한다. 즉, 모든 i와 j에 대해 aij ≡ bij mod n이면, A ≡ B mod n이다.

Topics discussed in this section: 2-4 LINEAR CONGRUENCE 암호에서는 때때로 하나 이상의 Zn에 속한 계수를 갖는 방정식이나 그러한 방정식의 집합을 풀어야 할 경우가 있다. 이 절에서는 각 변수의 계수가 1인 방정식(선형 방정식)을 어떻게 푸는지 살펴본다. Topics discussed in this section: 2.4.1 일-변수 일차 방정식 (Single-Variable Linear Equations) 2.4.2 일차 연립 방정식 (Set of Linear Equations)

(Single-Variable Linear Equations) 2.4.1 일-변수 일차 방정식 (Single-Variable Linear Equations) 변수가 하나인 방정식, 즉 ax ≡ b (mod n ) 형태의 방정식을 어떻게 푸는 지 알아보자. 이러한 형식의 방정식은 해가 없거나 유한개의 해를 갖는다.

2.4.1 Continued Example 2.35 방정식 10 x ≡ 2(mod 15)를 계산하여라. Solution 먼저 gcd (10 and 15) = 5를 계산한다. 5가 2를 나누지 않기 때문에 해가 존재하지 않는다. Example 2.36 방정식 14 x ≡ 12 (mod 18)를 계산하여라. Solution

2.4.1 Continued 방정식 3x + 4 ≡ 6 (mod 13)를 계산하여라. Example 2.37 방정식 3x + 4 ≡ 6 (mod 13)를 계산하여라. Solution 먼저 방정식을 ax ≡ b (mod n) 형태로 바꾼다. 양변에 -4 (4의 덧셈에 대한 역원)를 더하면, 3x ≡ 2 (mod 13). 이 된다. gcd (3, 13) = 1이기 때문에, 방정식은 한 근을 가진다. 그 근은 x0 = (2 × 3−1) mod 13 = 18 mod 13 = 5이다. 이 답이 원래의 방정식에 적합한지 다음과 같이 검증할 수 있다. 3 × 5 + 4 ≡ 6 (mod 13).

2.4.2 Single-Variable Linear Equations 같은 모듈러에 대한 일차방정식 집합에서, 변수의 계수로 구성된 행렬의 역행렬이 존재하면(invertible) 그 방정식 집합을 풀 수 있다. Figure 2.27 일차 연립 방정식

2.4.2 Continued Example 2.38 다음의 일차 연립 방정식을 풀어라. : Solution 여기에서, x, y, z는 x1, x2, x3의 역할을 한다. 방정식의 집합으로 구성된 행렬은 역행렬이 존재한다. 그 행렬의 곱셈에 대한 역행렬을 찾아서 3, 4, 5로 구성된 열 행렬에 곱한다. 그 결과는 x ≡ 15 (mod 16), y ≡ 4 (mod 16), and z ≡ 14 (mod 16) 이다. 이 값들을 식에 대입하여 답인지 검증할 수 있다.