메르센 소수의 소수 판별

메르센 소수의 소수 판별 알고리즘은 일반적인 PS에서 출제되는 알고리즘은 아니지만.. 상당히 흥미로운 알고리즘이다.

엄청나게 큰 메르센 소수의 소수 판별을 빠르게 할 수 있고, 그래서 알려진 큰 소수 중 상위권은 항상 메르센 소수가 먹는다.

https://en.wikipedia.org/wiki/Largest_known_prime_number

(작성일 기준 1~7등이 모두 메르센 소수이다)

1. Trial Factoring

먼저 두 가지 정리를 미리 알아두고 가자.

정리 1. $2^p - 1$이 소수이면, p도 소수이다.

정리 2. $2^p - 1$의 인수는 모두 $2kp + 1$의 형태이며, 8로 나누었을 때 나머지가 1 또는 7이다.

정리 1과 2를 통해 $2^p - 1$의 인수가 될 만한 수의 후보를 추려낸 후, 다음과 같이 계산한다.

1. 후보 p가 존재.

2. p를 이진법의 형태로 바꾼다. 바꾼 후 나온 값을 추후에 계산할 때 사용한다.

3. 계산을 시작할 때의 초기 값은 1이다.

4. 주어진 값을 제곱한 뒤 이진법으로 표현한 앞자리부터 시작하여 숫자가 1이면 2를 곱하고 0이면 그대로 둔다.

5. 4에서 나온 값을 q로 나눈 나머지를 구한다.

6. 5에서 나온 나머지를 값으로 하여 4~5번 과정을 반복한다.

7. 최종 결과값이 1이면 q는 $2^p - 1$의 인수이다.

말로 하니 복잡하다. 예시를 보자.

(1) $2^{11} - 1$은 23으로 나누어떨어질까?

먼저 11을 이진수로 나타낸다. 1011이 된다.

그 후, 다음과 같은 과정을 거친다.

이진법	제곱 (초기값은 1)	곱 (이진법이 1이면 x2)	mod 23
1	1 * 1 = 1	1 * 2 = 2	2
0	2 * 2 = 4	-	4
1	4 * 4 = 16	16 * 2 = 32	9
1	9 * 9 = 81	81 * 2 = 162	1

최종 결과가 1이므로 $2^{11} - 1$은 23으로 나누어떨어진다.

수가 커지면 효율성이 커지는 것을 체감할 수 있다. 다음 예를 보자.

(2) $2^{1993} - 1$은 11959로 나누어떨어질까?

$2^{1993} - 1$을 구하는 것부터 숨이 턱 막힌다. 하지만 위의 방법을 사용하면 간편하다.

1993을 이진법으로 나타내면 11111001001이다.

이진법	제곱 (초기값은 1)	곱 (이진법이 1이면 x2)	mod 11959
1	1 * 1 = 1	1 * 2 = 2	2
1	2 * 2 = 4	4 * 2 = 8	8
1	8 * 8 = 64	64 * 2 = 128	128
1	128 * 128 = 16384	16384 * 2 = 32768	8850
1	8850 * 8850 = 78322500	78322500 * 2 = 156645000	6018
0	6018 * 6018 = 36216324	-	4472
0	4472 * 4472 = 19998784	-	3336
1	3336 * 3336 = 11128896	11128896 * 2 = 22257792	2093
0	2093 * 2093 = 4380649	-	3655
0	3655 * 3655 = 13359025	-	822
1	822 * 822 = 675684	675684 * 2 = 1351368	1

최종 결과가 1이므로 $2^{1993} - 1$은 11959로 나누어떨어진다.

위 방법의 장점은 사용하는 숫자의 범위가 작다는 점도 있다. 때문에 int, long long 등을 사용해도 어느 정도의 크기의 숫자까지는 사용 가능하다.

trial factoring은 사실 그냥 2^p - 1 mod q의 값을 구하는 과정이다.

때문에 특정 메르센 수가 어떤 범위에서 어떠한 수로 나누어떨어지거나, 약수를 가지지 않는다는 것은 보일 수 있지만 소수 판별을 하려면 다음에 소개된 LL이라는 방법을 사용해야 한다.

2. Lucas-Lehmer Primality Testing

알고리즘은 상당히 심플하다.

"$2^p - 1$이 소수인 것과 다음 수열 S의 p - 2번째 항이 0인 것은 동치이다."

수열은 다음과 같다.

$S_0 = 4, S_n = (S_{n - 1}^2 - 2) mod (2^p - 1)$

이 방법으로 2^7 - 1이 소수인지를 확인해보자.

S0 = 4

S1 = (4 * 4 - 2) mod 127 = 14

S2 = (14 * 14 - 2) mod 127 = 67

S3 = (67 * 67 - 2) mod 127 = 42

S4 = (42 * 42 - 2) mod 127 = 111

S5 = (111 * 111 - 2) mod 127 = 0

따라서 소수임을 알 수 있다.

보기에 느껴지겠지만, 연산량이 굉장히 많다.

p번 연산을 하고, $2^p - 1$정도의 수를 제곱하고 mod해주어야 하니 대충 추산해도 복잡도가 $O(p^3)$이다. 카라추바 알고리즘을 사용한다고 가정해도 $O(p^{2.585})$ 정도.

prime95 프로그램에서는 곱셈을 빨리 하기 위해 FFT를 사용한다고 한다. 자세한 건 나도 잘 모르니 생략.