[현대암호학] 제 2장 암호수학 (2)

(2021.09.29)
이번에 정리할 부분의 목차

2.2 모듈로 연산
 2.2.1 모듈로 연산자
 2.2.2 잉여류 Zn
 2.2.3 합동
 2.2.4 Zn에서의 연산
 2.2.5 역원
 2.2.6 덧셈표와 곱셈표
 2.2.7 덧셈과 곱셈에 대한 다른 집합
 2.2.8 다른 두 집합

(2.2.6, 2.2.7, 2.2.8은 가볍게 정리)

 

 

 

 

2.2 모듈로 연산(modular arithmetic)

 

2.2.1 모듈로 연산자

 

a mod n = r 

n은 모듈로(modulus), r은 나머지(residue)라고 함

모듈로 연산자는 mod라고 표기함

모듈로 연산자는 집합 Z에서 a를 선택하고, 양의 정수 모듈로 n을 선택한다.

연산자는 음이 아닌 나머지 r을 생성한다.

 

(+교수님이 해주신 추가적인 내용: 자연수 집합에서 덧셈연산은 닫혀있고, 뺄셈연산은 닫혀있지 않다.)

 

ex)

27 mod 5 = 2

36 mod 12 = 0

-18 mod 14 = 10  ---> (14)x(-2)+10=-18

-7 mod 10 = 3    ---> (10)x(-1)+3=-7

 

 

2.2.2 잉여류 Zn 

 

모듈로 연산(a mod n)의 결과값은 항상 0 ~ (n-1) 의 정수의 집합임

==> 모듈로 n의 최소 잉여집합(set of least residues modulo) 

==> Zn

 

Zn={0, 1, 2, ... , (n-1)}

 

 

 

2.2.3 합동

 

합동 연산자:  ≡

 

① 합동 연산자와 등식 연산자의 차이점

  - 등식 연산자는 Z의 원소를 Z의 원소로 대응함

  - 합동 연산자는 Z의 원소에서 Zn의 원소로 대응함

② 합동 연산자의 우변에 있는 (mod n)은 (Zn)을 나타냄

 

ex) 

2 ≡ 12 (mod 10)

13 ≡ 23 (mod 10)

-8 ≡ 12 (mod 10)

 

 

잉여류(residue classes)

[a]: 모듈로 n에 합동인 정수들의 집합

--> 잉여류에서 모듈로 n의 최소 잉여(least residue)의 집합을 집합 Zn이라고 함

 

ex)

n=5 일때

[0]={..., -15, -10, 0, 5, 10, 15, ...}   ---> 0

[1]={..., -14, -9, 1, 6, 11, 16, ...}   ---> 1

[2]={..., -13, -8, 2, 7, 12, 17, ...}   ---> 2

[3]={..., -12, -7, 3, 8, 13, 18, ...}   ---> 3

[4]={..., -11, -6, 4, 9, 14, 19, ...}   ---> 4

최소잉여 Z5={0, 1, 2, 3, 4}

 

 

 

2.2.4 Zn에서의 연산

 

(a+b) mod n = {(a mod n) + (b mod n)} mod n

(+ 대신 - 와 x도 가능)

----> +/-/x 를 하고 mod 연산을 할것이냐, mod 연산을 하고 +/-/x 를 할것이냐

----> 컴퓨터 내에서는 후자로 함

 

예제 2.19

예제 2.20

 

 

 

2.2.5 역원

 

덧셈에 대한 역원

 

곱셈에 대한 역원

 

Zn에 속한 정수 a가 곱셈에 대한 역원을 가질 필요충분조건은 gcd(n,a)≡1(mod n) 이다.

확장 유클리드 알고리즘을 이용하여 n과 b가 주어지고, gcd(n.b)=1 일때
Zn에서 b의 곱셈에 대한 역원을 구할 수 있음
==> b의 곱셈에 대한 역원은 t를 Zn으로 대응시킨 값임.

 

 

확장 유클리드 알고리즘을 이용한 곱셈에 대한 역원 계산

 

 

 

덧셈에 대한 역원이 필요할 때는 Zn을 사용
곱셈에 대한 역원이 필요할 때는 Zn*을 사용

==> Zn의 원소는 0을 제외하고는 모두 덧셈에 대한 역원을 가짐
==> Zn*의 원소는 0을 제외하고는 모두 곱셈과 덧셈에 대한 역원을 가짐

Zp는 Zn과 같은데 p가 소수라는 특징이 있음
Zp*도 마찬가지임