저번에 쓴 글이 예상외로 인기가 많아서 더 쓴다.


저번 글은 고등학생들도 읽을수 있는 수준이였지만, 이번에는 좀 깊게 파고 들어가보자.


큰 소수를 찾는법을 요약하자면, 보통 큰 소수를 찾을려면 효율 좋은 소수판정법이 필수인데, 현재 결정론적 소수판정법으로는 128비트 이상을 조사할려면 택도 없다


현실적으로 계산이 힘드니 확률론적 소수판정법에 의존할 수 밖에 없다


확률론적 소수판정법을 쓸때 여러번 반복하면, 소수가 아닐 확률을 기하적으로 줄일 수 있다.


이번에는 이런 소수판정법 몇개를 소개하고, 각 특징을 알아보겠다. 그 전에 기초지식이 필요하다.


기초지식


-big O notation


O(p(n))은 앞에 있는 상수를 무시하겠다는 의미다. 대략적으로 알고리즘을 쓸때, 몇번의 계산이 필요한지 (시간복잡도), 저장공간이 얼마나 필요한지 (공간복잡도)를 나타낸다. 소수를 판정하는데 쓰는 연산에서 저장공간은 별로 잡아먹지 않기 때문에, 공간복잡도에 대한 이야기는 하지 않겠다.


알고리즘의 시간복잡도의 서열은 O((log n)^a), O(n^b), O(c^n) 순으로 나타난다. a b c는 임의의 상수이고, 각각 로그시간 다항시간 지수시간이라고 불린다


왼쪽으로 갈수록 신이 내려준 효율을 보여주고, 오른쪽으로 갈수록 개지랄맞은 효율을 보여준다. 모든 알고리즘은 왼쪽으로 가는걸 목표로 삼는다.



-Z_p


Z_p={0,1,2,... p-1} 이고 더하기와 곱하기는 결과값에 p를 나눈 나머지를 취하는것으로 정의하겠다. p는 소수다.


그러면 놀랍게도 Z_p에서 더하기 빼기 곱하기 나누기가 잘 정의된다.


쉬운 예시 2*4 = 1 (mod 7) ----> 2^(-1) = 4 (mod 7) 또는 4^(-1) = 2 (mod 7) 라고 쓸 수 있다.


Z_p에서 더하기의 역원은 -a = p-a (mod p)이고, 곱하기의 역원은 유클리드 호제법으로 O(log p)번의 곱셈으로 구할수 있다.




-Fast exponentiation 존나빠른 거듭제곱


x^m을 구하는 방법

1. m을 이진화한다.

2.x^(2^n) 을 차례로 구하면서, 이진화한 m에 1에 해당되는 부분만 곱한다.


예시. 5^100 을 구해보자. 100을 이진화하면 1100100 이다. (100=64+32+4)


제곱하면서, 5, 5^2, 5^4, ... ,5^64을 모두 알아낼 수 있다. 이진수를 거꾸로 읽으면서 1에 해당하는 부분만 곱해주면 된다.


5^4 * 5^32 * 5^64 = 5^100


O(log m)번의 곱셈만으로 계산할 수 있다.


우리는 Z_p안에서만 연산을 할 것이기 때문에, 곱하기를 할때 마다 (mod p)를 취해줄 것이다.


그리하면 지수가 아무리 커져도 연산과정의 모든 숫자들은 p보다 작기 때문에, 컴퓨터의 계산속도가 확 늘어난다거나 그러진 않는다.


5^100 (mod 101) = 5^4 (mod 101) * 5^32 (mod 101) * 5^64 (mod 101) = 19 * 52 * 78 (mod 101) = 1



-Fermat little theorem 페르마 소정리


p가 소수이면, Z_p에 있는 0이 아닌 모든 a에 대해 a^(p-1) = 1 (mod p)


역은 성립하지 않는다.


101은 소수이기 때문에, 5^100 = 1 (mod 101)이 성립했다. 



-legendere symbol 르장드르 기호


p는 홀수인 소수, a는 정수일때, (a/p)는 x^2 = a (mod p) 의 해가 Z_p 안에 존재하면 1 존재하지 않으면 -1이다. a가 p의 배수이면 0이다.


즉 a가 p에 대한 이차잉여이면 1, 아니면 -1


모조리 정수에 대해서만 이야기하니까 (a/p)를 헷갈려하지 말자.


예시. x^2=1 (mod p) 의 해가 1, -1 있으므로 (1/p) = 1



-jacobi symbol 야코비 기호


르장드르 기호를 모든 양의 홀수로 확장한 기호


귀찮으니까 사진

viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73ced81fa11d02831edca684dcd73c50d611ea9794e05f84ecbbd005b5837003d2350d109a947458c0d5f1b0a5133c4873c3c6164ff75e5

하지만 (a/n)=1이라고 해서 x^2=a (mod n)의 해가 존재하는것은 아니다.


오직 n자리에 임의의 양의 홀수를 놓아도 계산이 되도록 만든 개념이다.





Fermat primality test


페르마 소정리의 대우명제에 따라, a^(n-1) =/= 1 (mod n) 이면 n은 합성수이다.


이를 이용해서 페르마 테스트를 만들수 있다.


1.n과 n보다 작은 a를 뽑는다.

2.a^(n-1) (mod n)를 구한다. 만약 1이 안나오면 탈락. 1이 나오면 통과


시행을 r번 하면 시간복잡도는 O(r (log n)^2 log log n)이다.


오직 지수 연산만 하기 때문에, Fast-exponentiation의 총애를 받아 시행시간은 적은 편이다.


합성수인데 페르마테스트를 통과할 확률은 아무리 높아도 (phi(n)/ n)와 같다. phi(n) = n이하의 서로소의 개수


이 확률을 상한으로 가지고 있기 때문에, r번 반복하면 합성수가 통과할 확률은 (phi(n)/n)^r이하이고, 원하는만큼 시행해서 확률을 낮출수 있다.


근데 페르마 테스트에는 치명적인 결함이 있다. 이것때문에 페르마 테스트가 찐따취급을 벗어날 수 없다.


바로 카마이클 수의 존재로, 합성수 n과 a가 서로소이면 a^(n-1)=1 (mod n)이 성립하는 상당히 또라이 같은 수다.


다른 말로는 절대유사소수(absolute pseudoprime)라고 부르는데, 가장 대표적으로 561이 있다. 561=3*11*17


561은 3의 배수라서 서로소 개수가 320개정도 밖에 안되기 때문에 한번 시행의 통과 확률이 57%정도 된다.


근데 카마이클 수인 1729=7*13*19는 74%의 통과확률을 가졌다. 1729는 라마누잔 수이기도 하다.


카마이클수의 가장 작은 소수가 커지면 커질수록, 서로소의 비중이 더 높아지면서 통과확률이 높아진다.


그러니까 이 새끼들 때문에 강제적으로 페르마 테스트의 시행 횟수가 늘어나게 된다.


더욱이 골때리는것은, 카마이클 수가 무한하다는 것이다. 덕분에 페르마 테스트로 원하는만큼 확률을 낮추기 위해서는 시행횟수가 훨씬 많아진다.


혹시 페르마 테스트를 배우고 인류의 지성에 감탄했다면, 미안하지만 카마이클 수가 당신의 뒤통수를 후릴것이다.


하지만 걱정마라. 놈은 우리중에서 최약체니까.





Solovay-strassen primality test


이름부터 불쌍하게 솔로다.


오일러는 다음을 증명했다. p가 홀수인 소수이면, a^{(p-1)/2} = (a/p) (mod p). 이를 오일러 판정법이라고 한다,


우선 (a/p)를 구하는 법부터 설명해야하지 않을수 없겠다. 설마 x^2=a (mod p)를 만족하는 x가 있는지 조사할려고 생각했나?


우리가 찾는 p는 128비트가 넘기에 그런 짓을 하면 안된다. 만약 저런 생각을 했다면 스스로 뒤통수를 가격하도록하자.


이차상호법칙에 따르면, 홀수 m n에 대해, (m/n)*(n/m) = (-1)^{(m-1)(n-1)/4}이다. 그리고 (ab/n) = (a/n)(b/n)이고, (n+a/n)=(a/n)이다.


쉽게 말해, 위에있는놈 과 아래있는 놈을 뒤집을수 있고, 위에있는놈이 소인수 분해가 가능해지면 분해 할 수 있다.


계속 반복하면, 밑에있는놈이 3이하가 되도록 만들 수 있다. 야코비 기호에 대해 서술한것이니, m과 n이 소수인것은 걱정하지 않아도 된다.



예시. (12/175) = (2^2/175)(3/175) = (3/175) = -(175/3) = -(1/3) = -1.



보통 O((log n)^2)번의 곱셈만으로 야코비 기호를 계산할 수 있다.


이제 솔로베이 슈트라센 테스트(이하 SST)를 소개하겠다.


1.n과 n보다 작은 a를 뽑는다.

2.a^{(n-1)/2} (mod n)을 계산한다.

3.(a/n)을 계산한다.

4.둘이 비교한다. 같으면 통과, 다르면 탈락


시간복잡도는 r번 시행했을때 O(r (log n)^3 )이다.


한번 페르마 테스트에서 뒤통수를 맞아서 의심이 가는 친구들이 있을지도 모른다.


n과 서로소인 a에 대해서 저 식이 성립하는 또라이 같은 숫자가 존재하는거 아니야? 라고


하지만 안심해라. 그런 수는 존재하지 않는다.


더 나아가, 솔로베이와 슈트라센은 모든 합성수 n에 대해서 절반 이상의 a에 대해 저 식이 성립하지 않는다는것을 증명했다.


다시말해 SST는 어떤 합성수를 뽑아도 통과확률이 1/2 이하라는 것이다.


우효~~~~~ 통과확률의 상한 겟또다제~~~~~!!!


우리는 SST를 256번 통과한 수에 대해서, 이 수가 소수가 아닐 확률은 1/2^256 미만이라고 확실하게 말할수 있다.


시간복잡도는 페르마 보단 조금 높지만, 페르마처럼 쉽게 뚫리지는 않는다. 얼마나 멋있는 놈이란 말인가.





Miller-rabin primality test


미안하지만 지금부터 소개시키려는 소수판정법은 미친놈이다.


혹시 당신이 솔로베이슈트라센에게 반했다면, 밀러라빈이 당신을 강제로 빼앗을것이다.


이름부터 솔로인 이유가 있다. 미리 구질구질한 그에게 작별인사를 고하기를.


쉬운 예시부터 들겠다. a^12=1 (mod 13)이므로, a^6 (mod 13)은 1또는 -1이다.


a^6=1 (mod 13)인 녀석들만 생각한다면, a^3 (mod 13) 은 1 또는 -1이다.


식으로 써본다면, Z_13안에서, 0이 아닌 모든 a에 대해 a^3 = 1 (mod 13) 또는 a^(3* 2^r)= -1 (mod 13)이다. (r=0,1) 또한 a^12=1 (mod 13)


즉 이렇게 말할수 있다. p가 소수라면, p-1 = d * 2^s 라고 할때, Z_p안에 0이 아닌 모든 a에 대해 다음이 성립한다.



a^d =1 (mod p) or a^(d * 2^r) = -1 (mod p) (for r = 0,1,...,s-1), and a^(n-1)=1 (mod p)



이 정리를 이용해서 밀러라빈 테스트를 할 수 있다. 그런데 만약 자신이 똑똑하다면, 한번 밀러라빈 테스트를 추측하는게 어떨까? 30초간 생각해보도록.



1.n을 뽑고 n-1 = d * 2^s인 s와 d 구하기.

2.a를 뽑은다음 x = a^d (mod n)이 1 또는 -1인지 확인. 맞으면 통과

3.x^2 = -1 (mod n)인지 확인. 맞으면 통과 <------ s-1번 반복

4.x^2 = 1 (mod n) 인지 확인. 맞으면 통과 아니면 탈락


시간복잡도는 r번 시행했다면 O((r log n)^3)이다.


그런데 n이 소수라면 페르마 테스트보다 훨씬 빨리 통과시키기 때문에, 실질적으로 페르마 테스트보다 시간적으로 유리하다.


그럼 이제 밀러라빈 테스트를 통과할만한 위험한놈에 대해 알아보자.


밀러라빈 테스트를 뚫는 위험한놈은 강한유사소수(strong pseudoprime)이라 불린다. 이름만 들어도 강철문을 찢으면서 들어올법한 녀석이다.


특정한 b에 대해서, 밀러라빈 테스트를 통과한 강한유사소수는, b에대해서 페르마 테스트를 뚫는것은 물론이요, 솔로베이슈트라센 테스트도 뚫는다.


대신 그 역은 성립하지 않는다. 이는 즉 밀러라빈 테스트는 솔로베이 슈트라센보다 높은 정확성을 가진다는 뜻이다.


특정한 b에 대해 강한유사소수는 무한히 많이 존재한다. 어떤 b를 가지고 오더라도 항상 강한유사소수가 존재한다.


설마 밀러라빈도 패배하는 걸까? 당신은 또 이런 이상한 수에게 다시 뒤통수를 맞을것인가?


하지만 어림 반푼어치도 없다. 밀러와 라빈은 n이 강한유사소수라도, 밀러라빈을 통과할 a의 개수는 n/4이하라는것을 증명했다.


이는 다시말해 어떤 합성수를 가지고 오더라도, 밀러라빈 테스트의 통과확률은 1/4보다 작다는 것이다.


솔로뭐시기랑은 비교도 안되는 확률이다. 128번 밀러라빈테스트를 통과했으면, 소수가 아닐 확률은 1/2^256 미만이라고 말할수 있는것이다!


시간은 페르마보다 빠르면서 정확성은 솔로뭐시기보다 높다고? 미쳤네;;





다음에 설명할것은 작은 수에 대해서 소수인지 확정짓기 위해 밀러라빈 테스트의 최소 횟수이다..


n이 2037보다 작으면, 2에 대해서 확인만 하면 된다.


n이 1373653 보다 작으면, 2와 3에 대해서 확인만 하면 된다.


만약 100만이하의 소수를 뽑고 싶으면, 밀러라빈 알고리즘에 대해 2와 3만 체크하도록 코드를 짜는것이 효율적이다.


3억이하의 소수를 뽑고싶으면, 2 3 5 7에 대해서만 체크해도 된다. 개노가다로 얻은 결과이니 그냥 믿자.


그리고 여기서 리만가설의 깜짝출현이 있겠다. 모두 박수로 맞이하도록


"만약 리만가설이 참이라면, 2와 2*(ln n)^2 사이에 있는 모든 수가 밀러라빈테스트를 통과하면, n은 소수이다"


위 명제는 밀러가 증명했다. 리만가설이 참이면 소수를 빨리 찾네 뭐시기네 떠들던게 이 정리를 말한것이다.


리만 가설에 의존하는 다른 결정론적 소수판정법도 많이 있다.


만약 당신이 리만가설이 거짓임을 증명하고 싶다면, 2와 2 (ln n)^2 사이의 모든 수에 대한 강한유사소수를 노가다로 찾으면 되겠다.


아르노는 397자리 카마이클 수가 307보다 작은 수에 대해서 강한유사소수임을 1995년에 확인했다. 좀더 노오력하면 찾을수 있을지도?








이제 슬슬 마무리 지어야한다. 아쉽게도 밀러라빈 테스트보다 더 뛰어난 친구들이 많이 있다.


왜냐하면 미친놈 위에는 항상 더 미친놈이 있기 때문이다.


대신 그들은 이해하기가 더 난잡하다. 밀러 라빈 및 솔로베이 슈트라센 등등이 선녀로 보일만큼.


확률론적 소수판정법중에 Frobenius primality test는 밀러라빈 테스트에 3배정도 느리지만, 7배 높은 정확성을 가지고 있다.


baillie-PSW primality test는 이 테스트를 뚫는 합성수가 아직 발견 되지 않았다. 2^64 미만까지 조사한 결과이다.


결정론적 소수판정법중에는 AKS primality test가 가장 미친놈이다.


다른 가설에 의존하지 않고 시간복잡도를 O(n)안으로 밀어넣었다. 심지어 현재진행형으로 줄어들고 있다.


그리고 양자컴퓨팅이 가능하다면, 결정론적으로 시간복잡도 O((log n)^3)정도로 소수를 판정할수 있다.


만약 양자컴퓨팅이 가능해진 시대라면, 위에서 배운 애들은 다 역사속으로 묻힌다. 참으로 슬픈 일이 아닐수가 없다.