새로운 인수분해 알고리즘

해커뉴스를 보니 P=NP 블로그 포스트가 소개되어 있다. P=NP 블로그는 잘 모르는 게 너무 많아서 잘 안 읽었는데, 요번 포스트는 좀 읽어봤다. 켁. 전산수학 하는 사람이 관심있을만 할 듯.

A New Provable Factoring Algorithm in Gödel’s Lost Letter and P=NP

primality test로는 deterministic algorithm이자 복잡도가 자리수의 다항식 (그러니까 \log N의 다항식)인 AKS가 알려져 있지만, prime factor를 찾는 알고리즘은 아직 복잡도가 자리수의 sub-exponential 알고리즘이 알려져 있지 않다.

P=NP 블로그에서는 prime factor를 찾는 알고리즘을 unprovable과 provable로 분류하고 있는데, unprovable은 undeterministic이거나 또는 증명되지 않은 가설을 가정한 알고리즘을 말한다. 해커뉴스 댓글을 보니 unprovable algorithm으로 Pollard’s rho algorithm 이야기가 나오던데, 위키피디아를 읽어보니 점화식 a_{n+1}= a_n^2 +c로 생성되는 수열로 modular sequence를 만들어서 주기를 찾아내는 방법으로 prime factor를 발견하는 알고리즘 같다. 이 수열이 random walk인지 증명할 수 없기 때문에 unproven이라고 한다.

P=NP 블로그에 따르면 Michael Rubinstein이라는 정수론 학자가 새로운 인수분해 알고리즘을 발견한 모양인데, 그 복잡도가 N^{\frac{1}{3}+\epsilon} 이라고 한다. 여기서 \epsilon이 엄청 작은 건 아닌 것 같고, divisor bound 때문에 sub-linear로 \exp \left(O\left(\frac{\log N}{\log \log N}\right)\right) 사이즈가 들어가는 듯.

여하간 이 복잡도는 N이 이진수로 표현될 때 자리수가 n이면 2^{\frac{n}{3}}인데, 현재 알려진 가장 빠른 unprovable로 general number field sieve가 다음 복잡도를 가진다고 한다.

\displaystyle \exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln N)^{\frac{1}{3}}(\ln \ln N)^{\frac{2}{3}}\right)

이 값은 러프하게 이진수 자리가 n이면 2^{n^{1/3}}으로 요번에 새로 발견된 Rubinstein의 알고리즘과 크게 차이나지 않는다. 오호!! 근데 자세한 알고리즘의 과정은 귀찮아서 안 읽어봤다-_-

여하간 자꾸 factorize bound가 낮아지는데 이거 polynomial time도 발견되는거 아닌지 모르겠다. 일전에 RSA가 깨지냐에 대한 잡담을 하긴 했지만, 여러가지로 RSA가 정말 위험할지도…. ㅋㅋㅋ

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중