[이산수학#13] 정수론

1. 나눗셈

a, b가 정수, a가 0이 아닐 때, b=ac 를 만족시키는 정수 c가 있다면 a가 b를 나머지 없이 나눈다

=> a는 b의 약수(인수), 배수는 a|b로 표현

 

최대공약수 : d = gcd(a, b)로 표현, 0이 아닌 두 정수 a,b에 대해 d|a, d|b인 최대의 양의 정수 d를 a와 b의 최대 공약수

gcd(a,b) = 1인 경우, a,b는 서로소

 

베주의 항등식 : 적어도 하나는 0이 아닌 두 정수 a,b가 gcd(a, b) = d라 할 때, ax + by = d를 만족하는 정수 x, y 존재

- a,b가 서로소 => gcd(a,b) = 1 => ∃𝒙, 𝒚 ∈ 𝒁, 𝒂𝒙 + 𝒃𝒚 = 1

 

유클리드 호제법(알고리즘)

- 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘

- 두수가 서로 상대방 수를 나눠 원하는 수를 얻는 알고리즘

- a,b,q,r 가 정수면, a = bq + r이면 gcd(a,b)=gcd(b,r)

 

2. 나머지 연산

나머지 함수 : 정수 n과 양의 정수 m에 대해 n을 m으로 나눴을 때 나머지를 구하는 함수, n mod m으로 표기

모듈로 합동 : a, b가 정수 m이 양의 정수면, a-b가 m으로 나눠떨어지면 a와 b는 모듈로-m 합동, a = b(mod m)으로 표기

a mod m = b mod m이 필요충분조건

 

3. 소수와 소인수분해

소수 :1보다 큰 자연수 p는 p의 양의 인수가 1과 p뿐일 때

합성수 :1보다 크면서 소수가 아닌 자연수

소인수 : 주어진 자연수의 약수 중에서 소수인 것

소인수분해 : 합성수를 소인수들의 곱으로 표현

 

소수 판별법

- 만약 n이 합성수라면, n의 소인수 중 하나는 루트n보다 같거나 작다

 

가장 큰 소수 찾기

- 𝟐^𝒑 − 𝟏 (단, 𝒑는 소수 | 합성수일 경우 소수가 아님)

 

소수 정리

4. RSA 암호

 

페르마의 작은 정리
나머지 거듭제곱 알고리즘