Primality Test (Monte Carlo)

  • How to tell is n is a prime?
    • Trying factoring doesn’t work
  • Fermat’s theorem
  • Is 8377 a prime?
    • If 8377 is a prime, then for any a, a^8376 == 1 mod 8377
    • If 8377 is not a prime, then for some a, a^8376 != 1 mod 8377
      • This is not a fact but a belief

머지 소트의 경우 정렬하는데 O(nlogn) 시간이 걸린다고 한다. 그런데 숫자의 개수는 똑같이 n개인데 한 입력은 숫자가 작고 다른 입력은 숫자들의 클 때, 두 입력을 정렬하는데 걸리는 시간이 같을까? 당연히 숫자가 큰 입력이 정렬하는데 더 시간이 오래 걸릴 것이다.

숫자가 작고 크고에 따라 정렬 시간이 분명히 다르다는 것이다. 물론 실제로 32비트 컴퓨터의 경우 32비트 이하의 숫자들은 한꺼번에 비교하기 때문에, 입력이 32비트의 이하의 숫자들로 구성된 경우에는 O(nlogn) 시간이 걸린다. 그러나 정확히 따지려면 원소들의 값도 고려해야 하기 때문에 O(nlogn)이 아니라 O(nlogn * s) (s: 입력에 주어진 두 숫자를 비교하는데 걸리는 시간)시간이 걸린다.

정리하면, 어떤 숫자와 관련해서 다를 때 숫자 자체가 시간 복잡도에 등장하면 실제로는 exponential time이 걸린다는 것이다.

그렇기 때문에 위로 다시 돌아와서 n이 소수인지 판별하기 위해 실제로 하나씩 나눠보는 것은 시간이 너무 오래 걸린다(O(n)).

1부터 int(sqrt(n))(a라 하자)까지만 체크하면 조금 더 빠른 O(sqrt(n)) 시간에 문제를 풀 수 있다. a까지만 체크해도 되는 이유는, 만약 b^2 == n인 b가 a+1와 n 사이에 존재한다면, n/b = c(c는 1보다 큰 자연수)가 성립한다. 즉, n = b*c이고 b < a이므로 c는 a보다 작다. 따라서 b가 존재한다면 c값이 1부터 a 사이에 있다는 것이다. 그래서 1부터 a까지의 범위만 체크해도 된다.

그러나 sqrt(n)도 여전히 크다. log(n)나 log(n^2) 정도는 돼야함.

페르마의 정리라는 것이 있다. 먼저 n=7인 경우를 보자.

a 1 2 3 4 5 6
a^1 % 7 1 2 3 4 5 6
a^2 % 7 1 4 2 2 4 1
a^3 % 7 1 1 6 1 6 6
a^4 % 7 1 2 4 4 2 1
a^5 % 7 1 4 5 2 3 6
a^6 % 7 1 1 1 1 1 1

n=6인 경우를 보자.

a 1 2 3 4 5
a^1 % 6 1 2 3 4 5
a^2 % 6 1 4 3 4 1
a^3 % 6 1 2 3 4 5
a^4 % 6 1 4 3 4 1
a^5 % 6 1 2 3 4 5

6은 소수가 아니고 7은 소수이다.

Fermat’s Theorem: n이 소수이면, a^(n-1) == 1 mod n이다. (1 < a < n)

Let’s do the test

  • a = 35 –> 35^8376 == 1 mod 8377
  • a = 186 –> 186^8376 == 1 mod 8377

  • Is 8377 a prime? Yes!

  • a = 35 –> 35^8373 == 2989 mod 8379
  • 8379 is not a prime, and 35 is a witness to non-primeness of 8379

Next Question

  • Does every nonprime have a witness?
    • Unfortunately no
    • Carmichael numbers are exceptions
    • Fortunately there is a test for Carmichael numbers.

Density of Witnesses

  • Having a witness is not enough
  • You need to have a lot of witnesses, because there seems to be no way of efficiently finding witnesses
  • Theorem: If there is one witness for n, then at least half of Zn* are witnesses (Zn*: 2, 3, ,,, n-1 정도라고 생각하면 됨. 실제로는 조금 다름)

Proof of Theorem

  • Let a be a witness for n
  • Let’s partition Zn* into A and B
    • A: witnesses, B: not witnesses
  • We can prove that |A|>|B|
    • Let’s consider aB
    • All members of aB are witnesses
    • If b∈B and c∈B and b!=c mod n, then ab!=ac mod n

Process of Finding a Random Prime

  • R1: Choose random n
    • Test is n is a Carmichael number
      • If so, go back to R1
  • R2: Choose random a (1<a<n)
    • Check if gcd(a, n) is 1
      • If not, then n is not a prime, so go back to R1
    • Check is a^(n-1) is 1 mod n
    • If so, go back go R2 for repeat test
    • If not, n is not a prime, so go back to R1

What is the Failure Probability

  • Nonprime n passes the test
  • If you repeat k times
  • The probability is at most 1/(2^k)
  • This is a very small probability. 100번만 해도 로또에 당첨될 확률보다 낮다.