암호수학 시험 정리

1. 기약 잉여계, 완전 잉여계, 오일러 함수 정의

기약 잉여계

• $\{a_1, a_2, \dots , a_m \}$가 법 $m$에 대한 완전 잉여계일 때, 여기서 $m$과 서로소인 원소만 모은 집합을 법 $m$에 대한 기약잉여계라 한다.

 

완전 잉여계

• $\{a_1, a_2, \dots , a_m \}$에서 $a \equiv a_i \pmod{m}$인 $a_i$가 유일하게 있을 때, $\{a_1, a_2, \dots , a_m \}$ 를 완전잉여계라고 한다.

 

오일러 정의

기약 잉여계 개념은 정수론에서 오일러의 정의를 증명하는 데 사용된다. 정수론에서 유용하게 쓰이는 정리로, 합동식과 관련이 있다. 페르마의 소정리를 일반화한 것이다.

 

• $a$와 $n$이 서로소인 양의 정수일 때, $a^{\varphi(n)} \equiv 1(mod\ n)$이다.
  • 여기서 $\varphi(n)$은 $1$부터 $n$까지의 정수 중 $n$과 서로소인 정수의 개수이다. 오일러 피 함수라고도 불린다.

 

• 양의 정수 $m$에 대하여, $m$ 이하의 자연수 중에서 $m$과 서로소인 정수의 개수를 $\varphi (m)$으로 나타내고 함수 $\varphi : Z→N$ 를 오일러의 $\varphi$ 함수라고 한다.
  
  • $\varphi$ = varphi

 

2. 확장 유클리드 알고리즘으로 곱셈의 역원 구하기

정의

유클리드 호제법이란 두 정수 사이에 최대공약수(GCD)를 보다 효과적으로 구하는 것으로, 인류 최초의 알고리즘이라 한다. 

 

두 개 자연수 $A, B$가 있고 $A\ \%\ B = r$이면 다음과 같다. (단, $A > B$)

 

$GCD(A,B) = GCD(B,r)$

 

이 때, $A\ \%\ B = r$에 의해 다음과 같은 식이 기본적으로 유도된다.

 

$A = Bq + r$

 

 

증명

두 자연수 $A,B (A > B)$의 최대공약수를 $G$라 하자. $G$는 공약수이므로 두 서로소 $a, b$에 대해 다음 식이 성립한다.

 

$A = aG, B = bG$

 

위의 식을 사용하여 $A = Bq + r$에 대입하면 다음과 같다.

 

$aG = bGq + r$

 

$r = aG - bGq$

 

$ r = (a - bq)G$

 

$A = aG, B = bG$에서 $a, b$가 서로소라면 $G$가 최대공약수이기 때문에 $b, a - bq$가 서로소임을 증명하면 된다.

 

이를 증명하기 위해서는 가정에 모순을 확인하는 귀류법을 사용하여 해결할 수 있다.

 

$b$와 $a - bq$가 서로소가 아니라면 두 수는 공약수 $k$를 가지기 때문에 다음과 같이 나타낼 수 있다.

 

$a - bq = mk$

$b = nk$

 

위 식의 항을 옮기고 대입하여 정리하는 과정은 다음과 같다.

 

$a = mk + bq$

 

$a = mk + nkq$

 

$a = (m+nq)k$

 

따라서 다음과 같은 식을 확인할 수 있다.

$a = (m+nq)k$

$b = nk$

 

하지만 $a$와 $b$는 서로소이나 공약수 $k$를 가지므로 거짓 명제이다.

 

따라서 $a-bq$와 $b$는 서로소이다.

 

 

3. 군환체 조건 정의 및 다항식체 모듈러 계산

군, 환, 체의 경우 대수학에서 사용되는 개념으로 기본적이면서 가장 중요한 개념으로 여겨진다.

 

군 환 체 정의

군

 

공집합이 아닌 집합 G 위에 다음 세 조건을 만족하는 이상연산 $\circ$가 정의될 때 $<G, \circ>$를 군이라 한다.

 

군의 공리

• 결합법칙 : $G$의 임의의 원소 $a, b, c$에 대해 다음이 성립한다.
  • $(a \circ b)\ \circ \ c\ =\ a\ \circ \ (b \circ c)$

 

• 항등원 : $G$의 모든 원소 $a$에 대해 다음이 성립하는 $e \in G$가 존재해야하며, 이 때 $e$를 $G$의 단위원 또는 항등원이라한다.
  • $a \circ e\ =\ e\circ a = a$

 

• 역원 : $G$의 각 원소 $a$에 대해 다음이 성립하는 $a^{-1}$이 $G$에 존재해야 하며, 이 때 $a^{-1}$를 $a$의 역원이라한다.
  
  • $a \circ a^{-1} = a^{-1} \circ a = e$

 

• 닫힘 : 어떤 집합의 임의의 두 원소(순서쌍)간에 연산이 행해질 때, 그 결과 역시 그 집합의 원소가 되는 것을 의미한다.
  • $a \circ b$ 연산의 결과도 집합 $G$에 속하며 순서쌍 $(a,b)$들의 곱(카테시안 곱) 연산에 대해 닫혀있음

 

군은 결합법칙, 항등원, 역원, 닫힘의 네 가지 특성을 가지고 있어야 한다.

 

군의 종류

• 가환군 or 아벨군
  • 군의 네 가지 특성에 추가적으로 교환법칙까지 성립할 경우 이를 아벨군(abelian group) 또는 가환군(commutative group)이라 한다.

 

• 순환군(Cyclic Group)
  
  • 한 원소로 군의 모든 원소를 표시할 수 있는 군을 의미하며, 이 때 해당 원소를 생성원(generator)라 한다.

 

• 덧셈군(Additive Group)
  
  • 군의 이항 연산이 덧셈 연산인 군

 

• 곱셉군(Muliplicative Group)
  
  • 군의 이항 연산이 곱셈 연산인 군

 

• 부분군(Subgroup)
  • 군 $G$의 부분집합으로 군 $G$와 같은 연산 구조를 가지는 군

 

군의 표기

• $(G, \circ)$ 또는 $<G, \circ>$ 또는 ${G, \circ}$
  • $G$: 군의 원소 집합
  • $\circ$ : 군의 연산
• 군의 차수/위수(order): $|G|$ 또는 $O(g)$ 또는 $G_n$ 또는 $ord(G)$로 나타낼 수 있다.

 

 

환

 

어떤집합 R 및 그 집합 위에 2개의 이항연산$(+, \circ)$이 정의되는 대수 구조를 의미하며 다음과 같이 표기한다.

• $(R, +, \circ)$ 또는 $< R, +, \circ>$ 또는 $환 R$

 

환의 공리

• 덧셈 연산에 대해 : $(R, +)$는 가환군
  • 닫혀 있음
  • 항등원(`0`)이 존재 $\rightarrow a + 0 = 0 + a = a$
• 각 성분에 대해 역원이 존재함$\rightarrow a + (-a) = (-a) + a = 0$

 

• 모든 성분에 대해 교환법칙이 성립 $\rightarrow a + b = b + a$

 

• 모든 성분에 대해 결합법칙이 성립 $\rightarrow (a + b) + c = a + (b + c)$

 

• 곱셈(\circ) 연산에 대해 : $(R, \circ)$
  • 닫혀 있음
  • 모든 성분에 대해 결합법칙이 성립 $\rightarrow (a\circ b)\circ c = a\circ (b\circ c)$
• 덧셈 및 곱셉 연산에 대해 : $(R, +, \circ)$
  • 모든 성분에 대해 분배법칙이 성립 $\rightarrow a\circ (b + c) = a\circ b + a\circ c, (a + b)\circ c = a\circ c + b\circ c$

 

추가적인 조건에 따른 환의 종류

 

• 가환환
  • 추가적으로 곱셈(\circ)에 대해서 가환이 되는 환 : $a \circ b = b \circ a)$

 

• 단위원을 갖는 환(Ring with Unity)
  • 추가적으로 곱셈 항등원 즉, 단위원을 갖는 환 : $1 \circ a = a \circ 1 = a$

 

• 나눗셈환
  • 단위원 1을 갖는 환으로써, 곱셈 역원이 존재하는 환 : 각 원소 $a \in R, a \neq 0$에 대해, $a \circ a^{-1} = a^{-1}\circ a = 1$

 

• 정역(Integraldomain)
  • 단위원 1을 갖는 가환환으로써, 추가적으로 다음 조건을 만족
    • $a \neq 0, b \neq 0$이면 $a \circ b \neq 0$을 만족함 또는
    • $a \circ b = 0$이면, $a = 0$ 또는 $b = 0$ $(a,b \in R)$

 

체

• 코드(부호) 등을 기술하는데 사용될 수 있는 수학적 대수 구조
  • 예) 실수 $R$, 유리수 $Q$, 복소수 $C$와 같은 수 체계에 대한 추상화
• 특정한 성질을 만족하는 2개의 연산이 정의되는 가환환
  • 그 요소들이 집합을 이루면서, 덧셈과 곱셈 연산 두 쌍을 사용할 수 있는 구조(2개 산술연산자)

 

체의 공리

• 덧셈 연산에 대해 : $<F, +>$
  • 집합 내 원소의 연산 결과가 다시 그집합 내에 있게된다. $\rightarrow$ 닫혀있음
  • 항등원 (`0`)이 존재 : $a + 0 = a = 0 + a$
  • 모든 성분에 대해 덧셈 역원이 존재 : $a + (-a) = 0 = (-a) + a$
  • 모든 성분에 대해 결합법칙이 성립 : $(a + b) + c = a + (b + c)$
  • 모든 성분에 대해 교환법칙이 성립 : $a + b = b +a$
• 곱셈 연산에 대해 : $<F, \circ>$
  • 모든 성분에 대해 분배법칙이 성립 : $a (b +c) = a b + a c$

위 체의 공리에서 덧셈 공리들 만을 만족할 경우는 아벨군 또는 가환군이며, 곱셈의 역원 존재 만을 제외한 나머지 공리들을 만족하는 경우는 환이다.

 

체의 공리가 성립하는 예제

• 실수체 : 실수 전체의 집합
• 복소수체 : 복소수 전체의 집합
• 유리수체 : 유리수 전체의 집합

유한개의 원소를 갖는 체 $\rightarrow$ 유한체(갈로이스체)

 

 

4. 중국인 나머지 정리

개요

중국인의 나머지 정리의 경우 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이며 그 기원은 다음과 같다.

 

중국의 5세기 문헌인 『손자산경(孫子算經)』에는 다음과 같은 문제가 있다고 한다.

 

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?

 

 

정의

$gcd(n,m) = 1$면 $\begin {cases} x \equiv b\ (mod\ n) \\ x \equiv c\ (mod\ m) \end {cases}$는 $1 \leq x \leq nm$에서 단 하나의 해를 갖는다.

 

증명

 

$x \equiv b\ (mod\ n)$    (1)

$x \equiv c\ (mod\ m)$    (2)

 

$x \equiv b\ (mod\ n)$이므로 $x = ny + b$를 만족하는 $y \in Z$가 존재할 것이고, 이를 (2)에 대입하면 다음과 같다.

 

$ny \equiv c -b\ (mod\ m)$

 

위 정의에 의해 위 합동식은 $1 \leq y \leq m$에서 유일한 해 $y_0$를 갖고, 따라서 $x = ny_0 + b$는 $1 \leq x \leq nm$에서 유일한 해 $x_0$를 가진다. 따라서 다음과 같다.

 

$x_0 = ny_0 + b$

 

여기서 $x_0$는 (1)의 해다. 이제 $ny_0 \equiv c -b\ (mod\ m)$에 $ny_0 = x_0 - b$를 대입하면 다음과 같다.

 

$x_0 \equiv c\ (mod\ m)$

 

$x_0$은 (2)의 해가 된다. 증명 끝.

 

5. 가우스 소거법 / 가우스 조단 소거법

가우스 소거법을 이용하여 연립 방정식의 해를 구하는 과정이며, 아래에서 $R_2$는 2열을 의미한다.