정수론의 기본 바탕인 나눗셈 관계식, 자주 쓰일 유클리드 알고리즘에 대해 다뤄보고자 한다.
나눗셈 관계식이란 피제수(dividend), 제수(divisor), 몫(quotient)으로 되어있는 관계식이다.
그림으로 이러한 형태로 나오며, 이는 차 후 합동식에서 나머지와 최대공약수를 구하기 위해 자주 쓰인다.
이 식을 가로형태로 만들면 a = q x b + r 이고 0 ≤ r < b의 조건을 성립해야한다.
암호학에서 사용하는 나눗셈 관계식은 2개의 제약이 존재한다.
- 재수는 양의 정수 (b > 0)이다.
- 나머지는 음이 아닌 정수(r ≥ 0) 이여야 한다.
유클리드 알고리즘 : 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다
유클리드 알고리즘은 아래 2개를 기반하고 있다.
- gcd(a, b) = a이며 0은 모든 정수의 배수이고 모든 정수는 0의 약수이다.
- gcd(a, b) = gcd(b, r)이다, 이 때 r은 a을 b로 나눈 나머지다.
계산을 할 때는 알고리즘 표를 작성을 해야 계산하기 유리하다.
위와 같은 형태가 유클리드 알고리즘을 계산할 때 쓰이는 "표" 이다.
유클리드 알고리즘은 사용은 하나 한계가 있기에 이름하여 "확장된 유클리드 알고리즘" 을 사용한다.
확장된 유클리드 알고리즘이며 r = r1 - (q x r2), s = s1 - (q x s2), t = t1 - (q x t2) , s1 = 1, s2 = 0, t1 = 0, t2 = 1은 해당 알고리즘에 고정된 값이며, 주로 사용되는 공식은 디피헬먼, RSA, 역원, 원시근등이 존재한다.
확장된 유클리드 알고리즘의 공식은 (a x s) + (b x t) = d , d는 최대공약수 1이다.
양수가 아닌 음수가 존재 할 때
- a > 0, b < 0 인 경우
- a < 0, b > 0 인 경우
즉, r1 = 음의 정수(피제수), r2 = 양의 정수(제수) 로 계산을 시작해야한다.
'Math > Crypto math' 카테고리의 다른 글
| [정수론], 합동식 (0) | 2023.10.30 |
|---|---|
| [정수론], 소수와 소인수 분해 (0) | 2023.10.28 |
| [정수론], 정수론의 시작 집합 (1) | 2023.10.24 |
| [정수론], 기초 암호의 역사 이론-2 (1) | 2023.10.23 |
| [정수론], 기초 암호의 역사 이론-1 (0) | 2023.10.23 |