[암후] <암호학과 네트워크 보안> 책정리 2, 3주차

2.2 모듈로 연산

- 나눗셈 관계식 a = q x n + r

=> a를 n으로 나눌 때 r값이 무엇인지

 

- 모듈로 연산자

=> n은 모듈로 r은 나머지

ex) a mod n = r, -18 mod 14 = (-4 + 14)10(양수만 가능)

 

- 잉여류 Zn

: 모듈로 n의 최소 잉여 집합: 모듈로 연산 결과는 항상 0 ~ n-1 정수

 

- 합동

: 연산자 ≡

ex. 13 ≡ 23(mod 10), -8 ≡ 2(mod 5)

① 합동 연산자: 다-대-일 / 등식 연산자: 일-대-일(one to one)

② 합동 연산자 우변의 mod는 공역을 의미

 

⑴ 잉여류

: [a], [a]n은 모듈로 n으로 합동인 정소의 집합

ex. n=5일 경우 5개의 집합 존재 [0] = {..-10, -5, 0, 5, 10..} [1] = {..-4, 1, 6..}

- 각각의 집합에는 최소 잉여라고 불리는 한 원소가 존재, [0]에서 0, [1]에서 1

 

- Zn에서의 연산

: 덧셈, 뺄셈, 곱셈 가능

ex. Z_20의 7과 11을 곱하시오

(7 x 11) mod 20 -> 77 mod 20 = 17

① 성질

- (a + b)mod n = [(a mod n) + (b mod n)] mod n(뺄셈 곱셈도 같음)

+ 정수를 3으로 나눈 나머지는 그 정수의 각 자리수의 합을 나눈 나머지와 같음

ex. 6371은 6+3+7+1 = 17, 17 mod 3 = 2

 

- 역원

① a + b ≡ 0 mod n

② 어떤 정수와 그 정수의 덧셈에 대한 역원의 합은 모듈러 n에 대해 0과 합동

ex. Zn에서 모든 덧셈에 대한 역원 쌍 (0,0), (1,9), (2,8) ... (5,5)

③ a x b ≡ 1 mod n

④ 곱셈에 대한 역원이 있을 수도 없을 수도 있음

ex. 곱셈의 역원 필요충분조건 gcd(n, a) = 1 a와 n은 서로소

ex. Z_10에서 곱셈에 대한 모든 역원 (1,1), (3,7), (9, 9)

1 mod 10 = 1, 21 mod 10 = 1, 81 mod 10 = 1

 

- 덧셈표와 곱셈표

: Zn 덧셈표, Zn* 곱셈표

 

2.3 행렬

row = 행, column = 열, det(A) 로 행렬식 표기

① 덧셈, 뺄셈: 각 원소끼리 더한다(뺀다).

② 곱셈: 1행과 1열의 원소를 각각 곱해서 더한 것이 하나의 원소

* Mij, Nij에서 M의 i와 N의j의 (원소)최댓값이 같아야 함

ex. 3 x 3 행렬 계산식

5 2 1

det[ 3 0 –4 ] = -1^(1+1) x 5 x det[ 0 –4 ] + -1^(1+2) x 2 x det[ 3 –4 ] + ...

      2 1 6                                 1  6                                 2 6

= 1 x 5 x 4 + -1 x 2 x 24 + 1 x 1 x 3 = -25

 

- 역행렬

: 행렬은 덧셈, 곱셈에 대한 역행렬을 모두 가짐

* 곱셈은 정방 행렬만 가능

 

① 합동

A ≡ B(mod n), 모든 i,j에 대해 aij ≡ bij(mod n) 이다.

 

2.4 선형 합동

① 일변수 선형 방정식

: ax ≡ b(mod n) 방정식이 해가 없거나 유한개의 해를 갖음

gcd(a, n) = d 라고 가정 d !| b이면 해가 존재 x, d | b 이면 d개의 해 존재

 

d | b일 경우 해 구하는 법

⑴ 모듈로 포함하여 양변을 d로 나눔

⑵ 특수해 x0을 구하기 위해 약분한 방정식의 양변에 a의 곱셈에 대한 역원 곱하기

⑶ 일반 해는 k = 0, 1,...,(d-1)에 대해 x = x0 + k(n/d)

 

ex) 10x ≡ 2(mod 15) 의 해

=> gcd(10, 15) = 5 이고 5과 2를 나누지 않기에 해가 존재하지 않는다

ex) 14x ≡ 12(mod 18)의 해

=> 14x ≡ 12(mod 18) -> 7x ≡ 6(mod 9) -> x ≡ 6(7^(-1))(mod 9)

x0 = (6 x7^(-1)) mod 9 = (6 x 4)(mod 9) = 6

x1 = x0 +1 (18 / 2) = 15

따라서, 해는 6과 15이며, 검산 결과가 맞기 때문에 합동 관계식을 만족한다(x에 대입)