소수와 소인수분해
소수
- 1보다 큰 자연수 p는 p의 양의 인수가 1과 p뿐일 때 소수 라고 한다.
1보다 크면서 소수가 아닌 자연수는 합성수 라고 한다.
소인수
- 주어진 자연수를 나누어 떨어뜨리는 약수 중에서 소수인것
- 합성수를 소인수의 곱으로 표현하는 것
\(p 가 소수이고 p \| ab 이면, p \| a 또는 p \| b 이다.\)
\(p가 소수이고 p \| a_1a_2...a_n이면, 1 \le k \le n인 k에 대해 p \| a_k 이다.\)
\(p, q_1, q_2 .... q_n이 소수이고 p \| q_1q_2...q_n 이라면, 1\le k \le n인 k에 대해 p = q_k 이다.\)
- n이 2 이상의 자연수이면 n은 소수이거나 소수의 곱으로 유일하게 표현할 수 있다.
- 만약 n이 합성수라면, n의 소인수 중 하나는 \(\sqrt{n}\) 보다 같거나 작다.
- 무한히 많은 소수가 존재한다.
- x 이하의 소수의 개수 \(\pi\) x와 x/ln x 의 비율은 x가 무한히 커지면 1로 수렴한다.
RSA 암호
- 암호학에서는 \(b^n mod n\)을 효율적으로 계산하는 것이 필요하며, 이떄 자주 사용 되는 페르마의 작은 정리는 다음과 같다
p가 소수이고 a가 p로 나눌 수 없는 정수이면, \(a^{p-1} ≡ 1 (mod \ p) 이다.\) 또는, 모든 정수 a에 대하여 \(a^p ≡ a(mod \ p) 이다.\) - \(b^n \ mod \ n\)을 효과적으로 계산하는 또 다른 방법으로서 나머지 거듭제곱 알고리즘은 지수 n을
이진법으로 바뀐 뒤에 \(b^n\)을 2의 거듭제곱으로 형태로 만들어 계산하는 방법이다. - RSA 암호 알고리즘은 두 개의 큰 소수를 곱하여 만들어진 합성수의 소인수분해를 하기 어렵다는 원리에 기반을 둔 암호방법이다.
RSA암호 시스템에서 필요한 키는 공개키와 개인키, 두 가지가 있다.