TOC

1. 페르마 소수 판별법
2. 밀러-라빈 소수 판별법
   1. 결정론적인 버전
3. 참고 문헌

페르마 소수 판별법

페르마의 소정리를 이용하여 소수를 판별하는 것이다. 페르마의 소정리에 대해 알아보자.

페르마의 소정리에 대한 증명은 여럿 있지만, 그 중 완전한 잉여류 집합을 활용한 증명을 소개하겠다.

범위의 정수 를 선택해서 의 소수성 판별에 사용할 수 있을 것이다. 하지만, 치명적인 문제가 있다. 이면 가 소수가 아님을 알 수 있지만, 페르마의 소정리를 만족한다고 해서 소수라고 단정할 수 없다. 따라서, 어떤 정수 에 대해 를 만족하는 정수 를 유사소수_pseudoprime라고 한다. 그렇다면 가능한 모든 에 대해 만족하는지 확인해보면 되지 않을까? 아쉽게도 모든 정수 에 대해 페르마의 소정리를 만족하지만 소수가 아닌 가 있다. 이를 카마이클 수_{Carmichael number}라고 한다.

밀러-라빈 소수 판별법

밀러-라빈 소수 판별법은 페르마 판별법을 확장한 것이다.

홀수 에 대해 은 짝수이므로, 2의 거듭제곱으로 묶을 수 있다. 따라서, 다음과 같이 적을 수 있다.

이는 페르마의 소정리의 합동식을 인수분해할 수 있도록 한다.

이 소수라면 위 인수 중 하나가 으로 나누어떨어져야 할 것이다. 밀러-라빈 판별법은 바로 이 점을 검증하는 것이며, 따라서 페르마 판별법보다 더 엄밀하다. 인 밑 에 대해

이나 인 에 대해

가 성립하는 지를 확인한다.

어떤 밑 가 위 합동식 중 하나라도 만족하지 않는다면 이 합성수라는 증거를 찾은 것이다.

페르마 판별법와 유사하게, 합성수에 대해 위의 식들이 모두 만족할 가능성도 있다. 이 경우 해당 밑 를 강한 거짓 증거_{strong liar}라고 부른다. 즉, 밑 가 위 식 중 하나를 만족한다고 해서 이 반드시 소수임을 밝힌 것은 아니며, 단지 이 높은 확률로 소수임을 의미한다. 하지만 카마이클 수와 같이 모든 비자명한 밑수가 거짓 증거인 경우는 존재하지 않으며, 실제로 최대 의 밑만이 강한 거짓 증거가 될 수 있음을 보일 수 있다. 만약 이 합성수라면, 무작위로 선택한 밑수가 합성수를 증명할 확률은 최소 75%이다. 서로 다른 무작위 밑수를 선택하여 여러 번 반복하면 해당 수가 소수인지 합성수인지를 매우 높은 확률로 판별할 수 있다.

다음은 64비트 정수에 대해 밀러-라빈 소수 판별법을 구현한 것이다.

using u64 = uint64_t;
using u128 = __uint128_t;

u64 binpower(u64 base, u64 e, u64 mod) {
  u64 result = 1;
  base %= mod;
  while (e) {
    if (e & 1)
      result = (u128)result * base % mod;
    base = (u128)base * base % mod;
    e >>= 1;
  }
  return result;
}

bool check_composite(u64 n, u64 a, u64 d, int s) {
  u64 x = binpower(a, d, n);
  if (x == 1 || x == n - 1)
    return false;
  for (int r = 1; r < s; r++) {
    x = (u128)x * x % n;
    if (x == n - 1)
      return false;
  }
  return true;
};

bool MillerRabin(u64 n, int iter=5) { // n이 아마도 소수이면 true, 아니면 false를 반환.
  if (n < 4)
    return n == 2 || n == 3;

  int s = 0;
  u64 d = n - 1;
  while ((d & 1) == 0) {
    d >>= 1;
    s++;
  }

  for (int i = 0; i < iter; i++) {
    int a = 2 + rand() % (n - 3);
    if (check_composite(n, a, d, s))
      return false;
  }
  return true;
}

밀러-라빈 테스트를 수행하기 전에, 먼저 몇 개의 소수들이 약수인지 추가로 검사할 수 있다. 대부분의 합성수는 매우 작은 소인수를 가지므로, 이를 통해 테스트 속도를 크게 향상시킬 수 있다. 예를 들어, 전체 수의 는 보다 작은 소인수를 갖는다.

bool MillerRabin(u64 n) { // n이 소수이면 true, 아니면 false를 반환.
  if (n < 2)
    return false;

  int r = 0;
  u64 d = n - 1;
  while ((d & 1) == 0) {
    d >>= 1;
    r++;
  }

  for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
    if (n == a)
      return true;
    if (check_composite(n, a, d, r))
      return false;
  }
  return true;
}

참고 문헌

1. jakobkogler, et al. Primality tests. cp-algorithms.com.