[TIL]230315 - 컴퓨터시스템보안 2주차: 기초 정수론(2) 모듈러 연산

모듈러 연산

• 나머지 연산의 두 결과 값 중 나머지 r(>=0)만 출력하는 연산

  나눗셈 관계식: a= qn + r
  q: 몫
  n: 제수
  a: 피제수
  r: 나머지

a mod n = r

• 모듈러 연산의 예
  • 27 mod 5 = 2
  • 36 mod 12 = 0
  • -18 mod 14 = 10
  • -7 mod 10 = 3

---

최소 잉여 집합

• 모듈러 n을 이용하는 모듈러 연산의 결과는 0 ~ n-1 사이의 값을 가짐
• 이때, 정수 n에 대한 모듈러 연산 결과는 하나의 집합을 생성하는데, 이 집합을 모듈러 n의 최소 잉여 집합 Zn이라 함

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

• 최소 잉여 집합의 예
  • Z2 = {0, 1}
  • Z6 = {0, 1, 2, 3, 4, 5}
  • Z8 = {0, ... , 7}
  • Z10 = {0, ... , 9}

---

모듈러 합동

• 모듈러 연산 "mod 10"을 2, 12, 22, 52에 대해 수행하면,
  • 2 mod 10 = 2
  • 12 mod 10 = 2
  • 22 mod 10 = 2
  • 52 mod 10 = 2
• 즉 10에 대해서 모듈러 연산을 수행한 결과, 모두 같은 결과 값(r = 2)를 가짐
• mod 10에 대해 합동

합동 연산자 ≡

• a ≡ b (mod x): 두 정수 a와 b는 mod x에 대해 서로 합동임
• 즉, a와 b는 x로 나눴을 때, 서로 같은 나머지를 가짐

• mod 10에 대한 합동 연산자 사용 예
  • 2 ≡ 12 (mod 10)
    • mod 10에 대해 2와 12는 서로 합동입 (r = 2)
  • 13 ≡ 23 (mod 10)
    • mod 10에 대해 13과 23은 서로 합동임 (r = 2)
  • 34 ≡ 14 (mod 10)
    • mod 10에 대해 34와 24는 서로 합동임 (r = 4)

---

잉여류

• n으로 합동인 정수의 집합
• [a] 또는 [a]n으로 표기
  • [a]n은 n으로 나누었을 때, 나머지가 a가 되는 모든 정수들의 집합

• n = 5일 때 잉여류

  • [0] = {... 0, 5, 10, ...}

  • [1] = {... 1, 6, 11, ...}

  • [2] = {... 2, 7, 12, ...}

  • [3] = {... 3, 8, 13, ...}

  • [4] = {... 4, 9, 14, ...}