소수, 소수 판정 - 공부하는 도비

암호학에서 소수는 상당히 많이 사용된다. 

앞으로 소수와 관련된 내용을 정리하며, 암호에 대한 중요한 개념을 다뤄보려고 한다.

 

* 소수 : 하나의 양정수가 오직 1이나 자신으로만 나누어 떨어진다는 말과 동일하다.

 

→ 소수와 관련된 몇가지 사실

1) 가장 작은 소수는 2이다.

- Proof) 2는 1과 2로만 나누어 떨어지기 때문이다. 

 

2) 1은 소수가 아니다.

- Proof) 소수는 서로 다른 두 개의 정수로만 나누어 떨어져야 하고, 그 이상이나 그 이하의 정수로 나누어져서는 안된다. 1은 오직 자신에 의해서만 나누어지기 때문에 1은 소수가 아니다.

 

3) 소수는 무한하다.

- 소수가 무한하다는 증명은 몇 가지가 있는데, 가장 유명한 유클리드의 증명을 살펴보기로 한다. 

우선, 소수가 유한하다고 가정한다.

* 소수 판정법

 

1) 결정적 소수 판정 알고리즘

• 임의의 변수를 사용하여 소수라는 결론을 얻음으로써 100% 소수임을 판정하는 방법
• 정확하게 판정하는 방법이지만, 판정하는데 시간이 오래 걸려 현실적이지 못함
• 고전적 방법인 Sieve of Eratosthenes (에라토스테네스의 체)방법, Euclid (유클리드) 방법 및 Wilson(윌슨) 방법
• 최근 Adleman, Pomerance와 Rumley가 개발한 APR 방법

2) 확률적 소수 판정 알고리즘

• 임의 변수를 사용하지 못하고 특정한 값들을 사용하여 소수를 판정하는 방법으로 100% 소수로 판정하지는 못하더라도 적당한 확률 이상으로 소수임을 판정하는 방법
• 결정적으로 어떤 자연수가 소수인가를 판정할 수는 없지만 높은 확률을 가지고 빠르게 판정하는 것이 장점
• Lehmann-Peralta 알고리즘, Solovay-Strassen 알고리즘과 Miller-Rabin 알고리즘 등