MODULAR 개념과 암호

시저 암호(Caesar cipher)

줄리어스 시저(유리우스 카이사르)가 사용하였다는 암호

평문으로 사용되는 알파벳을 숫자로 변환 후 일정한 문자 수 만큼(Key) 평행이동 함으로써 암호화

덧셈 암호

평문과 암호문을 구성하는 문자를 Z(26)의 원소로 표현

Z (25 + 3) mod 26 == 28 mod 26. == 2 -> C

약수와 배수

• Z : 정수들의 집합
• b|a
  • b는 a를 나눈다.
• b†a
  • b는 a를 나누지 못한다.
• 소수(prime) p
  • 1, p 만을 약수로 가지는 양의 정수
• 합성수 : 1과 소수가 아닌 양의 정수
  • 예) 18 = { 1, 2, 3, 6, 9, 18}

모듈러(Modular) 연산

모듈러 연산 -> 나머지 값을 구하는 연산

• 어떤 양의 정수 n과 어떤 정수 b가 주어졌을 때,
  
  • 만약 a를 b로 나눈다면
  • 다음과 같은 관계인 몫 q와 나머지 r을 얻을 수 있음
    • a = b*q + r 단, 0 <= r < b
    • a mod b = r (mod b)

최대공약수(GCD) 계산 : Euclid 호제법

유클리드 호제법 or 유클리드 알고리즘

2개의 자연수 또는 정식(整式: 정수)의 최대공약수를 구하는 알고리즘

예)

r1 = q * r2 + r

합동식

a ≡ r (mod b) 또는 a mod b ≡ r

완전잉여계, 기약잉여계

완전잉여계

modular 뜻은 '법'

법 m에 관한 완전잉여계

->임의의 정수 m로 나눈 “나머지” 들을 원소로 갖는 집합

Zm = { a ∈ Z | Z mod m ≡ a}

기약잉여계

법 m에 관한 기약잉여계

-> 법 m에 관한 완전잉여계의 원소 중에 m과 서로소인 원소들의 집합

완전잉여계 Zm = {0,1,2,3,…, m-1}

군(Group) : 하나의 사칙연산자 대해..

군(Group) : 네 개의 성질(혹은 공리)을 만족하는 이항 연산 “•”이 정의된 원소들의 집합

G = < Zm , +> 또는 G = < Z*m , x> 하지만 G =(x) < Zm , x>

환(Ring) : 두개의 연산자에 대해..

R = <{…},•,☐> 은 두 개의 연산을 가지는 대수적 구조

• 덧셈과 곱셈의 두개의 연산이 정의된 집합
• (ex) R = < Zm, +, ×>

체(Field) : 두개의 연산자에 대해..

F = <{…},•,☐> 은 두 개의 연산에 대해

• 첫번째 연산 •에 대해서는 가환군(Group)이 성립
• 두번째 연산 ☐에 대해서는 가환환(Ring)이면서, 첫번째 연산에서의 항등원에 대해서는 역원이 존재하지 않아도 되는 경우
  
  • (ex) F = <Zp, +, *>

아벨군(Abelian Group)

컴퓨터 이진수 체계 - Galois Field : GF

GF(23) = {0,1,2,3,4,5,6,7} <- Z8
         = {000, 001,010,011,100,101,110,111}
기약다항식 m(p) = x3 + x1 + 1을 이용하여 mod 연산을 수행

곱셈에 대한 Modular 8 적용                                                  곱셈에 대한 Mod (기약다항식) 적용

확장 유클리드 알고리즘

두 정수 a 와 b가 주어졌을 때, 다음 식을 만족하는 다른 두 정수 계산해야 할 수 있을까?

확장 유클리드 알고리즘을 변경/이용하여 해결 가능하다.