2002/08/12

素数の13行詩

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

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

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

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

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

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