제목대로 입니다. NP(Nonpolynomial)가 아니라 P입니다.
알고리듬 관련 책을 한번이라도 보신 분이라면 무슨 뜻인지 아실 겁니다.
암호학에 있어서의 혁명적인 논문이군요.
'페르마의 마지막 정리' 증명에 버금가는 발견이네요.
역시 geekforum의 기사 중에서 관심을 끄는 기사를 올려봅니다.
http://geekforum.kldp.org/stories.php?story=02/08/10/2549088
----------------------------------------------------------------------------------------
소수 판별 다항식 알고리듬이 발견되었다고 합니다.
"Prof. Manindra Agarwal and two of his students, Nitin Saxena and Neeraj Kayal (both BTech from CSE/IITK who have just joined as Ph.D. students), have discovered a polynomial time deterministic algorithm to test if an input number is prime or not. Lots of people over (literally!) centuries have been looking for a polynomial time test for primality, and this result is a major breakthrough, likened by some to the P-time solution to Linear Programming announced in the 70s.
One of the main features of this result is that the proof is neither too complex nor too long (their preprint paper is only 9 pages long!), and relies on very innovative and insightful use of results from number...."
원문 출처:
http://www.cse.iitk.ac.in/news/primality.html
-----------------------------------------------------------------------------------------
다음은 ZDNet의 기사입니다.
원문 출처:
http://www.zdnet.co.kr/biztech/hwsw/techtrend/article.jsp?id=51346&forum=0
-----------------------------------------------------------------------------------------
인도 과학자, 정확한 암호화 연산 방식 개발
인도의 컴퓨터 과학자들이 컴퓨터가 소수 여부를 신속하게 판별해낼 수 있는 방법을 고안해 냄으로써 오랜 숙원이던 수학 문제의 해결했다. 이는 암호해독에 있어서 중대한 발전을 의미한다.
Sandeep Junnarkar (Special to ZDNet News )
2002/08/12
원문보기
전자 상거래 보안에 사용되는 암호화 알고리듬인 RSA는 자신 스스로나 숫자 1로만 나뉘는 소수(素數)를 판정해 낼 때 소수점 이하 수가 충분히 클 때 이를 소수로 추정하는 방식을 쓴다. 이 수가 소수인지 여부를 확실하게 판별해내는 것은 거의 불가능하다.
RSA 방식을 사용해 암호 키를 생성해낼 때 훨씬 큰 소수를 만들기 위해 대단히 큰 소수와 그를 곱한 수 두 가지를 사용한다. 이같은 현행 연산 방식은 속도는 빠르지만 오답을 산출할 가능성이 약간 있는 소수 판정법(primality tests)이라는 방식을 사용한다.
그런데 캉푸에 있는 IIT(Indian Institute of Technology)의 마닌드라 아그라울과 그의 학생인 니래즈 카얄, 니틴 새시나가 공동 개발한 새로운 연산 방식을 사용하면 매번 정확한 답을 산출하는 것으로 알려졌다.
뉴저지 주립대학 컴퓨터 과학과 에릭 알렌더 교수는 "현행 암호 해독 소프트웨어에서 가장 두드러진 단점은 어떤 수가 소수인지를 판별해 낼 수 없다는 것"이라고 말했다. "이번에 새로 고안된 연산 방식은 몇 세기 동안 미해결 상태였으며 지난 몇 십년 동안 열정적으로 연구가 진행되고 있는 기본적인 의문에 답을 제공한다."
아직 '소수(素數)는 P에 있다(Primes is in P)'라는 아그라울의 논문은 아직 출간되지 않았지만 고대 중국과 그리스에서 오랫동안 수학자들을 사로잡았던 수학 문제를 처리하는 방법을 제시한다는 점에서 이 분야를 흥분 속으로 몰아넣었다. 뛰어난 컴퓨터 과학자들과 수학자들은 이 논문을 연구했다.
알렌더는 "이 논문 가운데 일부는 상당히 복잡했다. 이것은 정말 사랑스럽고, 산뜻하며 훌륭한 연산"이라고 평가했다.
컴퓨터 과학자들은 아직 이 연산이 실용화되려면 시간이 필요하다고 인정하고 있다.
아그라울은 "이번 연구에서 소개된 연산은 현재 가장 빠른 것으로 알려진 소수 판정법 알고리즘보다 느린 것이 흠이다. 우리가 연구한 연산법이 만족스러운 것은 아니지만 오류가 생길 수 있는 기존 방법과 달리 완벽한 답을 제시한다"고 말했다.
컴퓨터 과학자들은 많은 영역에서 사람들이 종종 오류 가능성을 기꺼이 견뎌왔다고 말했다. 하지만 은행이나 보안 통신같은 분야에서 암호화에 대한 신뢰성 문제가 증가함에 따라 암호화의 정확성에 대한 문제가 최우선시되고 있는 실정이다.
알렌더는 "이번에 새로 나온 연산 방식은 이론적인 결과이며 첫발을 내디뎠다는 점에 가장 큰 의미가 있다. 앞으로 이번 연산 방식을 시작으로 이를 실용화할 수 있도록 기술을 개선하고 향상시켜 나가게 될 것"이라고 말했다.
