03. 소수

소수(Prime Number)

소수는, 양의 약수가 1과 자기 자신 뿐인 1보다 큰 자연수

0.1 0.2는 /소수/로 발음하고, Prime Number인 소수는 /소쑤/로 발음한다.

(예전에는 Prime Number는 '솟수'로 썼었는데, 1998년 맞춤법 개정에서 6개의 한자어인 곳간, 찻간, 퇸간, 셋방, 숫자, 횟수를 제외하고는 사이시옷을 쓸 수 없다는 규정에 의해, '소수'로 바뀌었다. )

소수는 1과 그 자신만을 약수로 갖는 1보다 큰 자연수이다. 따라서, '1'은 소수가 아니고, '2'는 약수가 1과 2이므로 소수이다. 또한 3과 5도 1과 그 자신만을 약수로 가지므로 소수이다. 

즉, 소수를 나열해 보면, 2,3,5,7,11,13,17,19,23.... 등이다.

소수는 현대 암호학에서 매우 중요한 수이다. 소수가 가지는 특이한 성질 때문에 여러 알고리즘에서 자주 등장하므로 그 성질을 잘 알아둬야 한다.

소수의 성질: 1보다 큰 임의의 정수 n은 적어도 하나의 소인수를 갖는다.

소인수는 소수인 약수를 말한다. 이 성질은 '어떤 수라도 소인수분해를 할 수 있다'는 말과도 같다. 즉, 어떤 큰 수가 있을 때(예를들어 342,961,111) 이 수를 소인수분해하라고 하면, 이 수가 소수가 아니라면 무조건 어떤 작은 소인수가 존재하므로, 작은 소수부터 차례로 나눠가면 소인수를찾을 수 있다는 근거가 된다.

복잡하게 생각할 거 없이, '모든 수를 소인수분해할 수 있다'고 생각하면 된다.

이 생각을 좀 더 발전시키면, 곱셈의 관점에서 소수는 자연수를 이루는 성분이라 할 수 있다. 예를들어, 12 = 2²  × 3 으로, 자연수 12는 소수 2와3의 조합으로 표현할 수 있고, 그 조합은 (소인수의 순서를 무시하면) 단 한가지 방법만으로 소인수분해되는 것이다. 

증명은 다음과 같다. (그리 복잡하지 않고, 한 번 논리적으로 수긍하게되면 기억에 오래 남으므로 해보도록 한다.)

• n이 소수이면 n = n·1 이므로, n은 그 자신인 소인수를 가지므로, 하나 이상의 소인수를 갖는다고 할 수 있다.
• n이 소수가 아니라면 자기자신이 아닌 약수들이 존재할 것이다. 이 약수 중에서 가장 작은 약수를 a라하면 a는 소수이다.
  왜냐하면, 만약 a가 소수가 아니면 a=p·q, p<a 인 p가 존재할 것이고, p|n 이 되므로(∵ a|n인데 a=p·q이므로), 최초의 가정인 a가 n이 가장 작은 약수라는 가정에 위배되므로, a는 소수이다.   

소수의 성질: n이 합성수이면 n은 √n보다 작은 소인수 p를 가진다.

예를 들어 n=77 이라면, √n보다 작은 수, 즉 9이하인 수 중에서 소인수가 존재한다는 의미이다. (77 = 7 × 11)

이 성질은 어떤 수n에 대해서 소인수분해를 해야해서, 가장 작은 소수인 2부터 시작해서 차례로 소인수가 될만한 소수들을 찾아나갈 때,  √n이 될 때까지도 소인수가 없다면 n은 소인수가 없다, 즉 'n은 소수'라는 결론을 낼 수 있는 근거가 된다. (√n이 될 때까지만 뒤지면 된다)

증명은 간단하다.

n이 합성수이면 n=pq(1<p≤q)인 p,q가 존재한다. 여기서 p²  ≤ n 이므로(왜냐면 두수의 곱 중에서 작거나 같은 수를 p라고 가정했으므로 p가 가장 커질 때는 p=q일 때이고 이때 pq=p²=n이다. 그 이외는 p<q이므로 p²<n ), p ≤ √n 이 되어, n은 √n보다 작은 소인수 p를 가지는 것이다.

(유클리드 정리) 

소수는 무한히 많다.

RSA암호의 경우 일반적으로 512비트 정도의 소수를 사용한다. 이것도 작은 수가 아닌데, 요즘은 RSA의 키로 1024비트정도의 큰 소수를 사용한다. 이렇게 수가 커져가도 소수는 존재할까? 

존재한다고 한다. 그것도 무한하게 많이.

그리이스 수학자인 유클리드는, 소수가 무한히 많음을 다음과 같은 논리로 간단히 증명했다.

• 유한 개의 소수가 존재한다고 가정하자.
• 이 유한 개의 소수들을 모두 곱한 값에 1을 더한다. 
• 그 결과값은 다른 어떤 소수로 나누어도 나머지가 1이므로 어떤 소수로도 나누어 떨어지지 않는 수가 된다.
• 따라서 이 수가 소수라면 기존의 최대소수보다 큰 소수가 있다는 것이 증명되고, 이 수가 소수가 아니라고 해도 기존의 최대소수보다 큰 소수가 있어야 한다는것을 의미하기 때문에 소수가 유한하다는 애초 가정에 모순이 존재함을 알 수 있다.

 

1보다 큰 임의의 정수 n은 다음과 같은 형태로 유일하게 표현된다.

        n = p₁^α1 ···p_k^α2

여기서, p₁,···,p_k 는 서로 다른 소수이고 p₁<p₂<···<p_k이며, α₁,···,α_k 는 양의 정수이다.

이 말은 지수승이 있는 복잡한 수식으로 되어 있어 어려워 보이지만, 사실 앞에서 논한 바 있는 '1보다 큰 정수 n은 적어도 한 개 이상의 소인수를 갖는다'와 동일한 말이다.

즉, 어떤 정수라도 소인수분해를 할 수 있다는 말이고, 이것을 수식으로 표현하면 n = p₁^α1 ···p_k^α2 이 되는 것이다.

예를 들어 360을 소인수분해하면 360 = 2³·3²·5¹ 이라는 거다.