소수 이야기

소수(prime number)란 {2,3,5,7,1,13, ...} 과 같이 1과 자신만으로 나누어지는 1보다 큰 양의 정수를 말한다. 소수에 관하여 알려진 사실 가운데 가장 확실한 사실은 "소수는 무한히 많다"는 것이 증명(Euclid's second theorem) 되었다. 이렇게 무한히 많은 소수들은 매우 불규칙하게 나타난다. 그러므로 수가 충분히 커졌을 때 특정 소수 다음에 어떤 소수가 나타날지 예측할 수 없다. 또한 소수를 만드는 공식을 찾기 위해 많은 수학자들이 노력을 기울였으나 아직까지 명쾌한 해답을 제시하지 못하고 있다.

지금까지 알려진 가장 긴 소수들의 등차수열은 1993년 Pritchard 에 의하여 발견된 11,410,337,850,553 + 4,609,098,694,200k (k =0, 1, ..., 21) 과 2003년 Frind에 의하여 발견된 376,859,931,192,959 + 18,549,279,769,020k (k =0, 1, ..., 21) 로 길이 22의 소수로 이루어진 등차수열이다.

소수의 성질
이렇듯 소수는 아직 인간이 정복하지 못한 산 중에 하나일 것이다. 고로, 우리가 알고 있는 소수의 성질이라고 함은 다음과 같은 것들이 있다.

1. 페르마 정리

m 이 소수이고 a, m 이 서로 소(relatively prime)이면
a^{φ (m)} ≡ 1 (mod m)
만약 m = p 소수 이면 φ (p) = p-1 이므로
a^{p-1} ≡ 1 (mod p)

[문제1]
Q. 2^123 mod 77
A. 77 = 7 × 11 이므로 φ(77) 를 다음과 같이 나타낼 수 있다.
φ(77) = (7-1)(11-1) = 60
(2^60)^2 × 2^3 mod 77
∴ 2^3 mod 77

2. 윌슨(Wilson) 의 정리
p가 소수일 필요 충분 조건은 (p-1)! ≡ -1 (mod p) 이다.

3. 2^a -1 이 소수이면 2^{a-1} (2^a -1) 은 완전수이다.

4. p 가 소수이고 a,b 가 자연수, p|(a^p - b^p) 이면 p^2|(a^p - b^p) 이다.

소수 판정법

1. 결정론적 (Deterministic)
n 을 소수라 할 때, √n 보다 작거나 같은 소수들 P1, P2, P3, ... 에 대하여 gcd(Pi, n) = 1 을 만족하는 지 확인 하는 방법으로 결과를 100%로 신뢰할 수 있지만 n 이 커질 수록 연산과정이 많아 비효율적이다.

2. 확률론적 (Probabilistic)
확률론적 소수 판정 알고리즘의 일반적인 구조는 다음과 같다.

bool IsPrimeNumber(int n)
{
  for(int i=1; i<t; t++)
  {
    int a = random(seed);
    if (f(n, a) == 0)
      return false;
  }
  return true;
}

• f(n,a) 은 n 이 소수임을 판단하는 함수이고 a 는 랜덤 값으로 f(n,a)≠0 일 경우 합성수이다.
• f(n, a) ≠ 0 은 "n 이 합성수임을 보여주는 증거" 라는 의미에서 n 에 대한 witness 라 한다.
• n 이 합성수 임에도 불구하고 f(n, a) = 0 을 만족시키는 a 를 "n 을 소수처럼 보이게 하는 거짓 증거"라는 의미에서 n 에 대한 liar 라 한다.

2.1 Fermat
Miller Rabin 판정법과 연산량이 비슷하지만 정확성이 떨어짐.

n 이 소수이고 a 가 1 과 n-1 사이의 정수일 때, a^(n-1) ≡ 1 (mod n) 을 만족
f(n, a) = a^(n-1) (mod n)

2.2 Solovay-Strassen
연산량이 높으며 Jacobi 심볼을 계산해야 하기 때문에 구현이 더 어려움

n 이 홀수인 소수, n 과 서로 소인 모든 정수 a 에 대하여
gcd(a,n) > 1, a^(n-1/2) not ≡ (a/n) mod n ==> Euler witness
gcd(a,n) = 1, a^(n-1/2) ≡ (a/n) mod n ==> Euler liar

2.3 Miller-Rabin
연산량이 적으며 구현이 용이하고 다른 두 판정법에 비해 정확성이 높음.

n - 홀수, 합성수, n - 1 = 2^s×r (r 은 홀수)
1 < a < n-1
a^r not ≡1 (mod n) 0 < j < s-1, a^(2jr) not ≡ -1 (mod n) ==> strong witness
a^r ≡ 1 (mod n) 0 < j < s-1, a^(2jr) ≡ -1 (mod n) ==> string pseudo prime