보안 예비 지식 (Preliminaries)

1. 나눗셈 정리 (Division Theorem)

• 정의
  임의의 정수 a, 양의 정수 n에 대해,
  유일한 정수 q,r이 존재하여 다음을 만족: a=nq+r, 0≤r<n
  • q: 몫(quotient)
  • r: 나머지(remainder)
• 예시
  • a=39,  n=7 ⇒ q=5,  r=4 a = 39, 39 = 7 × 5 + 4.

2. 자연수의 최소원리 (Well-Ordering Principle)

• 정의
  자연수 집합 N의 임의의 공집합이 아닌 부분집합 S는 최소 원소 m을 가진다.
  • ∀S⊆N,  S≠∅ ⇒ ∃m∈S  s.t. ∀s ∈ S,  m≤s
• 활용
  나눗셈 정리와 같은 기본 정리를 증명하는 데 사용.

3. 합동 (Congruence)

• 정의
  m≥1인 정수에 대해, 두 정수 a, b가 mod m에서 합동이면:
  • a ≡ b (mod m) ⇔ m ∣ (a−b)
  • 즉, a − b = km인 정수 k가 존재.
• 성질 (동치 관계 성질)
  • 반사성 (Reflexivity): a ≡ a(mod m)
  • 대칭성 (Symmetry): a ≡ b(mod m) ⇒ b ≡ a(mod m)
  • 추이성 (Transitivity): a ≡ b, b ≡ c ⇒ a ≡ c (mod m)
• 예시
  • 39 ≡ 25 ≡ 4 (mod7)
• 역원(Inverse) 예시
  • 모듈러 연산에서 나눗셈은 역원으로 정의됨.
    • a/b ≡ a⋅b−1 (mod m)
  • b⋅c≡1(mod m)을 만족하는 c가 b의 역원.
  • 예: p=5, 3−1≡2 (mod 5)
    • 3⋅2≡1(mod5)

4. 합동류 (Congruence Classes)

• 정의
  합동 관계(≡)는 동치 관계이므로, 집합을 동치류로 나눌 수 있음.
  이를 합동류(congruence class)라 부름.
• 예시 (m = 4)
  • [0] = {…,−8,−4,0,4,8,…}
  • [1] = {…,−7,−3,1,5,9,…}
  • [2] = {…,−6,−2,2,6,10,…}
  • [3] = {…,−5,−1,3,7,11,…}

5. 잔여계 (Residue System)

• 정의
  각 합동류에는 대표 원소가 존재 → 0 ≤ a < m 범위의 원소 선택.
  이 대표 원소들을 모은 집합을 잔여계(residue system)라 함.
  • 예시 (m=4)
    • Z4={0,1,2,3}
  • 성질
    합동류끼리 연산 정의 가능:
    • (a1 ≡ b1), (a2 ≡ b2) ⇒ a1 + a2 ≡ b1 + b2 & a1a2 ≡ b1b2
    • ​따라서, Zm에서 덧셈/곱셈이 잘 정의됨

6. 환 (Ring)

• 정의
  집합 R에 두 연산 +, ⋅이 정의되어 세 가지 공리를 만족하면 환이라 부름.

1. 덧셈에 대해 아벨 군(an abelian group under addition)
   • 결합법칙: (a+b)+c = a+(b+c)
   • 교환법칙: a + b = b + a 
   • 항등원: a + 0 = a 
   • 역원: a + (−a) = 0
2. 곱셈에 대해 모노이드(a monoid under multiplication)
   • 결합법칙: (ab)c = a(bc)
   • 항등원: a⋅1 = a
3. 분배법칙 성립
   • a(b+c)=ab + ac
   • (b+c)a=ba + ca

7. 체 (Field)

• 정의
  환 R이 추가 조건을 만족하면 체(Field)가 됨:
• R∖{0}이 곱셈에 대해 아벨 군을 이룸.
• 즉, 덧셈, 뺄셈, 곱셈, 나눗셈(0 제외) 모두 정의 가능.

• 예시
  • 유리수 집합 Q
  • 실수 집합 R
  • 복소수 집합 C소수 p에 대한 모듈러 체: Zp

✅ 정리

 

예비 지식 부분은 암호학과 Private AI를 이해하기 위한 수학적 기초를 다루고 있습니다

​

1. 정수의 분할(몫과 나머지)
2. 자연수의 최소 원리
3. 합동 관계와 그 성질
4. 합동류 및 잔여계
5. 이 구조들을 기반으로 한 환(Ring), 체(Field) 개념