Ｗｅｂ教材一覧＞アルゴリズム
（ＢＯＫ大区分：１　基礎理論、中区分：２　アルゴリズムとプログラミング、中区分：２　アルゴリズム）

素数判別、素因数分解

学習のポイント

素数判別、素因数分解の基本的なアルゴリズムを理解します。

キーワード

アルゴリズム、素数、剰余、素数判別、エラトステネスのふるい、素因数分解

これまでは、素数研究が社会に直接関係することはあまりありませんでした。ところが、電子メールなどの暗号化が必要になりました。その暗号鍵、復号鍵では、「非常に大きいを素因数分解する計算には非常に時間がかかる」ことをベースにしています（→参考：「公開鍵暗号方式の原理」）。そのため、素数に関する関心が高まっているのです。

２，３，５，７，１１，１３，１７，…など、１と自分自身でしか割り切れない数を素数といいます。１２＝４×３や、１８＝２×９のように、素数ではない数のことを合成数といい、２、３、４、９など、合成数を割り切れる数を約数といいます。そして、２や３など約数自体が素数であるとき、その約数を素因数といいます。

素数を扱うアルゴリズムは、大きく２つに区分されます。

素数判定: 与えられた数ｎが素数であるかどうかを判定するアルゴリズムです。
ｎ＝１２のとき、「約数４が見つかったので１２は素数ではない」というように、一つの約数を見つければよいことになります。
素因数分解: １２＝２×２×３、１８＝２×３×３のように、合成数を構成するすべての素因数とその個数を列挙するアルゴリズムです。素因数分解のほうが複雑になります。一般的には、素数判定のアルゴリズムを発展させて、素因数分解に用いています。

単純な素数判定アルゴリズム

与えた数ｎが素数であるときは１、合成数のときは０を戻す、単純なプログラムを示します。
ｉを２からｎ－１まで変化させ、そのなかでｎを割り切れたら合成数、どれでも割り切れなかったら素数だとすればよいことは自明でしょう。

　　function prime(n) {
　　　　for(i=2; i<=n-1; i++) {
　　　　　　if ((n % i) == 0) return 0;
　　　　}
　　　　return 1;
　　}

しかし、これではあまりにも非効率です。例えば、

ｎ≦３のときは素数です。上のアルゴリズムでは、１のときの例外が考慮されていません。
ｎが２つの数の積になるのであれば、小さいほうの数は、√ｎの以下になります。ｉの上限値を√ｎにすべきです。
２で割れないのであれば、それ以上の偶数で割り切れるはずがありません。ｉが３以上の場合はｉが奇数のときだけチェックすればよいことになります。

それらを考慮すると、次のようになります。

　　function prime(n) {
　　　　if (n <= 3) return 0; 　　　　if ((n % 2) == 0) return 0;
　　　　for(i=3; i<=Math.sqrt(n); i++) {
　　　　　　if ((n % i) == 0) return 0;
　　　　}
　　　　return 1;
　　}

エラトステネスのふるい

上と同様に考えて、ｎがある数で割りきれないときは、その倍数のチェックをする必要がありません。それで、table[i] という表を用意しておき、ｉで割り切れたときは、ｉの倍数ｋについて、table[k] を０にします。このようにして、素数を求めていくのです。
　　function eratosthenes(n) {
　　　　table = new Array(101);
　　　　　　　　　　　　　/* 初期設定：とりあえず２と奇数は素数だと仮定しておく */
　　　　for (i=0; i<= n; i++) table[i] = 0;
　　　　table[2] = 1;
　　　　for (i= 3; i<=n; i=i+2) table[i] = 1;
　　　　　　　　　　　　　/* ３以上、ｎの平方根以下の奇数について */
　　　　for (i=3; i<=Math.sqrt(n); i=i+2){
　　　　　　if (table[i] == 0) continue;
　　　　　　　　　　　　　/* 既に倍数になっているならチェックしない */
　　　　　　for (j=i+i; j<=n; j=j+i) table[j] = 0;
　　　　　　　　　　　　　/* ｊ＝２×ｉ、３×ｉ、…は倍数であるとする */
　　　　　　　　　　　　　/* このようにして、ふるいにかけられて、素数が減少する */
　　　　}
　　　　return table[n];
　　}
エラトステネスのふるいでは剰余の計算が不要です。その観点からも効率的になります。

単純な素因数分解アルゴリズム

上述の「単純な素数判定アルゴリズム」では、素因数が何であるかを知ることができません。その「改良版」をベースにして、素因数分解アルゴリズムにします。

フェルマの方法

素因数分解というより、２つの約数の積として分解するアルゴリズムです。その約数をさらに分解すれば、素因数分解になりますが、ここでは、解法のアイデアを示すことを目的として、約数を求めるだけにします。
　　　ｎ＝(ｘ－ｙ)×(ｘ＋ｙ)＝ｘ²－ｙ²　（ｘ≧ｙ≧０の整数）
として、ｘ－ｙ＝１ならば素数、そうでなければｘ±ｙが約数になります。
　上式から、
　　　ｙ＝√ｘ²－ｎ
となりますが、ｙは整数でなければなりません。
　それで、ｙが整数になるまで（ｎ＝(ｘ－ｙ)×(ｘ＋ｙ) になるまで）、
　　　√ｎ≦ｘ≦ｎ／２
の範囲で、ｘを１ずつ変化させて、試行錯誤させることになります。

function fermat(n) {
　　　　　　　　　　　　msg = "<html><body>"
　　　　　　　　　　　　　　+ "<h4>フェルマの方法による約数探索</h4>"
　　　　　　　　　　　　　　+ "<p>n=" + n + "</p>"
　　　　　　　　　　　　　　+ "<table border='1'><tbody>"
　　　　　　　　　　　　　　+ "<tr><td>x</td><td>y</td>"
　　　　　　　　　　　　　　+ "<td>x-y</td><td>x+y</td><td>(x-y)(x+y)</td></tr>";
　　xmin = Math.ceil(Math.sqrt(n));　　　　　/* √ｎの切り上げ */
　　xmax = n/2;
　　for (x=xmin; x<=xmax; x++) {
　　　　y = Math.floor(Math.sqrt(x*x-n));　　/* √ｎの切り捨て */
　　　　　　　　　　　　xmy = x-y; xpy = x+y; xy = xmy*xpy;
　　　　　　　　　　　　msg = msg + "<tr><td>" + x + "</td><td>" + y + "</td>"
　　　　　　　　　　　　+ "<td>" + xmy + "</td><td>" + xpy + "</td><td>" + xy + "</td></tr>";
　　　　if ( (x-y)*(x+y) == n) break;
　　}
　　　　　　　　　　　　msg = msg + "</tbody></table>";
　　　　　　　　　　　　xmy = x-y; xpy = x+y; xy = xmy*xpy;
　　　　　　　　　　　　if (xy == n) msg = msg + "<p>" + n + "＝" + xmy + "×" + xpy + "</p>";
　　　　　　　　　　　　else msg = msg + "<p>" + n + "は素数</p>";
　　　　　　　　　　　　msg = msg + "</body></html>";
　　　　　　　　　　　　document.write(msg);
}

この方法は、約数が大きいとき（√ｎに近いとき）に効率的です。しかし、√を求める計算に時間がかかるので、ｎが大きいときには探索範囲が広く、非効率になります。

大きな数の素因数分解には、非常に計算量が大きくなることから、効率的な解法を求めることが、数学者の関心を集め、以前からも多様な研究が行われてきました。素因数を探すことに比べて、最大公約数を求める操作は計算量が小さい。古典的な方法では、それをうまく用いて高速化を図っています。

特に最近ではデータの暗号化が重視され、特に公開鍵暗号方式が広く用いられています。この方式は、百桁以上の非常に大きな２つの素因数をもつ合成数から素因数を見つけることは時間がかかることを基盤にしています（→参考：「公開鍵暗号方式の原理」）。
　効率的な解法が発見されると、この暗号方式の機密性が崩されます。これは、個人のクレジット番号の漏洩から、国家機密にいたるまで、大きな影響を及ぼします。暗号方式の脆弱性を把握するために、効率的な解法の研究が重要課題になり、多様な方法が発表されています。

計算プログラム

１：素数表による因数分解
２：単純計算による因数分解
３：フェルマの方法による約数の検出
４：ρ法による約数の検出（求められないこともある）
ｎに大きい数値を与えると、時間がかかるので注意してください。