西暦2400年はうるう年？うるう年じゃない？：いまから始めるアルゴリズム（3）（2/2 ページ）

» 2007年11月21日 00時00分公開

[鹿野恵祐，＠IT]

前のページへ 1|2 　　　　　　

素因数分解、覚えていますか

　もう1つの例を取り上げましょう。

　素因数分解って覚えていますか？ある数を、素数を掛け合わせた形で表すための方法です。例えば、「52」という数字を素因数分解すると、「2 * 2 * 13」という素数の積で表せます。

　……というと簡単そうに聞こえるかもしれませんが、素因数分解を行うことは非常に難しいのです。先ほどの52でいえば、

2 * 2 * 13 = 52

と計算するのと

52 = 2 * 2 * 13

と素因数分解するのでは、かかる手間が大きく異なります。

　では実際に、52を素因数分解してみましょう。

（1）     2 ) 52
（2）     2 ) 26
（3）    13 ) 13
（4）          1

　まず、（1）素数のうち最も小さな2で割ってみます。すると商は26、余りは0で割り切れることが分かります。

　（2）商である26をもう一度2で割ってみると、商は13、余りは0でこれも割り切れます。

　（3）この13をさらに2で割ってみると商は6、余りが1で割り切れません。そこで、2の次に小さい素数である3で割ってみます。しかしこれも余りが出て割り切れません。

　続けて、さらに大きな素数5、7、11で順に割ってみると、やはり余りが発生します。13で割ってみると、商が1で余りが0になります。（4）商をこれ以上割ることができなくなったので、素因数分解はここで終了し、「2 * 2 * 13」という素数の積が得られます。

（1）     7 ) 371
（2）    53 )  53
（3）           1

　同様に、「371」という数字を素因数分解してみましょう。2、3、5、7……と、小さい順に素数で割っていくと、（1）7で初めて割り切れ、商は53になります。（2）53は素数ですので、1と53以外では割り切れません。（3）そこで「371 = 7 * 53」という結果が得られます。

　ちなみに、「373」を素因数分解するとどうなるか、すぐに分かりますか？実は、373は素数です。これ以上の素因数分解はできないのです。

　しかし、373が素数かどうかすぐに分かる人は、そう多くはないでしょう。やはり小さい順に素数で割っていった結果、どこかの時点で、これ以上素因数分解できないことが分かることになるはずです。

コンピュータに素因数分解をさせるには

　このように、皆さんが素因数分解するときには、小さい素数から順に割ってみるという方法を取ることが多いでしょう。これは、皆さんの記憶に素数のテーブルがあるから実現できる方法です。

　では、コンピュータに素因数分解をさせたいとき、どのように命令すればよいのでしょうか？コンピュータは、割ろうとしている数が素数かどうかを知りませんから、まずは割る前にその数が素数かどうかを判定する必要があります。

　すでに割った数の倍数は素数ではないことに注目し、その計算を行うことで、多少の高速化を図れる可能性があります。ただし、各素数の倍数に基づく処理を実装することになり、ソースコードは肥大化します。

　今回はトレードオフを行い、2以外の偶数は素数ではないという処理のみを盛り込むことで、ソースコードの長さを抑えました。

このアルゴリズムを基に作成したソースファイルのダウンロード（C・Java）

　普通に生活をしていると、素因数分解などめったに行うことはないでしょうが、コンピュータの通信で使われるRSA暗号は、巨大な数を素因数分解することの難しさを利用して作られた暗号系です。Webブラウザや携帯電話に組み込まれ、皆さんも知らず知らず使っていると思います。

　RSA暗号の鍵として、現在は10進数で300けた以上の数が使われています。300けたの数を素因数分解するなんて気が遠くなりそうですが、連載第1回で取り上げた大きな数の取り扱い方法を使えば、300けたの数字でも計算は行えます。

　すでに10進数で193けたの数が素因数分解されています。興味があれば、よりけたの大きな数の素因数分解にチャレンジしてみるのもいいかもしれません。

　これで、今回の連載は終了です。

　アルゴリズムに関しては、各アルゴリズムの計算量の違いについて取り上げる記事をよく見掛けます。今回は、多忙なITエンジニアの皆さんが普段あまり考えないようなことを取り上げ、身近な事柄にもアルゴリズムが隠れていることを伝えるのを目的としました。もし興味があれば、アルゴリズムによる計算量の違いも勉強してみてください。

　最近ではPCの性能も上がり、Javaなど豊富なAPIを持った言語もありますので、あまり普段はアルゴリズムを意識することがないかもしれません。しかし本来、アルゴリズムに関する問題は身の周りにたくさんあるのです。

　この記事をきっかけに、「この処理はどうやっているのかな？」「もしこの命令が使えなかったら、どうやって実現したらいいんだろう」など、興味を持ってみてください。考える楽しみが生まれるかもしれません。そしてぜひ皆さんも、優れたアルゴリズムを考えてみてくださいね。