素数の13行詩

たまーに、タイムリーな話題でも。

ZDNN: 暗号技術研究者が素数の問題を克服

素数っていうのは皆さんご存じの通り1と自分自身以外公約数のない「素敵な数」のことですが、コレがなかなか奥が深いとかいうことを利用して(説明を省きすぎ)RSAとかの暗号の強さが保証されているわけですな。で、今回の証明は何がすばらしいかというと、どうも素数かどうかの判断がとっても速くできるらしい、という話らしいですな。

ということで、さっそくその論文を見てみたんですが、……やっぱり英語ですね。読む気になりません。しかしながら、アルゴリズムがコンピュータ言語っぽく載ってるじゃないですか(MATLAB風だのPascal風だの言われてますが、この際私には関係ないですな)。

で、それをそのまま引用すると、こんなかんじ。

 1. if (<var>n</var> is of the form <var>a<sup>b</sup></var> , <var>b</var> &gt; 1) output COMPOSITE;
 2. r=2;
 3. while (<var>r</var> &lt; <var>n</var>) {
 4.     if( gcd(n,r) != 1 ) output COMPOSITE;
 5.     if( <var>r</var> is prime )
 6.         let <var>q</var> be the largest prime factor of <var>r</var>-1
 7.         if(<var>q</var> &gt;= 4<var>r</var><sup>1/2</sup>log <var>n</var>) and (<var>n<sup>r-1/q</sup></var> !≡ 1 (mod <var>r</var>)) 
 8.             break;
 9.         r=r+1;
10. }
11. for a=1 to 2<var>r</var><sup>1/2</sup>log <var>n</var>
12.     if( <var>(x-a)<sup>n</sup></var>
13.