소수 (prime number)

소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수를 의미한다. 예를 들어, 자연수 2, 3, 5의 약수는 1과 자기 자신뿐이기 때문에 자연수 2, 3, 5는 소수라고 할 수 있다.

개요

소수의 개수는 무한하며, 이 명제를 유클리드의 정리라고 한다. 가장 오래된 증명은 그리스 수학자 유클리드의 《유클리드 원론》(제 9권, 정리 20)에서 볼 수 있다. 유클리드의 증명은 “어느 주어진 유한한 소수들 보다 더 많다.”라는 결론으로 표현되었다. 소수와 합성수를 구분해낼 수 있는 명확한 공식은 지금까지도 밝혀지지 않은 상태이나, 대역적으로 자연수 중 소수의 비율의 근사치를 예측하는 모델로는 여러가지가 알려져 있다. 이러한 방향으로의 연구의 첫 결과는 19세기 말에 증명된 소수 정리인데, 이는 무작위로 선택된 한 수가 소수일 확률은 그 수의 자릿수, 곧 로그값에 반비례함을 알려준다.

역사

유클리드(Euclid)

• 유클리드(Euclid)

이집트인들의 기록을 살펴보자면 그들이 소수에 대한 약간에 지식이 있었던 것으로 보인다. 예를 들어, Rhind papyrus에는 여러가지 소수들과 합성수 들이 쓰여져 있었다. 그러나 실질적으로 소수에 대한 연구가 시작된 것은 고대 그리스 부터였다. 유클리드(Euclid)가 저술한 원론(기원전 300년)에서는 몇 가지 기본적이고 중요한 증명들이 있는데 예를 들면 소수의 무한성도 그 중 하나였다. 또한 유클리드는 Mersenne 소수로 부터 어떻게 완전수를 만들 수 있는지도 보였다. 에라토스테네스(Eratosthenes)가 고안한 에라토스테네스 체(Sieve of Eratosthenes)는 소수를 찾기에는 가장 간단한 방법이지만 현재 큰 소수를 찾는 컴퓨터는 이 알고리즘을 택하지 않는다. 그리스 이후 17세기까지 소수에 대한 연구는 큰 진보를 하지 않았다.

페르마(Pierre de Feramt)

• 페르마(Pierre de Feramt)

1640년 피에르 데 페르마 (Pierre de Fermat) 는 그의 페르마 소정리 (Fermat's little theorem)를 발견하였고, 이는 후에 라이프니츠(Leibnitz)와 오일러(Euler)에 의해 증명되었다. 참고적으로 페르마 소정리의 특정 부분은 훨씬 전부터 중국에서도 알려져 있었다. 페르마는 n=4 일 때 까지를 검토해 본 후 모든 2^2ⁿ+1 꼴의 수는 소수일 것이라고 추측하였으나 그 54번 째 페르마 수인 $2^{32}+1$은, 오일러에 의해 641의 배수임이 밝혀졌다.

마린 메르센느(Marin Mersenne)

• 마린 메르센느(Marin Mersenne)

프랑스의 수도사 마린 메르센느(Marin Mersenne)는 $2^{p}-1$ 꼴의 소수(p는 소수)에 대한 연구를 하였고, 이 공로를 인정받아 $2^{p}-1$ 꼴의 소수는 나중에 메르센느 소수라는 이름이 붙는다.

오일러(Leonhard Euler)

• 오일러(Leonhard Euler)

오일러의 정수에 대한 연구는 소수에 대해 많은 결과를 낳았는데, 그는 다음과 같은 형태의 무한 급수

${\frac {1}{2}}$ + ${\frac {1}{3}}$ + ${\frac {1}{5}}$ + ${\frac {1}{7}}$ + ${\frac {1}{11}}$ + ···

가 발산함을 보여, 소수가 무한함을 유클리드와는 다른 방식으로 증명하였다. 또한 오일러는 2^p-1(2^p-1) 꼴의 수 (이 때, 두번째 항은 메르센느 소수) 들이 모두 유일한 짝수 완전수 꼴 임을 보였다. 하지만 현재까지도 홀수 완전수가 존재하는지 존재하지 않는지에 대한 어떠한 증명도 발견되지 않고 있다.

르장드르(Adrien-Marie Legendre)

• 르장드르(Adrien-Marie Legendre)

19세기 초에, 르장드르(Legendre)와 가우스(Gauss)는 독립적으로 $x$가 무한대로 발산할 때, $x$ 보다 작은 소수의 개수는 $x/log(x)$와 같다는 사실을 발견하였다. 1859년에 리만은 그의 논문에서 제타 함수(zeta-function)에 대한 아이디어를 선보였다. 리만의 아이디어를 이용하여 1896년 아다마르(Hadamard)와 발레푸생(Vallée-Poussin)은 독립적으로 소수 정리를 증명하였다. 이 후 수학자들은 매우 큰 수에 대하여, 이 수가 소수인지 아닌지 (짧은 시간에) 판단할 수 있는 방법을 모색했다. 이에 따라 1877년에는 페르마 소수들을 위한 Pépin's 테스트가, 1878년엔 Proth의 정리, 1856년엔 메르센느 소수들을 위한 Lucas–Lehmer 테스트 등이 발견되었다. 현대에 가장 많이 쓰이는 알고리즘으로는 APRT-CL, ECPP, AKS 등이 있지만 여전히 더 나은 알고리즘을 찾기 위해 많은 수학자들이 노력하고 있다. 오랜 시간동안 소수는 순수 수학 외에는 아무 쓸모가 없다고 판단되었으나, 1970년 발명된 RSA 암호 방식 (소인수 분해가 오랜 시간이 걸린다는 사실을 이용한 암호화 방식)을 통해 소수에 대한 생각이 완전히 바뀌게 되었다.

특징

• 소수는 1보다 큰 자연수이다. 즉, 1은 소수가 아니다.
• 소수의 약수는 1과 자기 자신뿐이다. 즉, 소수의 약수는 2개뿐이며, 역도 성립한다.
• 2는 소수이지만, 2를 제외한 모든 짝수는 2를 약수로 가지므로 소수가 아니다.
• 2, 3을 제외한 모든 소수는 자연수 n에 대해 6n-1 혹은 6n+1 꼴이다. 역은 성립하지 않는다.

예제

• 에라토스테네스의 체(Sieve of Eratosthenes)

1~100 까지의 모든 소수를 구한다고 가정했을 때,

1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
4. 지워지지 않은 수 중 제일 작은 5을 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
5. 지워지지 않은 수 중 제일 작은 7을 소수로 채택하고, 나머지 7의 배수를 모두 지운다.
6. 지워지지 않고 남은 수는 전부 소수이다.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

• C++

void getChe(int num) {
   int *arr;
   arr = (int *)malloc(sizeof(int) * num);
   int i = 2;

   // 입력받은 수 만큼 배열에 모두 초기화 해둔다.

   for (i = 2; i <= num; i++) {
       arr[i] = i;
   }
   
   for (i = 2; i <= num; i++) { 
       if (arr[i] == 0) // 이미 체크된 수의 배수는 확인하지 않는다.
           continue;
       for (int j = i + i; j <= num; j += i) { // i를 제외한 i의 배수들은 0으로 체크
           arr[j] = 0;
       }
   }

   // 출력

   for (i = 2; i <= num; i++) {
       if (arr[i] != 0)
           cout << arr[i] << " ";
   }
}

• JAVA

public class PrimeNumber1 {	
  public static void getPrime(int num, ArrayList<Integer> prime) {
    prime.add(2); 
	
    for (int i = 2; i <= num; i++) {
      for (int j = 0; prime.size() > j; j++) {
        if (i % prime.get(j) == 0) break; // 소수가 아닌 경우 pass
			
        if (j + 1 == prime.size()) // 소수일 때
             prime.add(i);
        }
     }
	
     for (Integer result : prime) {
         System.out.println(result);
     }
  }

  public static void main(String[] args) {
     ArrayList<Integer> prime = new ArrayList<Integer>();

     long start = System.currentTimeMillis();
     getPrime(30000, prime);
     long end = System.currentTimeMillis();
     System.out.println("수행시간 : " + (end - start));
  }
}

• 파이썬

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1): 
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

참고자료

• 〈소수 (수론)〉, 《위키백과》</ref>
• 수학방 공식 홈페이지 - https://mathbang.net/199
• 김동이, 〈정수론〉, 《오픈튜토리얼스》, 2015-04-09
• 〈2. 소수 구하기 - 에라토스테네스의 체〉, 《위키독스》
• 신매력, 〈(C++) 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체〉, 《티스토리》, 2013-09-29
• 신매력, 〈(JAVA) 소수 구하기 최적의 알고리즘 (1)〉, 《티스토리》, 2013-09-20
• jjycjn, 〈소수(Prime number) 이야기〉, 《티스토리》, 2016-09-09

같이 보기

• 자연수
• 약수
• 소인수분해

이 소수 (prime number) 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반