#1. 기초 정수론

 

 

기초 정수론 1. 정수와 나눗셈 2. 소인수와 소인수분해

 

 

암호와 대수적 구조

 

 

 

 

1. 정수와 나눗셈

 

 

 

숫자 집합

표기	집합
R	실수 집합
Z	정수 집합
N	자연수 집합

 

- 소수 (prime)

   약수가 1과 자기자신만 있는 2보다 크거나 같은 수

   ex) 2, 3, 5, 7, ...

 

- 합성수 (composite)

   소수가 아닌 2보다 크거나 같은 수

   ex) 4, 6, 8, 9, ...

 

- 서로소 (Relatively prime)

   두 정수 a, b가 "서로소 (relatively prime) 이다" <=> a와 b의 공약수가 1밖에 없다

   ex) 5 & 6, 9 & 14

 

 

 

 

집합과 연산

집합 A가 연산 ⊗에 닫혀 있다

모든 A의 원소 a, b에 대해 a⊗b도 A의 원소이다.

 

항등원 (identity)

연산 ⊗에 대해 집합 A의 원소 e가 항등원이다.

<=>  모든 A의 원소 a에 대해, a⊗e = a이다.

 

역원 (inverse)

연산 ⊗에 대해 A의 원소 b가 A의 원소 a의 역원이다

<=> a⊗b = e <=> (표기) b = a^(-1)

 

집합	덧셈	덧셈 항등원	덧셈 역원	곱셈	곱셈 항등원	곱셈 역원
자연수	닫혀 있다	없다	없다	닫혀 있다	1	없다
정수	닫혀 있다	0	-a	닫혀 있다	1	없다
실수	닫혀 있다	0	-a	닫혀 있다	1	1/a

 

 

 

 

 

 

나눗셈 정리

- a, b: 임의의 정수, b ≠ 0 - 다음을 만족시키는 정수 q (몫), r (나머지)이 유일하게 존재한다.   ㄴ a = bq + r   ㄴ 0 ≤ r < lbl

ex)

a = 7, b = 3 => 7 = 3 x 2 + 1

a = 7, b = -3 => 7 = -3 x (-2) + 1

a = -7, b = -3 => -7 = -3 x 3 + 1

 

 

 

 

약수와 배수

[표기] 정수 b가 a의 약수이다 <=> b l a

 

최대공약수

[표기] 양의 정수 c가 두 정수 a와 b의 최대공약수 <=> c = gcd(a,b)

GCD 정리 a,n: 임의의 정수 & d =gcd(a,n) => 1) as + nt = d 를 만족시키는 두 정수 s, t 가 존재한다. (단, 유일하지는 않음)      2) a, n을 위와 같은 방식으로 결합했을 때 gcd(a,n)이 얻을 수 있는최소의 자연수이다.          (즉, 임의의 두 정누 s', t'에 대해  l as' + nt' l ≥ d )

ex)

a = 6, n = 9  =>  gcd(a,n) = 3 = 6 x (-1) + 9 x 1

a = 1180, n = 482  =>  gcd(a,n) = 2 = 1180 x (-29) + 482 x 71

 

 

 

 

 

 

 

2. 소수와 소인수 분해

 

- 소수 (prime)

p가 소수이고 a, b는 정수라고 하자. p l ab 이면 p l a 또는 p l b 이다. p가 소수이고, a1, a2 ...an이 정수라고 하자. => p l (a1 x a2 x ... x an) 이면 어떤 수 ai 에 대해 p l ai 이다.

 

 

 

 

 

 

소인수 분해정리

1을 제외한 모든 양의 정수는 소수들의 곱으로 표시되며 그 표시 방법은 (곱하는 순서를 무시하면) 유일하다.

소수 p는 그 자체를 하나의 소수의 곱으로 간주

 

소수는 무한히 많다.

pf) '소수는 유한하다' 로 가정한다

 

소수의 집합 Q = {p1, p2, p2, ... , pn}

 

Q집합의 모든 원소를 곱한 후 1을 더한 값을 p로 하면 다음과 같이 나타낼 수 있다.

p = p1 x p2 x ... x pn + 1 

 

위 p는 모든 소수에 대해 나머지가 1이다.

따라서 p는 소수이며 pn보다 큰 소수가 존재하다는 것이 밝혀지며 전제가 틀리게된다.