Lucas–Lehmer primality test
안녕하세요?
오늘은 $2^p - 1$꼴의 수(메르센 수)에 대해 소수 여부를 빠르게 판정할 수 있는 Lucas–Lehmer primality test에 대해 설명해보고자 합니다.
일반적인 소수 판정법은 시간이 굉장히 오래 소요됩니다. 가장 자명한 방법으로는 해당 숫자의 제곱근 이하의 소수들로 모두 나누어보는 방법이 있지만, 수가 어느 정도 커지면 사용하기 힘들어지게 됩니다.
더 큰 수에 대해 사용할 수 있는 알고리즘으로는 밀러-라빈 소수판정법이 있는데, 비결정론적인, 즉 확률에 의존한다는 단점이 있습니다.
하지만 특정 형태의 수에 대해서는, 굉장히 큰 숫자여도 해당 숫자가 소수인지를 결정론적으로 빠르게 판별할 수 있습니다. 메르센 수($2^p - 1$ 형태의 소수)가 그 중 하나이며, Lucas–Lehmer primality test를 사용하면 메르센 수가 소수인지 아닌지 아주 간단하게 확인할 수 있습니다.
실제로 현재 알려진 가장 큰 소수들 중에는 메르센 소수가 대부분입니다. 알려진 소수의 리스트를 확인해보면, 상위 13개의 소수 중 12개가 메르센 소수임을 확인할 수 있습니다.
메르센 소수가 가지는 또 다른 재미있는 성질로, 메르센 소수를 알면 완전수(자기 자신을 제외한 약수의 합이 자기 자신이 되는 수)를 쉽게 만들어낼 수 있다는 점이 있습니다.
$M_p = 2^p - 1$가 메르센 소수라 할 때, $M_p 2 ^ {p - 1}$의 자기 자신을 제외한 약수의 합을 구해봅시다.
자기 자신을 제외한 약수의 합은 $(1 + M_p) \times (1 + 2^1 + 2^2 + … + 2^{p - 1}) - M_p 2^ {p - 1} \ = (1 + M_p) \times (2^p - 1) - M_p 2^{p - 1} = 2^p - 1 - M_p + M_p 2^{p - 1} = M_p 2^{p - 1}$이 되어, 자기 자신이 되는 것을 알 수 있습니다. 다시 말해, $M_p 2 ^ {p - 1}$는 항상 완전수가 되게 됩니다.
그렇다면 과연 메르센 소수의 소수 판별은 어떻게 진행될까요?
Lucas–Lehmer primality test
Lucas–Lehmer primality test는 메르센 수가 소수인지를 판별해주는 알고리즘으로, 그 과정이 매우 간단합니다.
$M_p = 2^p - 1$이라고 할 때, 다음이 성립합니다.
$s_0 = 4$, $s_{i + 1} = (s_{i}^{2} - 2) % M_p$라 할 때, $s_{p - 2} \equiv 0 \pmod{M_p}$와 $M_p$가 소수인 것은 동치이다.
즉, 점화식을 p - 2번 계산한 후 결과를 확인할 경우 빠르게 소수 여부를 판별하는 것이 가능합니다. 코드로 작성해도 굉장히 간단합니다.
def isMersennePrime(p):
M_p = 2 ** p - 1
s = 4
for i in range(p - 2):
s = (s * s - 2) % M_p
return s == 0
몇 가지 최적화 기법을 적용하면 속도를 더 줄일 수 있지만, 간단하게 작성한 6줄의 python 코드만으로 3376자리수인 $2 ^ {11213} - 1$과 같은 수의 소수 여부를 5초 내외로 판별할 수 있습니다.
Lucas–Lehmer primality test의 시간 복잡도는 어떻게 될까요?
수행해야 하는 연산에는 크게 s * s를 계산하는 것과, 이를 $M_p$로 나눈 나머지를 구하는 것이 있습니다. 이러한 연산을 총 p - 2번 수행해야 합니다.
먼저 s * s를 계산하는 것을 살펴보겠습니다. s는 $M_p$보다 작기 때문에, 최대 p비트를 가지는 수가 됩니다. p비트의 수 2개를 곱하는 데 걸리는 시간은 일반적으로 $O(p^3)$이지만, FFT를 사용하면 $O(p \log{p} \log{\log{p}})$로 줄이는 것이 가능합니다.
$M_p$로 나눈 나머지를 구하는 것은 훨씬 더 복잡해 보이지만, 굉장히 흥미로운 계산 트릭을 사용하면 $O(p)$ 시간 내에 완료할 수 있습니다.
$k \equiv ((k \% 2^p) + (k » p)) \pmod{2^p - 1}$이 성립하기 때문에, 최대 3번의 $O(p)$ 계산으로 이를 구해낼 수 있습니다.
따라서 Lucas–Lehmer primality test의 시간 복잡도는 $O(p^2 \log{p} \log{\log{p}})$가 됩니다.
아래부터는 Lucas–Lehmer primality test가 왜 성립하는지, 그 증명을 한 번 알아보겠습니다.
Lucas–Lehmer primality test의 증명
Lucas–Lehmer primality test를 증명하기 위해서는, $s_{p - 2} \equiv 0 \pmod{M_p}$일 때 $M_p$가 소수인 것과, $M_p$가 소수일 때 $s_{p - 2} \equiv 0 \pmod{M_p}$인 것 둘을 증명하면 됩니다.
$s_{p - 2} \equiv 0 \pmod{M_p} \Longrightarrow$ $M_p$가 소수
먼저, $\omega = 2 + \sqrt{3}$, $\bar{\omega} = 2 - \sqrt{3}$라고 정의를 합시다. 이 때, $s_{i} = \omega^{2^i} + \bar{\omega}^{2^i}$임이 성립합니다.
이제 $s_{p - 2} \equiv 0 \pmod{M_p}$일 때, $M_p$가 소수인 것을 보일 차례입니다. 귀류법을 사용하겠습니다.
$s_{p - 2} \equiv 0 \pmod{M_p}$이므로, $\omega^{2^{p - 2}} + \bar{\omega}^{2^{p - 2}} = kM_p$를 만족하는 정수 k가 존재하게 됩니다.
양변에 $\omega^{2^{p - 2}}$를 곱한 후 정리하면, $\omega^{2^{p - 1}} = kM_p\omega^{2^{p - 2}} - 1$을 만족하게 됩니다.
이 때 $M_p$가 소수가 아니라고 가정을 해 보겠습니다. $M_p$의 가장 작은 소인수를 q라고 합시다. 이 때 q는 2보다 홀수입니다.
이제 집합 X를 다음과 같이 정의합니다. $X = \{ a + b\sqrt{3} \mid 0 \leq a, b < q \}$ 집합 X의 원소의 수는 $q^2$개입니다.
위 집합의 원소들은 곱셈에 대해 닫혀있습니다. 또한, $\omega$와 $\bar{\omega}$ 또한 집합 X의 원소입니다.
이제 집합 X의 부분집합인 집합 $X’$를 집합 X 중 곱에 대한 역원을 가진 원소들의 집합으로 정의하겠습니다. 0은 집합 X의 원소이지만 역원이 없으므로 X’의 원소가 아니고, 따라서 X’의 크기는 $q^2 - 1$보다 같거나 작습니다.
$kM_p \omega^{2^{p - 2}} = 0$는 X의 원소인데 $M_p \equiv 0 \pmod{q}$이므로 $kM_p \omega^{2^{p - 2}} = 0$이 됩니다. 따라서 $\omega^{2^{p - 1}} = -1$이며, 제곱하면 $\omega^{2^p} = 1$이 됩니다.
$\omega^{k} = 1$이 되는 가장 작은 k가 있다고 할 때, k는 $2^p$의 약수여야 합니다. 하지만 $\omega^{2^{p - 1}} = -1$이므로, k는 $2^p$이 됨을 알 수 있습니다.
즉, $\omega^1, \omega^2, …, \omega^{2^p}$이 모두 X’의 원소가 됩니다. 따라서, X’의 크기는 $2^p$보다 같거나 큽니다. 즉, $2^p <= |X’| < q^2$이 성립합니다.
한편, q는 $M_p$의 가장 작은 소인수이므로 $q^2 <= M_p = 2^p - 1$이 성립해야 합니다. 위 식과 모순이 되기 때문에, $M_p$는 소수입니다.
$M_p$가 소수 $\Longleftarrow s_{p - 2} \equiv 0 \pmod{M_p}$
반대 방향을 보이는 것은 조금 더 간단합니다. 다만 대수학적 지식이 조금 필요합니다.
소수 q와 서로소인 수 a가 있을 때, $a^{\frac{q-1}{2}} \equiv \pm 1$이 성립합니다.
이제 $Q = 2^p - 1$이라 두고, $(1 + \sqrt{3})^{Q} \pmod{Q}$를 봅시다.
Q가 소수이므로 이항 전개에서 가운데의 항들은 모두 사라지고, 양 끝의 항들만 남게 됩니다. 따라서 $(1 + \sqrt{3})^{Q} \equiv 1 + \sqrt{3}^{Q} \pmod{Q}$가 성립합니다.
$1 + \sqrt{3}^{Q} = 1 + 3^{\frac{Q - 1}{2}}\sqrt{3}$인데, 이 때 $3^{\frac{Q - 1}{2}} \equiv \pm 1 \pmod{Q}$이며, 특히 law of quadratic reciprocity에 따라, $3^{\frac{Q - 1}{2}} \equiv -1 \pmod{Q}$이 성립합니다.
따라서 대입하면 $(1 + \sqrt{3})^{Q} \equiv 1 - \sqrt{3} \pmod{Q}$이 성립하며, 양쪽에 $1 + \sqrt{3}$을 곱하면 $(1 + \sqrt{3})^{Q+1} \equiv -2 \pmod{Q}$가 됩니다.
$(1 + \sqrt{3})^2 = 2\omega$이므로, 대입해서 정리하면 $2 * 2^{\frac{Q - 1}{2}} * \omega^{\frac{Q+1}{2}} \equiv -2 \pmod{Q}$가 됩니다.
우리는 $2^{\frac{Q - 1}{2}} \equiv 1 \pmod{Q}$임을 알고 있으므로, 대입 후 정리하면 최종적으로 $\omega^{\frac{Q+1}{2}} \equiv -1 \pmod{Q}$가 성립합니다.
Q를 대입한 뒤 정리하면 $\omega^{2^{p-1}} = \omega^{2^{p-2}} * \omega^{2^{p-2}} \equiv -1 \pmod{Q}$이며, 양변에 $\bar{\omega}^{2^{p - 2}}$를 곱하면 최종적으로 $\omega^{2^{p-2}} +\bar{\omega}^{2^{p-2}} \equiv 0 \pmod{Q}$라는 식을 얻게 됩니다.
따라서 증명이 완료되었습니다.
Reference
다음은 글을 쓸 때 참고한 사이트입니다.