[DiscreteMath]정수론

📚나눗셈

📄나눗셈

a는 정수이고 b는 양의 정수라 할 때, 다음을 만족하는 유일한 정수 q, r이 존재한다.

a = bq + r

단, 0 <= r < b

📄약수와 배수

a,b가 정수이고 a ≠ 0 일 때, b = ac를 만족시키는 정수 c가 있다면 ‘a가 b를 나머지 없이 나눈다’ 또는 ‘a는 b를 정제한다’ 또는 ‘b는 a로 나누어 떨어진다’라고 표현합니다. 이 경우 a는 b의 약수 또는 인수, b는 a의 배수라고 합니다. 기호로는 a∣b로 나타냅니다.

a가 b를 나누지 않을 때에는 a∤b로 나타냅니다.

📄최대공약수

두 개 이상의 정수에서 공통된 약수를 공약수라고 합니다. 두 정수의 최대공약수는 두 정수의 모든 양의 공약수를 찾고 그 공약수 중 가장 큰 수를 찾으면 됩니다.

• 최대 공약수

0이 아닌 두 정수 a,b에 대하여 d∣a이고 d∣b인 최대의 향의 정수 d를 a와 b의 최대공약수라고 하고 d = gcd(a, b)로 표시한다.

• 서로소

a,b에 대하여 gcd(a,b) = 1을 만족하면 정수 a와 b는 서로소라고 합니다.

📄유클리드 호제법

최대공약수는 유클리드 호제법을 사용하여 쉽게 계산할 수 있습니다.

a, b, q, r이 정수일 때, a = bq + r이면 gcd(a, b) = gcd(b , r)이다.

위의 정리를 알고리즘으로 표현하면 아래와 같습니다.

1. b∣a이면 gcd(a, b) = b이다.
2. a∤b이면 다음과 같은 나눗셈 알고리즘을 적용한다.

\[\begin{align} a = bq + r& \quad\quad 0 < r < b \\ a = rq_1 + r_1& \quad\quad 0 < r_1 < r \\ a = r_1q_2 + r_2& \quad\quad 0 < r_2 < r_1 \\ a = r_2q_3 + r_3& \quad\quad 0 < r_3 < r_2 \\ ...\\ r_{n - 2} = r_{n - 1}q_n + r_n& \quad\quad 0 < r_n < r_{n-1} \\ r_{n - 1} = r_{n}q_{n + 1} + 0& \end{align}\]

따라서 \(gcd(a, b) = gcd(b, r) = gcd(r, r_1) = ... = gcd(r_{n-1}, r_n) = r_n\) 이 됩니다.

📚나머지 연산

📄모듈로 합동

a, b가 정수이고 m이 양의 정수일 때, a - b가 m으로 나누어떨어진다면 a와 b는 모듈로-m 합동이라고 합니다. 모듈로-m 합동은 기호로 a ≡ b(mod m)으로 나타냅니다.

• 합동 정리

m > 1이 고정되고 a, b, c, d를 임의의 정수라고 할 때, 다음 성질이 성립합니다.

1. a ≡ a(mod m)
2. a ≡ b(mod m) 이면 b ≡ a(mod m) 이다.
3. a ≡ b(mod m) 이고 b ≡ c(mod m) 이면 a ≡ c(mod m)이다.
4. a ≡ b(mod m) 이고 c ≡ d(mod m) 이면 a + c ≡ b + d(mod m) 이고 ac ≡ bd(mod m) 이다.
5. a ≡ b(mod m) 이면 a + c ≡ b + c(mod m) 이고 ac ≡ bc(mod m) 이다.
6. a ≡ b(mod m) 이면 모든 양의 정수 k에 대해 a^k ≡ b^k(mod m)이다.

📚소수와 소인수분해

1 보다 큰 모든 자연수는 최소한 두 개의 자연수로 나누어떨어집니다. 어떤 자연수는 1과 자기 자신 이외에는 약수를 가지지 않는데 이런 자연수를 소수라고 합니다.

📄소수와 함성수

1보다 큰 자연수 p는 p의 양의 인수가 1과 p뿐일 때 소수라고 합니다. 1보다 크면서 소수가 아닌 자연수는 합성수라고 합니다.

• 소인수
  주어진 자연수를 나누어 떨어뜨리는 약수 중에서 소주인 것을 말합니다.

• 소인수 분해
  합성수를 소인수의 곱으로 표현하는 것입니다.

📚RSA 암호

📄페르마의 작은 정리

암호학에서 bⁿ mod m을 효율적으로 계산하는 것이 필요합니다. 페르마의 작은 정리는 거듭제곱 형태의 수를 나누었을 때 나머지를 효과적으로 계산하는 방식입니다.

p가 소수이고 a가 p로 나눌 수 없는 정수이면, a^p-1 ≡ 1 (mod p)입니다. 또한 모든 정수 a에 대해 a^p ≡ a (mod p)입니다.

📄나머지 거듭제곱 알고리즘

m이 자연수이고 a, b는 정수라고 하면, 다음 두 등식이 성립합니다.

1. (a + b)mod m = ((a mod m) + (b mod m)) mod m
2. ab mod m = ((a mod m)(b mod m)) mod m

📄RSA 암호

RSA(Rivest-Shamir-Adleman) 암호 알고리즘은 두 개의 큰 소수를 곱하여 만들어진 합성수의 소인수분해를 하기 어렵다는 원리에 기반을 둔 암호방법입니다. RSA 암호 시스템에서 필요한 키는 공개키와 개인키가 있습니다. 공개키는 공개목록에 등록하고 개인키는 비밀리에 보관합니다.