인도의 세 컴퓨터 과학자들이 소수를 판정하는 다항 시간 알고리즘을 찾아냈다. 지금까지 널리 쓰이는 소수판정 알고리즘은 확률적인 방법이었다. 전혀 새롭고 놀랍도록 아름다운 증명이라고 한다.
see also:
Like other modern tests for primes, the new algorithm is based on a number-theoretic fact that Pierre de Fermat (of Last Theorem fame) discovered in the 17th century: If n is prime, then it evenly divides a^n - a for any number a. Fermat's test makes it possible to prove that a number n is not prime without finding any of its factors. For example, 2^9 - 2 = 510, which is not divisible evenly by 9. Hence, 9 cannot be a prime number.
![[http]](/ns/imgs/http.png)
뉴욕타임즈 기사 등록을 하고 로그인을 해야 볼 수 있음
- 논문 pdf/ps
- Science Magazine 기사
- PRIMES is in P: A Breakthrough for Everyman : AMS Notices, 2003년 5월호
Like other modern tests for primes, the new algorithm is based on a number-theoretic fact that Pierre de Fermat (of Last Theorem fame) discovered in the 17th century: If n is prime, then it evenly divides a^n - a for any number a. Fermat's test makes it possible to prove that a number n is not prime without finding any of its factors. For example, 2^9 - 2 = 510, which is not divisible evenly by 9. Hence, 9 cannot be a prime number.
Unfortunately, some composite numbers n also evenly divide a^n - a. To eliminate such "false positive" readings, the new algorithm runs a more elaborate but still elementary test, based on searching for pairs of numbers that fulfill a few simple conditions. If the search is successful, then n is declared composite; otherwise, it's prime. The key to the algorithm's efficiency is that the search can be restricted to a small range of numbers.
see also FermatsSmallTheorem|}}
알고리즘
{{|INPUT : integer n > 1
if ( n is of the form a^b, b > 1 ) output COMPOSITE;
r = 2;
while( r < n ){
for a = 1 to 2(sqrt(r))log n
r = 2;
while( r < n ){
if ( gcd(n,r) <> 1 ) output COMPOSITE;
if ( r is prime )
}if ( r is prime )
let q be the largest prime factor of r - 1;
if ( q >= 4(sqrt(r))log n ) and (n^((r-1)/q) <> 1 (mod r))
r = r + 1;if ( q >= 4(sqrt(r))log n ) and (n^((r-1)/q) <> 1 (mod r))
break;
for a = 1 to 2(sqrt(r))log n
if ( (x-a)^n <> (x^n-a) (mod (x^r-1), n) ) output COMPOSITE;
output PRIME;|}}소수판정은 현재 인터넷에서 사용되는 암호기술에 결정적으로 중요한 역할을 합니다. 예컨대 현재 대표적인 암호체계인 RSA는 '큰 정수의 소인수분해가 어렵다'는 사실에 기반하고 있죠. 어떤 큰 정수가 있을 때 그것이 소수인지 아닌지 판별하는 방법이 바로 소수판정법입니다.
이제까지 가장 좋은 알고리즘이 (log n)^O(log log log n) 이었고 거의 상수시간이 걸리는 확률적 알고리즘도 있었습니다. 이번 알고리즘이 O((log n)^12)이라니 실제 동작하는 건 예전게 아직은 더 빠를겁니다. (1024bit 암호까지는...) 그리고 거의 상수시간에 판별하는 randomized algorithm도 있고요. 사실 최적 알고리즘이 언제나 가장 빠른 건 아닙니다. 1000000000000000000000 bit 암호를 쓴다면 물론 이번 알고리즘이 비교할 수 없게 빠르겠지만요. 어쨌거나 대단한 결과라는데는 변함이 없죠. 그리고 이 논문에 쓴 기법을 이용해 보다 실용적이고 빠른 소인수 판별 알고리즘이 나올 수 있을테고요. 이 논문의 가장 중요한 영향은 소수를 기반으로 하는 암호체계에 대한 믿음이 흔들리는 것일겁니다.
어.. 좀 혼동스러운데, 소수판정법이란건 어떤 정수가 소수인지 아닌지 판별하는 방법이란거지 소인수분해를 해주는 방법이란 뜻은 아니지 않나요? 소인수분해는 소수판정보다 훨씬 어려운 걸로 알고 있는데요. 그렇다면 이번 논문때문에 소수를 기반으로 하는 암호체계에 대한 믿음이 흔들린다는 건 이해가 잘 안되는데요.
네. 소인수분해가 소수판정보다 훨씬 더 어렵죠. "소수 판정이 어려운데 소인수 분해는 얼마나 어렵겠니?"라고 하는 것과 "소수 판정은 아주 쉬운데 소인수 분해는 아주 어렵다"는 건 느낌이 다르죠. 암호 알고리즘은 물론 수학을 기반으로 하고 있습니다만, 다들 남들이 잘 안 깨진다고 하니깐 쓰는 것일 뿐입니다. (음모론에 따르면) NSA는 DES나 RSA를 아주 쉽게 들여다보고 있을지도 모릅니다.
네. 암호라는 것 전체가 믿음에 기반하고 있다는 것은 사실입니다. 사실 암호의 안전성에 대해 수학적으로 증명된 것은 없다고 봐야겠죠. 제말은 이 논문의 가장 중요한 영향이 무엇인가에 대한 생각이 저와 다르다는 것이었습니다. 제가 보기에는 소수판정이 (다항 시간안에) deterministic하게 이루어질 수 있다는 사실이 핵심이 아닐까 생각하는데요. 소수판정이 deterministic하게 이루어질 수 있다면 (pseudo prime을 썼던 과거에 비해서 이부분은 정확하게 모르니까 사실과 다르다면 수정해주세요) 오히려 소수를 기반으로 하는 암호체계의 안전성이 더 강화되는게 아닐까요.
앗.. 저도 비슷하게 생각했었는데;; .png ":)")
--지원
저 알고리즘이 가장 빠른 알고리즘이라는 증명이 없으므로 암호체계의 보안성에는 전혀 영향을 안미칠 겁니다. 무엇보다도, 2^10이 넘어가는 (현재가 2^10) 키를 사용할 정도로 연산속도가 빨라진다면 ECC 또는 HCC등의 방식을 사용하게 되므로, 소수판별법 이외의 EDLP등의 새로운 NP-problem들이 생겨나므로 물론 이 논문이 미치는 파장이 작다고도 할 수 없으며, 훌륭한 내용이지만, 현 암호체계에는 그다지 영향이 없을 것입니다. --선
저 알고리즘이 가장 빠른 알고리즘이라는 증명이랑 암호체계의 보안성이랑은 별로 상관이 없어 보입니다만? .. --지원
--지원저 알고리즘이 가장 빠른 알고리즘이라는 증명이 없으므로 암호체계의 보안성에는 전혀 영향을 안미칠 겁니다. 무엇보다도, 2^10이 넘어가는 (현재가 2^10) 키를 사용할 정도로 연산속도가 빨라진다면 ECC 또는 HCC등의 방식을 사용하게 되므로, 소수판별법 이외의 EDLP등의 새로운 NP-problem들이 생겨나므로 물론 이 논문이 미치는 파장이 작다고도 할 수 없으며, 훌륭한 내용이지만, 현 암호체계에는 그다지 영향이 없을 것입니다. --선
저 알고리즘이 가장 빠른 알고리즘이라는 증명이랑 암호체계의 보안성이랑은 별로 상관이 없어 보입니다만? .. --지원