2 PrimalityTest

소수 판별법

대표적인 방법

1부터 \(\sqrt{n}\) 자연수까지 모두 나눠본후 나눠지는 수가없을시에 그수는 소수이다. 2일때는 소수라 하고 짝수로 나누는 경우는 없애도 상관없다. \(O(\sqrt{n})\)

에라토스테네스의 체는 특정 \(n\)이 소수인지 판단하는것과는 무관하므로 제외한다..

이글의 연장선상인 얘기이다.

하나의 값 \(n\)을 놓고 이값이 소수인지 아닌지 보려면 현재 \(O(\sqrt{n})\)까지 만큼 비교해 보아야 확정적으로 알수있다.

엄청난 크기의 소수를 구하기 위해서 \(O(\sqrt{n})\)만큼의 시간도 길다고 판단해 이보다 좀더 효율적임을 위해서 결국 정확도를 조금 포기하고 확률적으로 소수인지 제대로 판단할 확률이 높은 알고리즘들이 나왔다.

의사소수 판정(pseudoprime test)

\(n\)이 소수일때 성립하는 페르마의 소정리를 판별방식으로 쓴다.

\(n\)과 서로소인 \(a\)에 대해서 \(a^{n-1}\) 을 \(n\)으로 나눈 나머지는 무조건 1이 된다. 소수일때는 무조건 성립하니까 이를 판별 방식으로 쓰자는것

따라서 어떤 값 \(n\)에 대해서 \(a^{n-1}\)을 \(n\)으로 나눈 나머지가 1인지 판별해보면 된다. 적당한 \(a\)를 뽑고, \(a^{n-1}\)을 고속 지수승 알고리즘을 통해 \(\log{n}\)번에 구할수있다.

1
2
3
4

PSEUDOPRIME(n)
    if MODULAR-EXPONENTIATION(2,n-1,n) != 1
        return COMPOSITE
    else return PRIME

이때 나오는 오진은 소수가 아닌데 \(a^{n-1}\)을 \(n\)으로 나눈 나머지가 1이 되는 경우이다. 이때 이 값을 카마이클 수(Carmichael number)라고 합니다 이 수의 특성도 재밌긴한데(사실 잘모름) 따로다루겠다.

카마이클수를 차례대로 나타내면

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973

굉장히 띄엄띄엄 있어서 오진율이 낮다.

밀러라빈소수 판별법(Miller-Rabin primality test)

앞의 의사소수 판정을 조금더 보완하기 위해서 검사를 더 촘촘히 하기로 해보자

다음 증명된 사실을 이용한다.

홀수인 소수 \(p\)와 정수 \(1 \le e\)에 대해서 \(\pmod{p^e}\)에서 \(x^2\)을 n으로 나눈 나머지가 1이 되는 x의 해는 무조건 \(1\),\(-1(=n-1)\)이다.

\(p^e \mid (x+1)(x-1)\)이 될때 \(p^e\)는 \((x-1)\),\((x+1)\)둘 중에 하나만이 될수가 있다. \(p^e\)가 \((x+1), (x-1)\)둘다 나눌수있을때에는 \(p^e\)가 \(2\)로 나누어지기 때문이다. 만약 \(p^e\)가 \(x+1\)을 나눌수있는 경우 \(x \equiv -1 \pmod{p^e}\), \(p^e\)가 \(x-1\)을 나눌수있는 경우 \(x \equiv 1 \pmod{p^e}\) 가된다.

이 정리의 대우에 따라서 1,-1을 근으로 가지지 않은 n은 합성수라고 판단 할 수 있다.

따라서 이 나머지가 1이되는데 x가 +-1인지를 살펴 보면된다.

임의의 a에 대해서 판단하는 방법은 다음과 같다.

  1. \(n-1\) 를 \(2^{t*u}\) (d는 홀수)로 나타낸다.

  2. \(a^u\)부터 \(a^{2^t*u}\)로 점점 제곱하면서 이 사이에 값이 1,n-1인데 그전의 값이 +-1이 아닌지 판별을 한다.

  3. 마지막에 \(a^{2^t*u}\) 값이 1인지 비교한다.(페르마 소정리)

예를 들어 카마이클 수는 561을 a = 2로 해서 구해보면 마지막에 \(a^(2^t*d)\)이 1이 되지만 제곱하기전의 값이 1이 아니라서 여기서 걸러지게 된다.

근데 이 판별이 결국 a에 따라 갈리게 된다. a값이 n에 대해서 제곱했을때 1이 되는 근이 아니어야 판별이 가능하다. 이는 합성수 n에 대한 다음 판별 방식으로 탐지되는 근이 \(1 \sim n-1\)사이에 최소 n/2가 존재한다

확실한건 a를 \(2 \sim n/2\)로 정하면 확실하게 나온다.

a를 촘촘하게 여러번 선택해서 판별하면 되는데 이러면 또 시간이 오래걸린다

따라서 탐지율이 a를 뽑는 횟수에 따라 다르다.

알고리즘 복잡도는 \(a\)를 반복해서 뽑는 \(k\)에 따라서 \(O(k \log^3 n)\)이다. 추가적으로 곱셈을 FFT로 처리했을때 \(O(k \log^2 n)\)까지 줄일 수 있다.

추가로 난제중 하나인 리만가설이 맞다면 \(2\log^2 n\) 개의 a로 검사를 했을때 소수일것이라고 판단이 되었을 경우 확정적으로 소수임이 드러나기때문에 \(O(\log^4 n)\)의 시간복잡도를 가지는 소수판별법이된다.

pollard’s rho algorithms

의사난수를 발생시켜 구하는 방법이다….

\[g(x) = x ^2-1 \pmod{n}\]

다음의 식을 사용해 반복적으로 \(g(x)\)를 만들어내고 \(y = g(g(x))\)로 \(\gcd(y-x, n)\)이 \(1,n\)인지 검사하는 방식이다. 그뒤 \(x = g(x)\)로 업데이트하여 반복한다.

Posted 2020-02-01
clrs