유한체, 갈루아 체

나머지 연산(Modular Arithmetic)

양수의 모듈러 연산

• 2 mod 7 = 2

• (2 + 7) mod 7 = 2

• (2 + 7n) mod 7 = 2

*음수의 모듈러 연산
(2 + (-2) x 7) mod 7 = -12 mod 7
-12 = 7 x (-1) -5
-5 + 7 = 2로 나머지는 2이다.

a mod n = b mod n일 때 a≡b mod n이다. '합동'이라고 표현한다.
정수에 대한 모듈러 연산의 결과 집합은 ${Z}_n=\left\{0,1,...,\left(n-1\right)\right\}$이다.

군(Group)

군은 아래와 같은 4가지 조건을 만족하는 집합을 뜻한다.

• 닫혀있다(Closure)

• 결합법칙(Associative)의 성립

• 항등원 존재(Identity element)

• 역원 존재(Inverses element)

+교환 법칙(Commutative) -> 아벨군(Abelian Group)

모듈러 연산 집합에 대한 덧셈군(Additive Group)

${Z}_n=\left\{0,1,...,\left(n-1\right)\right\}$이고, n = 11일 때
${Z}_{11}\ =\ \left\{0,1,2,3,4,5,6,7,8,9,10\right\}$이다.

• Z11에서 랜덤하게 두 개를 뽑아 더한 뒤 mod11해도 Z11에 속하므로 닫혀있다.

• a mod 11 + b mod 11 = (a+b) mod 11이 성립하므로 결합법칙 성립

• (a + 0) mod 11 = a 이므로 항등원 0이 Zn 안에 존재

• (a +(11-a)) mod 11 =0 이므로 mod11에 대하여 a의 역원 11-a가 Zn안에 존재

1번 문제: Z11에 대하여 x+7=3 일 때 x는?

(x+7) mod 11 = 3 mod 11
양변에 7을 빼면 x mod 11 = -4 mod 11
-4 mod 11은 7이므로 x mod 11 = 7을 만족하는 x는 7이다.

2번 문제: Z11에 대하여 2-x=8일 때 x는?

(2-x) mod 11 = 8 mod 11
식을 정리하면 x mod 11 = -6 mod 11
-6 mod 11 = 5이므로 x mod 11 = 5을 만족하는 x는 5이다.

모듈러 연산 집합에 대한 곱셈군(Additive Group)

${Z}_n=\left\{0,1,...,\left(n-1\right)\right\}$이고, n = 11일 때
${Z}_{11}\ =\ \left\{0,1,2,3,4,5,6,7,8,9,10\right\}$이다.

• 랜덤하게 두 개를 골라 곱한 뒤 mod 11연산을 하면 집합에 속하므로 닫혀있다.

• (a mod 11) (b mod 11) = ab mod 11 성립

• (a*1) mod 11 = a 이므로 항등원 1이 존재

• (a*a^-1) mod 11 = 1 이므로 역원 a^-1

모든 원소가 곱셈에 대한 역원을 가지고 있다.

문제: Z11에 대하여 2/x = 8 일 때 x는?

2/x mod 11 = 8 mod 11
양변에 x를 곱하면 2 mod 11 = 8x mod 11
양변에 8의 역원 8^(-1)을 곱하면 x mod 11 = 2 * 8^(-1) mod 11
Z11에서 8의 역원은 7이다.(8 * 7 mod 11 = 1)
즉, x mod 11 = 2 * 7 mod 11 = 3을 만족하는 x는 3이다.

*모듈러 연산 군에서 원소의 역원을 찾는 방법

1. 원소를 순차적으로 탐색하기(군이 작은 경우)
2. 페르마의 소정리
3. Extended Euclidean Algorithm

유한체, 갈루아 체(Galois field)

갈루아 체로도 불리며, 유한개 원소 만을 갖고, 그 안에서 대수적 구조를 형성하는 체.
유한체 집합 내 원소의 연산(덧셈,곱셈 등) 결과가, 다시 그 집합 내에 있게됨 (닫힘성)

위수: 체의 원소의 개수

$GF(p^n)$: q(위수) = $p^n$개인 유한체. (p:소수이고, n은 자연수)
유한체의 위수는 항상 소수 또는 소수의 거듭제곱 형태만이 가능하다.

Ex)
GF(2), GF(4), GF(8) -> 유한체 존재함.
GF(6), GF(10), GF(12) -> 유한체 존재하지 않음.

q(위수)가 소수일 때 GF(q) = {0,1..(q-1)}이다.

GF(2) = {0,1}
GF(3) = {0,1,2}
GF(5) = {0,1,2,3,4}
-> mod q

1번 문제: GF(5)에서 $1/4 -2/3$은 얼마일까?
$1/4 -2/3 = 1\times4^{-1} +(-2\times3^{-1})$이다.
mod 5에서 4의 역원은 4이다.( $4\times4$ mod 5 = 1, 4 mod 5 = 4)
mod 5에서 -2는 3이다.
mod 5에서 3의 역원은 2이다.
즉 $1\times4 + 2 \times3$ = 4 + 6이다. 6 mod 5 = 1이므로 4 + 1 = 5이다.
5 mod 5 = 0이므로 결과적으로
GF(5)에서 $1/4 -2/3$은 0이다.

2번 문제: GF(13)에서 $2x-y = 5$, $3x+2y=6$을 풀면?

$4x-2y = 10$
$3x+2y = 6$
$7x = 16$
$x = 16\times7^{-1} = 16 \times 2$
$x = 32 mod 13 = 6$이다.
$12-y = 5, y =7$이다.