현대 암호학: 정수론

학습 목표:

가분성(Divisibility)과 나눗셈 알고리즘 이해

최대 공약수를 계산하는 유클리드 알고리즘 이해

모듈러 연산 개념 이해

확장 유클리드 알고리즘 이해

소수(Prime Number)에 관련한 핵심 개념 이해 

페르마의 소정리(Fermat's theorem) 및 오일러 정리 이해

Euler’s totient 함수 이해

소수성(Primality) 테스트 이해

중국인의 나머지 정리 이해

이산대수 문제 이해

---

Divisibility(가분성)

 

가분성:

가분성: 0으로 나뉘지 않는 b로 a를 나눈다. 나머지가 없을 때, a = mb이고 a,b, m는 인수이다.

'b | a ':  a가 b로 나누어 떨어진다. 이 경우 b는 a의 약수이다.

ex) 24의 양의 약수는 1,2,3,4,6,8,12,24이고 a =24, b = 1,2,3,4,6,8,12,24인 것.

 

확장:

a | 1이면 a = ±1이다.

a | b 와 b | a이면  a = ±b이다.

0이 아닌 b는 0으로 나눌 수 없다.

a | b와 b | c이면  a | c이다. (Q.E.D: b =ak, c= bp이면 c = apk이므로 a로 나누어짐)

b | g와 b | h이면 b | (mg + nh)이다. (Q.E.D: g = bp, h = bq이면 mbp + nbq = b(mp + nq)이므로 b로 나누어짐 //공통분모)

 

나눗셈 알고리즘

정수론에서의 나누기는 INT-DIV(a, n)로 표기하고 (q, r)을 반환한다. (q = 몫, r = 나머지)

a = qn + r   (0 ≤ r < n; q= [a/n])

---

유클리드 알고리즘

 

유클리드 알고리즘: 두개의 공약수라고 중 가장 큰 최대공약수를 구하는 알고리즘.

서로소: 공약수가 1밖에 없는 수.

소수: 약수가 1과 자기 자신밖에 없는 수. (소수끼리는 항상 서로소이다.)

 

GCD(최대공약수)

공약수: a와 b인 두수를 나누는 약수 중 둘다 나눌 수 있는  약수

최대공약수: a 와 b인 두 수의 공약수 중 가장 큰 공약수

gcd(a, b) = k (k = 최대공약수)

gcd(0 ,0) = 0

서로소: gcd(a, b) = 1

 

유클리드 알고리즘

위 사진을 보면서 

gcd(a, b) = d이면

a =qb + r1

b = r1q1 + r2 

순서로 나머지가 없어질 때까지 진행하면 된다.

---

모듈러 연산

 

a mod n = r  

모듈러는 나머지 연산으로 불리며 r은 a를 n으로 나누었을 때의 나머지이다.

 

불러오기: a = qn + r   (0 ≤ r < n; q= [a/n])

이해가 쏙쏙 되잖아 쌀슝아:  

- a = qn + r을 같이 써놓자.   

- a mod n 은 a/n으로 보고 나머지를 구하면 쉽다.

- a가 음수이면 n에 q를 곱할 때 가장 |a|에 가까운 값이 나오게 한다.

 

a ≡ b (mod n) means a mod n = b mod n

a와 b를 n으로 나눌 때 나머지가 같으면 'a와 b는 모듈러 n에 대해 합동이다'라고 한다.

 

이해가 쏙쏙 되잖아 쌀슝아:  

- n | (a-b)이면 a ≡ b (mod n)이다. 즉 a - b = nk 

- 삼단논법 쌉가능(Q.E.D: a와 b가 n에 대해 합동이다, a와 c가 n에 대해 합동이다.(a = q1n + r, b = q2n + r, c = q3n +r)

 

모듈러는 분배법칙, 결합법칙, 항등원, 역원이 있다.

= 군임 

 

(a+b) ≡ (a+c) (mod n)이면 b와 c는 n에 대해 합동이다.

(a*b) ≡ (a*c) (mod n)이면 b와 c는 n에 대해 합동이다.

불러오기: n | (a-b)이면 a ≡ b (mod n)이다. 즉 a - b = nk   

Q.E.D: b-c = nk, (a+b) - (a+c) = nk //  a*(b-c) = a*nk

 

모듈러 역원 계산하기

모듈러 역원을 구하려면 a와 n이 서로소여야 한다.

gcd(a, n) = 1이 있다고 하면 a^-1 mod n을 계산하고 싶다.

즉 aa' ≡ 1 (mod n)을 만족하는 a'인 역원을 구하고 싶다.

(d,a′,n′) ← EXT-GCD(a,n)이라 가정하면 

d = 1 = gcd(a, n) = aa' + nn'

양변에 mod n을 하면  aa' ≡ 1 (mod n)이므로 nn' ≡ 0 (mod n)이다.

Q.E.D: 1 mod n =  1 (n은 a와 서로소이므로 1 불가), aa' mod n = 1 이므로 nn' = 0이어야함.

---

확장 유클리드 알고리즘

 

확장 유클리드 알고리즘: gcd를 제외한 값을 구하기 위해 확장됨.

베주 항등식: gcd(a, b) = d = ax + by

EXT-GCD(a, b)는 d, x, y를 반환한다.

응용:

a mod n = r 이고 몫이 q라고 하면  gcd(a, n) = gcd(n, r)

a = qn + r

Q.E.D:

1. a와 n의 최대공약수 d는 a와 n으로 나뉨. a = qn + r, d= ank

2. n와 r의 최대공약수 e는 n와 r로 나뉨. n = es, r = et

3. a = esq + et = e(sq + t)로 e는 a의 약수임.

d는 a와 n의 최대공약수이고

e도 a와 n의 최대공약수이며 n과 r의 최대공약수이다.

---

소수

 

소수는 1과 자기자신만을 약수로 가진다.

소수는 정수론에서 중요하다. why?

소인수분해!

소인수분해: 모든 수는 소수의 곱으로 표현할 수 있다.

소인수분해: p는 소수

소수와 최대공약수

최대공약수가 d이면 d = gcd(a,b)이고 d는 a와 b의 공통된 가장 작은 소수 거듭제곱의 곱이다.

Q.E.D:

a = p1^a1 x p2^a2 ...pt^at

b=  p1^b1 x p2^b2 ...pt^bt

들 중 가장 작은 a와 b가 공통으로 가지는 p중 가장 a와 b의 pt계수가 작은 것 고르고 곱하면 최대공약수.

---

페르마 정리

임의의 소수 p에 대해 p와 서로소인 어떤 수의 (p−1)제곱을 p로 나눈 나머지는 무조건 1이다.

모든 정수 a에 대해 소수 p로 나눈 나머지는 a와 a^p는 같다.

---

오일러 피 함수

 

오일러 피 함수는  n과 서로소인 n 이하의 자연수의 개수이다.

φ(n)= ∣{m:1≤ m ≤n, gcd(m,n) = 1 }|

𝜑(1) = 1

 

오일러 피 함수 응용

𝜑(p) = p - 1 (p는 소수)

 

𝜑(mn) =𝜑(m) x 𝜑(n) ( gcd(m,n) = 1)

>>> m,n이 소수인 경우 항상 소수끼리는 서로소이므로 

 

𝜑(pq) = 𝜑(p) x 𝜑(q) = (p-1) x (q-1)

>>> RSA의 기초이다.

 

𝜑(p^k) = {p^(k-1)} x {(p-1)} (p는 소수)

---

오일러 이론

>>> 모든 a, n이 서로소이면 위 식이 가능하다.

---

소수 판별

 

★밀러-라빈 알고리즘 

 

소수 판별 알고리즘

2002년 이전에는 큰 수의 소수 판별이 확률적이었으나, AKS 알고리즘의 개발로 인해 처음으로 효율적인 결정론적 소수 판별이 가능해졌다.

그러나 실제 성능 면에서는 확률적 알고리즘인 Miller-Rabin 알고리즘보다 빠르지 않을 수 있다.

 

소수는 무한하다

메르센 소수: 2^p - 1 (p = 소수)

 

소수의 분포: 

소수 계량 함수 π(x): 어떤 양수 x에 대하여 x보다 작거나 같은 소수의 개수 ==  대략 x / ln 𝑥 개

소수일 확률 = π(x) / X = 1 / ln X

즉 소수가 커질수록 소수의 개수는 줄어든다.

(홀수인 경우 확률이 2배가 됨 == 짝수는 2를 제외하면 소수가 아니므로)

 

소수와 등차수열: 폴 에르되시는 2보다 큰 모든 양의 정수 n에 대해, 전부 소수로 구성된 길이 n의 등차수열이 있다고 추정

---

중국인의 나머지 정리

 

 

 

 

---

이산 로그

 

이산 로그 함수: b  =  a^i (mod p)이면 i가 이산로그이다.

이산로그