[암호 수학] 정수론

1. 약수(Divisors) 

24의 양의 약수 = 1, 2, 3, 4, 6, 8, 12, 24

어떤 수를 나누었을 때 나머지가 0이 되는 수이다.

+ 모든 자연수는 1과 자기 자신을 약수로 갖는다.

+ 'a는 b의 약수이다'를 a|b라고 표현하기도 한다.

 

2. 공약수(Common Divisor)

a,b 가 정수일 때 d|a 이고 d|b 이면 d 는 a와 b의 Common Divisor(공약수) 이다.

 

3. 최대 공약수 - GCD (Greatest Common Divisor) 

d > 0 이고, d가 a와 b의 공약수들 중 가장 큰 수면, d 는 a와 b의 gcd(최대공약수)이다. 

+ gcd(a,b) : a와 b의 최대공약수

+ 공약수는 최대공약수를 나눌 수 있다.

d' : a와 b의 공약수

d : a와 b의 최대공약수

d' | d 가 성립한다.

 

4. 소수(Prime Numbers) 

1 보다 큰 자연수 중 1과 자기 자신밖에 약수가 존재하지 않는 자연수이다.

즉, 소수는 1과 자신의 수만을 약수로 갖는다.

 

5. 서로소(Relatively Prime Number)

8과 15는 서로소이다.
* 8의 약수 : 1, 2, 4, 8
* 15의 약수: 1, 3, 5, 15

어떤 두 수가 공통적인 소인수를 갖지 못할 때 두수를 서로소라고 한다.

 

6. 모듈러 연산 ( mod )

어떤 양의 정수 n과 어떤 정수 a가 주어지고 만약 a를 n으로 나눈다면 다음과 같은 관계를 가지고 몫(Quotient) q와 나머지r(Remainder)을 얻는다.

a = q / n
a = qn + r (0 <= r < n) a ≡ r mod n
q = a div n
r = a mod n

 

7. 페르마 정리

만약 p가 소수라면, a는 p에 의해 나누어지지 않는 양의 정수라고 한다면,
a**(P-1) mod p = 1

+ a**() 은 a의 거듭제곱을 나타낸다.

 

8. 오일러 정리

☞ 오일러의 totient 함수 (φ(n))

φ(n) : n보다 작고 n과 서로 소인 양의 정수의 개수

n	1	2	3	4	5	6	7	8	9
φ(n)	1	1	2	2	4	2	6	4	6

 

☞ 오일러 정리

서로소인 모든 a와 n에 대한 관계를 나타낸다.

a**φ(n) ≡ 1 mod n 
a**(φ(n)+1) ≡ a mod n

 

9. DAT (Division Algorithm Theorem)

a, b 가 정수일 때, a != 0 이면
a = bq + r ( 0 <= r < b ) 가 되는 정수 q와 r이 존재한다.

→  a mod b = r

 

10. GCD Theorem - Bezout's Threorem

a, b 가 정수일 때, 
ax + by = gcd(a,b) 가 존재한다. (x,y 는 정수)

+ 증명

S = {au+bv | u,v ∈ 정수 and au+bv > 0} 라는 집합이 존재할 때,

S 의 가장 작은 원소를 e, gcd(a,b) = d 라고 하자.

 

e = ax + by (x,y ∈ 정수) 에서

1) DAT(a,e) 에 의해 a = eq + r ( 0 <= r < e) 가 성립한다.

r = a - eq = a - (ax + by)q = a(1 - xq) + b(-tq) 이다.

a(1 - xq) + b(-tq) ∈ S 이지만 DAT(a,e)에 의해 r < e 이기 때문에,

a(1 - xq) + b(-tq) < e 이다.

e는 집합 S의 가장 작은 원소이며 0 <= r < e 이기 때문에 r = 0 가된다.

따라서 DAT(a,e)에 의해 a = qe 가 된다. 이것은 e|a 로 도달할 수 있다.

 

2) DAT(b,e) 에서 위의 1과 같은 방법으로 e|b 로 도달할 수 있다.

 

1)과 2)에 의해서 e|a 이고, e|b 이기 때문에 e 는 a와 b의 Common Divisor(공약수) 이다.

㉮ 모든 공약수는 최대공약수를 나눌 수 있기 때문에 e|d 가 성립한다.

 

㉯ gcd(a,b) = d 라는 의미는

a = dg , b = dh (g , h ∈ 정수)로 해석할 수 있다.

e = ax + by 에서 e = dgx + dhy 로 나타낼 수 있다. 즉,

e = dgx + dhy = d(gx + hy) 는 곧 d|e 를 나타낸다.

 

㉮ 와 ㉯ 에 의해 e|d (e <= d), d|e (d <= e)가 성립하므로 e = d 즉,

gcd(a,b) = ax + by (x,y ∈ 정수) 가 성립한다.