수학이론
소수 판별
existence_of_nothing
2022. 7. 30. 17:18
어떤 수 n이 주어졌다고 하자. 이것이 소수인지 어떻게 알 수 있을까? 암호학에서 아주 큰 수를 소인수 분해하는 것은 중요하다. N=n1n2.. np로 나누는 단계를 언제까지 진행하다 멈춰야 하는지를 알아야 효율적인 소인수분해가 가능하다. 이 문제는 그 문제의 단순함에 비해서 풀기가 쉽지 않고, 대부분 확률적 복잡도에 기반한 알고리듬들을 사용하고 있다.
타원곡선이론으로 이 문제를 해결하는 것이 1993년 Atkin-Morain에 의해서 발표된 ECPP (elliptic curve primality proof) 알고리즘이다. 인수분해 문제에 타원곡선을 적용한 최초의 수학자는 독일 수학자 HW Lenstra (1985)이다. ECPP는 현재까지 알려진 소수 테스트 방법중 가장 속도가 빨라서 O(log(n)^5)안에 연산을 마치며, 조금 변형된 방법으로는 O(log(n)^4)에 수행 가능하다. 2020년까지 밝혀진 가장 큰 소수는 40,000자리의 partition number p(1289944341)로 알려져 있다.
이틀전에 낸 어떤 수 n을 n보다 작은 수들의 합으로 기술하는 방법이 몇가지인가를 묻는 문제가 partion number problem이다. Partition number는 입자물리에서 종종 사용하는 young table을 나열하는 방법이 몇가지인지를 묻는다. 이것은 n개의 박스를 위쪽 box의 개수가 아랫쪽 박스보다 같거나 많게 나열할 수 있는 방법의 수 p(n)을 의미하며 아래 그림에서 보듯이 p(1)~p(8)은 (1,2,3,5,7,11,15,22)에 해당한다. 아래그림을 box 대신 dot 점으로 그리면 그것을 Ferrers diagram이라고 수학자들이 부른다.
타원곡선이론으로 이 문제를 해결하는 것이 1993년 Atkin-Morain에 의해서 발표된 ECPP (elliptic curve primality proof) 알고리즘이다. 인수분해 문제에 타원곡선을 적용한 최초의 수학자는 독일 수학자 HW Lenstra (1985)이다. ECPP는 현재까지 알려진 소수 테스트 방법중 가장 속도가 빨라서 O(log(n)^5)안에 연산을 마치며, 조금 변형된 방법으로는 O(log(n)^4)에 수행 가능하다. 2020년까지 밝혀진 가장 큰 소수는 40,000자리의 partition number p(1289944341)로 알려져 있다.
이틀전에 낸 어떤 수 n을 n보다 작은 수들의 합으로 기술하는 방법이 몇가지인가를 묻는 문제가 partion number problem이다. Partition number는 입자물리에서 종종 사용하는 young table을 나열하는 방법이 몇가지인지를 묻는다. 이것은 n개의 박스를 위쪽 box의 개수가 아랫쪽 박스보다 같거나 많게 나열할 수 있는 방법의 수 p(n)을 의미하며 아래 그림에서 보듯이 p(1)~p(8)은 (1,2,3,5,7,11,15,22)에 해당한다. 아래그림을 box 대신 dot 점으로 그리면 그것을 Ferrers diagram이라고 수학자들이 부른다.
이 문제의 답은 아래와 같은 예쁜 generating function p(n)으로 주어져 있으며, 근사적으로 구하는 공식도 주어져 있다. 1918년 Hardy와 Ramanujan이 찾아냈다고 한다. 아래에서 보듯이 p(n)에는 내재된 규칙 때문에 p(n) mod p는 여러 독특한 성질들을 갖는데, Ramanujan이 이와 관련된 여러 흥미있는 규칙들을 다수 찾아낸다. 아래 공식을 그냥 유추하기는 쉽지는 않지만, 답을 안다면 왜 그것이 답이 되는지는 짐작할 수 있다. 예를 들어 (1+x+x^2+…) (1+x^2+x^4+…) 을 곱하는 것을, 왼쪽은 그 숫자를 표현하는데 사용한 1의 가능한 개수를, 오른쪽은 2의 개수를 나타낸다고 생각할 수 있다. 각각에서 한 항씩 뽑을 때마다 1과 2의 가능한 개수들이 모두 나열된다. 이 것을 임의의 정수의 조합으로 확장하면 아래와 같은 생성식을 만들 수 있다. 오일러의 업적이다.
만약 n이 큰 경우, 그 값이 엄청나게 증가해서 p(10000)의 경우 이미 10^106을 넘어선다. 앞서 얘기한데로 4만자리의 큰 수 p(1289944341)이 소수라는 것을 ECPP 방법으로 찾은 것이 최고 기록이다. P(n)이 짝수인지 홀수인지를 알아내는 방법조차도 여전히 open problem으로 남아있다.
======================
소수를 찾는 많은 방법들은 Fermat의 little theorem을 기반으로 하고 있다. 즉, a^n=a (mod n) 이 소수 a에 대해서는 성립한다. 반대로 이것은 어떤 수 a가 소수인지를 판별하는데도 사용된다. 예를 들어 2^91=37 (mod 91) 이므로 91은 소수가 아니고, 2^341=2 (mod 341) 이므로 341은 소수일 것 같지만, 3^341=168 (mod 341)이므로 여전히 소수가 아니다. 즉, n이 소수이면 a^n=a이지만, a^n=a가 특정한 a에 대해서 성립한다면 이것이 n이 소수라는 얘기는 아니다. 그러나, 1~n-1까지의 모든 수 a에 대해서 성립한다면, 이것은 n이 소수라는 얘기를 의미할까? 불행히도 대답은 여전히 no이다.
어떤 자연수 n이 있을 때, 모든 자연수에 대해서 a^n=a mod n이 되는 수를 카마이클 수 (Carmichael number)라고 부른다. 예를 들면 561, 1105 같은 수들이 그러한 수이다. 그러한 수들이 몇 개안된다면 실용적으로 큰 문제가 안될 것이다. 과연 그러한 수의 개수는 무한개일까? 아니면 유한개일까? 이것은 문제는 쉽지만 해결에는 80년이 걸려서 1994년 Alford-Granville-Pomerance에 의해서 그 개수가 불행히도 무한개임이 증명되었다. 따라서, 페르마의 소정리를 바로 소수 판별에 적용하기는 무리이다. 그러나, 다행스럽게도 우리에게는 다른 무기가 있다.
오일러 torsion function pi(n) 에 대해서 pi(n)=n-1 이라면 n은 소수이다. N이 소수이면 당연히 pi(n)은 n가 서로소인 정수의 개수이므로 n-1 이고, 그 반대로 pi(n)=n-1 이라면 n은 소수일 때 밖에 없다.
(증명: 만약 n=p^k라면, pi(p^k)=p^k-p^(k-1)<p^k-1=n-1
만약 n=ab (gcd(a,b)=1)이라면 pi(n)=pi(a)pi(b)<(a-1)(b-1)<ab-1=n-1)
따라서, pi(n)=n-1인지 조사하면 쉽게 n이 소수인지 아닌지를 알 수 있을텐데, 불행히도 pi(n)의 계산이 녹록치 않다는 사실이다. 즉, 이 방법을 그대로 적용하는 것은 자살행위이다.
======================
소수를 찾는 많은 방법들은 Fermat의 little theorem을 기반으로 하고 있다. 즉, a^n=a (mod n) 이 소수 a에 대해서는 성립한다. 반대로 이것은 어떤 수 a가 소수인지를 판별하는데도 사용된다. 예를 들어 2^91=37 (mod 91) 이므로 91은 소수가 아니고, 2^341=2 (mod 341) 이므로 341은 소수일 것 같지만, 3^341=168 (mod 341)이므로 여전히 소수가 아니다. 즉, n이 소수이면 a^n=a이지만, a^n=a가 특정한 a에 대해서 성립한다면 이것이 n이 소수라는 얘기는 아니다. 그러나, 1~n-1까지의 모든 수 a에 대해서 성립한다면, 이것은 n이 소수라는 얘기를 의미할까? 불행히도 대답은 여전히 no이다.
어떤 자연수 n이 있을 때, 모든 자연수에 대해서 a^n=a mod n이 되는 수를 카마이클 수 (Carmichael number)라고 부른다. 예를 들면 561, 1105 같은 수들이 그러한 수이다. 그러한 수들이 몇 개안된다면 실용적으로 큰 문제가 안될 것이다. 과연 그러한 수의 개수는 무한개일까? 아니면 유한개일까? 이것은 문제는 쉽지만 해결에는 80년이 걸려서 1994년 Alford-Granville-Pomerance에 의해서 그 개수가 불행히도 무한개임이 증명되었다. 따라서, 페르마의 소정리를 바로 소수 판별에 적용하기는 무리이다. 그러나, 다행스럽게도 우리에게는 다른 무기가 있다.
오일러 torsion function pi(n) 에 대해서 pi(n)=n-1 이라면 n은 소수이다. N이 소수이면 당연히 pi(n)은 n가 서로소인 정수의 개수이므로 n-1 이고, 그 반대로 pi(n)=n-1 이라면 n은 소수일 때 밖에 없다.
(증명: 만약 n=p^k라면, pi(p^k)=p^k-p^(k-1)<p^k-1=n-1
만약 n=ab (gcd(a,b)=1)이라면 pi(n)=pi(a)pi(b)<(a-1)(b-1)<ab-1=n-1)
따라서, pi(n)=n-1인지 조사하면 쉽게 n이 소수인지 아닌지를 알 수 있을텐데, 불행히도 pi(n)의 계산이 녹록치 않다는 사실이다. 즉, 이 방법을 그대로 적용하는 것은 자살행위이다.
만약 p가 2^st+1인데 소수라면 위의 (1),(2)중 단 하나만을 만족시켜야 한다. 만약 두 조건을 모두 만족시키면 그것은 소수가 아니라는 얘기이다. 이제 어떤 수 N=2^st+1인 수가 주어진 경우, 1~N-1 인 witness number a가 (1)과 (2)를 동시에 만족하면 그 수 N은 소수가 아니다. 문제는 random하게 witness a를 선택할 경우에 그 수가 witness가 될 가능성이 높으냐이다. 그것에 대해서 Monier-Robin theorem의 두 수학자가 1980년에 그냥 눈 감고 뽑아도 그 수가 witness일 확률이 3/4를 넘을 것이라고 증명하였다. 다행이다. 이 사실에 의거한 Miller-Rabin 소수 검증 알고리즘을 살펴보면 아래와 같다.
이제 위의 M-R 테스트로 검증하면 어떤 수가 소수인지 아닌지를 출력하는데, 문제는 저렇게 여러 번 테스트한 witness 모두에 대해서 검증을 통과하였다고 해서 그 수 n이 반드시 소수는 아니라는 것이다. 즉, 소수일 확률이 (witness 수가 충분하다면) 높다는 것이지, 100% 확실하지는 않은 probabilistic algorithm이라는 것이다. 1993년 Damgard-Landrock-Pomerance는 M-R 알고리듬의 오류 확률을 다음과 같이 계산한다. 충분히 큰 수라면 잘못 판정할 확률이 exponential 하게 떨어지지만 당연히 100% 확신은 할 수 없다.
======================
타원곡선이론을 소수 검증에 사용하는 것은 비교적 최근에 제안된 내용인데, 이것은 다음과 같은 Goldwasser-Kilian 이론에 근거하고 있다. P=(x:y:z) 가 elliptic curve E/Q 상의 점이라고 하자. 타원곡선은 2차원 평면 상의 곡선이지만, 이것을 3차원 투영 공간의 곡선으로 보면 (x,y,z)라는 세 변수가 사용된다. z=0 (mod n)인 경우, nonzero (mod n)인 경우가 있고, 후자의 경우 중 특히 gcd(z,n)=1인 경우를 strongly nonzero 라고 하자. 만약 P 가 strongly nonero (mod n)이라면, P는 pn인 모든 자연수와도 nonzero 이다.
이제 어떤 수 N이 소수인지를 판정하려면, 위의 조건을 만족하는 M을 찾아서 M을 소인수 분해하여 모든 소수들에 대해서 (M/l)P가 0인지 아닌지를 조사하면 된다. 그런데, 이를 위해서는 먼저 큰 수 M을 소인수 분해해야 하며, 이 과정에서 M의 인수 q들이 소수인지를 먼저 판정해야 하는 문제에 부딪힌다. 즉, 어떤 수, N이 소수인지를 판정하기위하여, M의 인자들이 소수인지 아닌지를 먼저 판정해야 한다. 이를 위해 primality certificate라는 개념이 필요하다.
C=(p,A,B,x1,y1,q) 에서 P=(x1:y1:1)이 유리계수 타원곡선 E:y^2=x^3+Ax+B 위의 점이고, p는 gcd(p,discriminant)이고, q>(p^(1/4)+1) 이고 qP=0(mod p) 일때, C를 primality certificate라고 부른다.
위의 G-K 정리에 따라 만약 q가 소수라면 p도 소수이다. 즉, 어떤 수 p의 소수성을 판정하기 위하여 p보다 작은 certificate를 찾으면 이제, q의 소수성을 판정하는 문제로 환원되고, 이 과정을 반복하면, 결국은 소수인지를 충분히 판정할 수 있는 작은 q의 소수성을 판정할 수 있는 문제로 된다는 것이 ECPP 알고리듬의 핵심이다. 전체 알고리듬은 아래와 같이 좀 복잡하다.
C=(p,A,B,x1,y1,q) 에서 P=(x1:y1:1)이 유리계수 타원곡선 E:y^2=x^3+Ax+B 위의 점이고, p는 gcd(p,discriminant)이고, q>(p^(1/4)+1) 이고 qP=0(mod p) 일때, C를 primality certificate라고 부른다.
위의 G-K 정리에 따라 만약 q가 소수라면 p도 소수이다. 즉, 어떤 수 p의 소수성을 판정하기 위하여 p보다 작은 certificate를 찾으면 이제, q의 소수성을 판정하는 문제로 환원되고, 이 과정을 반복하면, 결국은 소수인지를 충분히 판정할 수 있는 작은 q의 소수성을 판정할 수 있는 문제로 된다는 것이 ECPP 알고리듬의 핵심이다. 전체 알고리듬은 아래와 같이 좀 복잡하다.
오늘날 소수인지 판별하는 가장 빠른 기법은 Atkin Morain 이 1993년 제안한 알고리듬과 이를 개량한 알고리듬으로 알려져 있으며 대략 O(n^4), n=log(p)으로 알려진 확률적 방법이다. 비교적 최근인 2002년 인도 공과대학 칸푸르의 컴퓨터 과학자인, Agrawal, Kaya, Saxena가 O(n^6) 정도의 복잡도를 가졌지만, deterministic polynomial time 알고리듬(AKS 알고리듬)을 개발하였으며, 이들은 그 공로로 2006년 괴델상, 풀커슨상등 각종 상들을 수상한다.
반응형