소수

1보다 큰 자연수 가운데 1과 자기자신을 제외하곤 약수가 없는 수. '솟수'라고도 쓰며 그렇게 읽히기도 한다.
대단할 것 같지만, 더이상의 설명은 없다. 하지만, 이 소수가 정수론을 이루는 두개의 축중 하나이며, 현대 암호학의 핵심이다.

Divisibility에 관해 잠시 살펴보자. 고교수준의 간단한 수학적인 개념이며, 잠시 짚고 넘어가기로 한다.

1,2,3,... 이라는 자연수(모든 자연수의 집합은 N이라 표시한다)가 존재한다. 자연수는 덧셈과 곱셈에 관해 닫혀 있으며, 덧셈과 곱셈에 대해 교환법칙, 결합법칙, 분배법칙이 성립한다. 게다가 두개의 다른 자연수는 그 크기로 정렬할 수 있으며, N에는 순서가 존재한다. 정수(Z)는 0, 1, -1, 2, -2,...로 나타낼 수 있으며 두개의 정수의 분수로 나타낼 수 있는 유리수(Q, the set of rationals)가 있다. 이러한 과정을 통해 실수(R)와 복소수(C)의 존재도 알 수 있다.

a와 b가 자연수라고 하자. 이때 a=bc를 만족하는 자연수 c가 있을 때 우리는 b가 a를 나눈다고 하며 b|a로 표현한다. 이때, b는 a의 약수(divisor)라고 하고 a는 b의 배수(multiple)이라고 한다. b|a라는 관계(relation)는 반사적(reflexive)이고 추이적(transitive)이지만 대칭적(symmetric)이진 않다. 참고로 b가 a를 나누면 b는 a보다 작은 수이다. 그러므로 어떤 자연수를 나누는 수의 개수는 유한하다. 이러한 Division의 개념은 정수(Z)까지 확장된다. 여기서 Division알고리즘이란, 어떤 정수 a,b가 있을 때, {{|a = bq + r, 0=< r < b|}}를 만족하는 정수 q,r이 존재한다는 것이다. 증명은 매우 간단하다. bq가 a보다 작은 가장 큰 곱이라고 할 때, bq < a < b(q+1)이다. a > bq이므로 r > 0 이고, a < bq + b 이므로 r < b 이다.

a와 b의 관계를 R 이라고 할 때,

• sysmmetric : aRb 이면 bRa 이다. (예: A=B 이면 B=A 이다. )
  
• reflexive : aRa 이다. (예: A=A 이다. )
  
• transitive : aRb이고 bRc이면, aRc이다. (예: A|B이고 B|C 이면 A|C이다) --> C=mB, B=nA 이면 C=mnA 즉, A|C
  
  

소수는 무한히 많다. 이것은 이미 유클리드 시대에 증명이 되어 있었다.
{{|
증명: 소수가 P1, P2, ..., Pn 의 n개뿐이라고 가정하자.
|}}

유클리드의 이 증명은 귀류법의 대표적인 예로, 많은 수학자들이 아름다운 증명으로 손꼽는다.

참고로 이 증명 과정을 오해하여 연속한 소수들을 곱한 다음 1을 더하여 새로운 소수를 만들 수 있다고 착각하는 경우가 많으나,

2 x 3 x 5 x 7 x 11 x 13 + 1 = 59 x 509

에서 보듯, 이 방법이 항상 소수를 만들어 내는 것은 아니다. 단지 이렇게 만들어진 수는 2,3,5,7,11,13으로는 나누어 떨어지지 않을 뿐이다.

(비전공자 gerecter의 상식에 따른 서술)
소수는 특정 숫자 근처에서 얼마나 많이 있고 적게 있는가? 어느 숫자 근처에 소수들이 몰려있고, 어느 숫자 근처에 소수들이 별로 없는가. 이것에 대한 완전한 증명은 아직까지 전혀 없다.

이것을 밝혀내는 가장 화끈한 방법은 현재, "리만 가설"이라는 것이 참임을 증명하는 것인데, 이것은 150년째 증명되지 못하고 있으며, 만약에 증명에 성공하면, 미국 메사추세츠주 케임브리지의 클레이 수학 재단에서 1백만 달러를 받을 수도 있다.

• gerecter의 의문
  

Pi 의 소수점이하 숫자들은, 3.14159216....과 같은 식으로 진행한다. 이 소수점을 자리수들을 특정한 단위로 끊었을 때, 예를 들면, 14 15 92 16과 같은 식으로, 이것들의 목록에는 소수가 몇개나 있고, 소수가 아닌 합성수가 몇 개나 있는가? 확실치 않다면, 이것이 보통 자연수의 소수 분포와 갖는 관계는 어떠한가?

Pi 에 대해 어떤 답이 주어졌다면, 2^(1/2) 이나, 3^(1/2) 과 같은 숫자들의 소수점 이하 숫자들에 대해서는 어떠한 결과를 얻을 수 있는가? 2^(1/2) + Pi 의 소수점 이하 숫자들이나, 2*2^(1/2) + Pi 혹은 3*2^(1/2) + 3*Pi 의 소수점 이하 숫자들은 어떤가. 이것과 자연수의 소수 분포와 그 관계를 연관시킬 수 있는가? 혹은 그 결과를 Pi의 소수점 이하 숫자들의 패턴이나 분포와 연결시킬 수 있는가?

이 문제로 숫자 패턴으로부터 숫자를 조사하는 계산의 속도와, 소수 분포도로 부터 소수 여부를 조사하는 계산의 속도를 따졌을 때, 이로부터 NP 문제와 P 문제 사이의 관계를 조사하는 근거가 될 수 있을 것인가?

최근에 발견된 소수 판별 다항시간 알고리즘: p는 소수이고, a < p 일 때, 모든 x에 대하여 ((x-a)^p) ≡ (x^p-a) (mod p) 항등식을 만족한다.
{{|
증명 : FermatsSmallTheorem에 의해 (x-a)^p≡x-a (mod p)가 성립한다. 그리고 (x^p - a) = (x^p) - (a) ≡ (x) - (a) (mod p)
|}}
See PrimalityTestIsP, http://www.cse.iitk.ac.in/news/primality.html

아직 PNPProblem은 풀리지 않았다.

more to come

SeeAlso 정수론 암호 http://www.utm.edu/research/primes/

수학분류