5장-Finite Fields and Polynomial Operation

Group (군)

군(G)은 어떤 이항 연산(예: +, × 등)에 대해 다음의 성질을 모두 만족하는 원소들의 집합이다:

공리	의미
A1. 닫힘성 (Closure)	a, b ∈ G → a • b ∈ G
A2. 결합법칙 (Associativity)	a • (b • c) = (a • b) • c
A3. 항등원 존재 (Identity)	a • e = a, e는 항등원
A4. 역원 존재 (Inverse)	∃ a⁻¹ ∈ G such that a • a⁻¹ = e
A5. 교환법칙 (Commutativity) → Abelian Group	a • b = b • a (모든 a, b에 대해)

🔹 용어 정리

• 군 (Group): A1~A4까지 만족하는 집합
• Abelian Group: A1~A5까지 모두 만족하는 교환군
  • 예시: 정수의 덧셈 (ℤ, +)

---

Cyclic Group (순환군)

정의: 군 G의 어떤 한 원소 a로부터 모든 원소를 생성할 수 있으면, 그 군을 **순환군(Cyclic Group)**이라고 한다.

🔹 수식 표현:

• G = { a⁰, a¹, a², ..., aⁿ } = ⟨a⟩
• 여기서 a는 generator (생성자) 역할을 한다.
• 모든 원소 g ∈ G는 g = aᵏ (단, k는 정수)

🔹 특징:

• 순환군의 연산은 지수 형태로 표현:
  • a³ = a • a • a
  • a⁰ = e (항등원), a⁻ⁿ = (a⁻¹)ⁿ
• 항상 Abelian Group (교환군) 이다.
  • 즉, a • b = b • a
• 순환군은 유한할 수도 있고, 무한할 수도 있음

🔹 용어 정리

• Generator: 순환군을 생성하는 원소
• ⟨a⟩: a로 생성된 순환군

---

Table 2.7; Modulo 19에서 거듭제곱

참고: 19 ≡ mod 19 field (체, modulo 19 system)에서 정수들의 거듭제곱 결과를 나열한 테이블

🔹 목적:

• 특정 수가 **순환군(Cyclic Group)**의 generator (생성자) 인지 확인할 수 있음
• 생성자는   Z₁₉* = {1, 2, ..., 18} 내의 모든 원소를 생성할 수 있어야 함

🔹 예시:

• 2¹ ≡ 2
• 2² ≡ 4
• 2³ ≡ 8
• 2⁴ ≡ 16 (mod 19)
• → ... 계속해서 2¹⁸까지 반복 없이 모든 값 생성 가능

즉, 2는 18개의 전부 생성 → generator

🔹 Generator가 될 수 있는 수:

• 예: 2, 3, 10, 13, 14, 15 등은 generator
• 이들은 Z₁₉* = {1, 2, ..., 18}에서 모든 값을 생성 가능
• 어떤 수 𝑎가 거듭제곱 후 mod n 한 값들이 Zₙ*의 모든 원소를 중복없이 생성하면, a는 generator다.

🔹 표현:

• Zₙ: 정수 전체를 n으로 나눈 나머지 집합 → {0, 1, ..., n-1}
• Zₙ*: Zₙ에서 0을 제외하고 n과 서로소인 수들의 집합 (곱셈이 가능한 원소들)

💡 정리:

용어	설명
Generator	어떤 수 a가 aᵏ ≡ x (mod n)의 결과로 Zₙ*의 모든 원소를 생성할 수 있으면 generator라고 함
Cyclic Group	하나의 generator로부터 모든 원소를 생성할 수 있는 군

---

Fields (체)

🔹 Field는 덧셈과 곱셈이라는 두 연산이 정의되고, 각 연산에 대해 다음 조건을 만족:

1. 덧셈에 대해 군 (A1~A5)
   1. A1 ~ A5: Closure, Associativity, Identity, Inverse, Commutativity
2. 곱셈에 대해 군 (단, 0 제외)
   1. 0을 제외한 모든 원소가 곱셈에 대해 군을 이룸
   2. 즉, 0을 제외한 모든 원소가 곱셈 역원을 가짐
      1. 어떤 수 a가 있을 때 a × a⁻¹ ≡ 1 (mod n) 을 만족하는 곱셈 역원 a⁻¹이 존재해야 한다는 뜻
3. 0의 곱셈역원은 없음 (zero divisor 없음)
   1. 0은 어떤 수와 곱해도 0이 되기 때문에 0 × x⁻¹ ≡ 1을 만족하는 수 x는 존재할 수 없다
4. 분배법칙: a(b + c) = ab + ac

🔹 정수 전체 ℤ는 Field가 아님

이유: 2에 대한 곱셈 역원(2⁻¹)은 ℤ에 존재하지 않음 → ℤ는 나눗셈이 안 되므로 Field 조건을 만족 못함

🔹 예시로 자주 등장하는 Field:

• 유리수 ℚ
• 실수 ℝ
• 복소수 ℂ
• (정수 mod p에서의 체): GF(p) (p는 소수일 때)

---

Finite Field GF(p)

• GF는 Galois Field의 약자
• GF(p): p가 소수일 때, {0, 1, ..., p-1} 원소로 구성된 유한체
• 연산은 모두 mod p로 수행됨

---

Types of Fields (Field의 유형)

1. Prime Field: GF(p)

• 소수 개수 p개의 원소로 구성
• 가장 기본적인 유한체

2. Extension Field: GF(pⁿ)

• pⁿ개의 원소를 가짐 (p: 소수, n: 양의 정수)
• GF(2ⁿ) = Binary Field → 디지털 회로, 암호 시스템에서 매우 중요

---

Modulo 8 vs Modulo 7 연산 테이블 (Table 5.1)

🔹 덧셈, 곱셈, 역원 비교 (mod 8 vs mod 7)

구분	Modulo 8	Modulo 7
덧셈	덧셈 결과를 8로 나눈 나머지	덧셈 결과를 7로 나눈 나머지
곱셈	곱한 후 8로 나눈 나머지	곱한 후 7로 나눈 나머지
덧셈 역원	w + (-w) ≡ 0 (mod n)	w + (-w) ≡ 0 (mod n)
곱셈 역원	존재하지 않는 경우 있음	항상 존재 (0 제외)
필드 조건 만족 여부	❌ 만족하지 않음	✅ GF(7): 필드임

 

🔹 GF(8)이 필드가 아닌 이유

• 8은 소수(prime) 아님 → GF(8)은 prime field 아님
• 일부 원소에 대해 곱셈 역원이 없음 → 필드 조건 위배

🔹 GF(7)이 필드가 되는 이유

• 7은 소수 → GF(7)은 정의상 유한체(Finite Field)
• {1,2,3,4,5,6} 모두에 대해 곱셈 역원 존재
• 덧셈/곱셈/역원 모두 만족 → 필드 조건 충족

📌 예시: 곱셈 역원 (mod 7)

w	1	2	3	4	5	6
w⁻¹	1	4	5	2	3	6

✔️ w × w⁻¹ ≡ 1 (mod 7)

🔹 GF(p)의 구성 요건

• 연산은 항상 mod p에서 수행
• 각 원소에 덧셈/곱셈 역원이 존재해야 하며 → p는 반드시 소수여야 함

---

GF(2ⁿ)의 동기 (Binary Field)

🔹 왜 GF(2ⁿ)를 쓰는가?

• 컴퓨터는 2진수 기반 시스템 → 8, 16, 32bit 단위 연산 사용
• GF(2⁸)이라면 → 0 ~ 255 표현 가능 (총 2⁸ = 256개 정수)

🔸 문제점: 그냥 Z₂₅₆으로는 안 됨

• Z₂₅₆은 256이 소수가 아니므로 역원이 없는 원소 존재 → 필드가 아님
• 반면 Z₂₅₁은 251이 소수라서 필드 구성 가능
  • BUT, 256개 중 251개만 사용 → 저장공간 낭비

---

GF(2ⁿ)에서의 다항식 연산 (Figure 5.5)

• GF(2ⁿ)에서는 숫자가 아닌 다항식(polynomial)으로 계산함
  • 덧셈: XOR
  • 곱셈: 다항식 곱셈
  • 나눗셈: 다항식 나눗셈 (mod 다항식)

📌 예시:

• (x³ + x² + 2) + (x² + x + 1) = x³ + 2x + 3
• 곱셈과 나눗셈도 유사하게 다항식 형태로 수행

---

다항식 나눗셈 (Polynomial Division)

• 다항식은 다음과 같이 표현 가능: f(x) = q(x)·g(x) + r(x)
  • 여기서 r(x)는 나머지, 즉 f(x) mod g(x)
• 나머지가 0이면 g(x)는 f(x)를 나눈다(divides):
  • 기호: g(x) | f(x)
  • g(x)는 인수(factor) 또는 약수(divisor)
• 기약 다항식 (Irreducible Polynomial): f(x)가 두 개의 낮은 차수의 다항식으로 나눠지지 않으면 기약임
• → 즉, 소수(prime polynomial)처럼 역할함

---

GF(2) 상의 다항식 연산 예시

• (a) 덧셈:
  • GF(2)에서는 XOR로 처리됨
  • 동일한 차수 항이 사라지는 방식
• (b) 뺄셈:
  • GF(2)에선 덧셈 = 뺄셈 (같이 XOR)
• (c) 곱셈:
  • 다항식을 곱해서 나온 항들을 더하고
  • 결과 항들의 계수를 GF(2)에서 정리 (XOR)
• (d) 나눗셈:
  • 일반적인 나눗셈과 유사한 방식
  • 몫과 나머지를 구함
  • 결과: f(x) mod g(x)

GF(2)에서는

• 1 + 1 ≡ 0 (mod 2)
• 1 - 1 ≡ 0 (mod 2)

즉, 덧셈과 뺄셈 모두 결과가 같음 → 같은 연산, XOR

a	b	a + b (mod 2)
0	0	0
0	1	1
1	0	1
1	1	0

---

다항식 최대공약수 (Polynomial GCD)

• 다항식 c(x)는 a(x), b(x)의 GCD (최대공약수)라면:
  1. c(x)는 a(x), b(x) 둘 다 나눔
  2. a(x), b(x)를 나눌 수 있는 다항식 중 가장 높은 차수여야 함
• 정의: gcd[a(x), b(x)] = 두 다항식을 나누는 가장 높은 차수의 다항식
• 유클리드 알고리즘도 GF(2) 다항식에 적용 가능

---

Table 5.4 Extended Euclid

🔸목적:

• 두 다항식 a(x), b(x)에 대해 최대공약수 GCD와 **계수 w(x)**를 구하는 확장 유클리드 알고리즘 설명.

🔸핵심 절차:

• 초기값:
  • a(x) = x⁸ + x⁴ + x³ + x + 1
  • b(x) = x⁷ + x + 1
• Iteration 1:
  • q₁(x) = x
  • r₁(x) = a(x) - q₁(x)·b(x) = x⁴ + x³ + x² + 1
  • v₁(x) = 1
  • w₁(x) = x
• Iteration 2:
  • q₂(x) = x³ + x² + 1
  • r₂(x) = x
  • v₂(x) = x³ + x² + 1
  • w₂(x) = x⁴ + x³ + x + 1
• Iteration 3:
  • q₃(x) = x³ + x² + x
  • r₃(x) = 1
  • v₃(x) = x⁶ + x² + x + 1
  • w₃(x) = x⁷
• Iteration 4:
  • q₄(x) = x
  • r₄(x) = 0 → 종료
  • GCD = r₃(x) = 1
  • w(x) = w₃(x) = x⁷

🔸결과:

• GCD(a(x), b(x)) = 1 (두 다항식은 서로소)
• w(x) = x⁷

---

Table 5.3 Polynomial Arithmetic Modulo (x³ + x + 1)

주제: GF(2) 위의 다항식 연산

• 다항식 덧셈은 GF(2) 위에서 이뤄져.
• GF(2)는 0과 1만 있고, 덧셈이 곧 XOR.
• 그래서 덧셈 결과는 항끼리 단순히 XOR하면 끝
• 곱셈: 차수 증가 → 곱셈의 결과를 모듈로로 줄여야 함

(a) 덧셈 연산-Addition

• 덧셈은 GF(2³)에서 XOR 연산과 동일함.
• 각 셀의 연산: a(x) + b(x) mod (x³ + x + 1)
• 다항식 기반의 XOR 테이블로 시각적으로 구성되어 있음.

(b) 곱셈 연산-Multiplication

• 다항식 곱셈 후, x³ + x + 1로 mod 연산하여 나머지를 구함.
• 이 mod 연산은 irreducible polynomial로 수행되며,
• 곱셈 결과를 GF(2³) 내에 다항식의 나머지 형태로 변환함.

---

Table 5.2 Arithmetic in GF(2³) (1~3 of 3)

주제: 위의 Table 5.3을 정수(비트)로 표현. GF(2³) 자체에서의 연산

(a) Addition

• 덧셈은 XOR 연산과 동일함; 위와 동일
• 각 셀은: a(x) + b(x) mod (x³ + x + 1)
• 결과는 다항식 XOR 기반 테이블로 구성

(b) Multiplication

• 다항식 곱셈 후 (x³ + x + 1)로 나눈 나머지를 취함; 위와 동일
• 즉, irreducible polynomial로 나눈 결과 → 곱셈 테이블

(c) Inverse

• w: 덧셈 역원
• w⁻¹: 곱셈 역원 (단, 0 제외)
• 덧셈과 곱셈에 대한 역원이 모두 존재함 → GF(2³) ≡ Field 조건 만족

---

Computational Considerations

GF(2ⁿ)에서의 다항식 연산을 효율적으로 구현하기 위한 계산적 고려사항

• GF(2)에서는 다항식의 계수들이 전부 0 또는 1이기 때문에, 다항식을 비트열 (bit string) 으로 표현할 수 있음
• GF(2)에서의 덧셈은 XOR과 동일하므로, 두 다항식을 더할 때는 단순히 비트 XOR만 수행하면 됨
• 곱셈은 숫자 곱셈처럼 자릿수를 밀면서 더하는 방식인데, 이게 비트 수준에선 Shift + XOR 연산으로 구현됨
• 곱셈 후 차수가 커지면 irreducible polynomial로 나눠야하는데, 이 과정도 최고차항을 치환 (substitute) 하고 XOR 하면서 정리함

연산	GF(2ⁿ)에서의 구현 방식
덧셈	비트 XOR
곱셈	Shift + XOR로 곱하고, 차수가 커지면 mod 연산 (irreducible polynomial로 나눔)
나눗셈	곱셈 역원을 구해 곱한 뒤, 차수가 커지면 mod 연산

---

Polynomial Arithmetic 예제

내용:

• 예: (x² + 1)(x² + x + 1) mod (x³ + x + 1)
• 다항식 곱셈 → mod 연산 순서대로 정리
• 결과: x² + x

---

Another Example (비트 기반 곱셈 과정)

🔸내용 요약: 비트 기반 다항식 곱셈 처리

• 다항식 f(x) = 01010111 과 g(x) = 10000001 을 비트 기반으로 곱셈 처리함
• 곱셈 시에는 shift (왼쪽으로 밀기) 후 XOR 연산으로 누적 계산
• 불필요한 carry는 irreducible polynomial로 mod 연산하여 정리

🔸연산 과정

1. g(x) 의 각 비트가 1인 위치마다 f(x)를 왼쪽으로 shift
2. shift된 f(x) 들을 XOR로 누적
3. 이 과정에서 생기는 불필요한 carry는 아래와 같이 제거

🔸Carry 제거

• carry가 발생하는 이유: 차수가 irreducible polynomial보다 클 경우
• 이때는 irreducible polynomial인 m(x) = x^8 + x^4 + x^3 + x + 1 로 mod 연산 수행
• 이 연산도 XOR로 처리됨 (최고차항 제거하는 방식)

🔸핵심

• 덧셈은 → XOR
• 곱셈/나눗셈(mod)은 → Shift + XOR
• 모든 연산이 비트 연산으로 구현 가능 → 하드웨어/암호 알고리즘에 적합

---

✅ 전체 요약

개념	핵심 내용
군 (Group)	하나의 연산에 대해 닫힘, 결합법칙, 항등원, 역원이 모두 존재
체 (Field)	두 연산(덧셈, 곱셈)이 모두 군의 성질을 만족하고, 곱셈에 대해 분배법칙도 성립
유한체 GF(p)	소수 p에 대해 정의된 체, 모든 연산은 mod p로 계산됨 (예: GF(7))
GF(2^n)	이진 연산 기반의 유한체, 연산은 비트 단위로 수행되며 컴퓨터/암호 시스템에서 많이 사용
순환군 (Cyclic Group)	하나의 생성자(generator)로부터 전체 원소를 생성할 수 있는 군
역원 (Multiplicative Inverse)	어떤 수 a에 대해 a × a⁻¹ ≡ 1 (mod n)을 만족하는 수 a⁻¹. 체에서는 0을 제외한 모든 원소가 역원을 가짐