■ 楕円曲線法(ECM, Elliptic Curve Method)
■ 複数多項式二次ふるい法(MPQS, Multiple Polynomial Quadratic Sieve)
素因数分解の困難さを説明してきたわけですが,現在素因数分解のもっとも有効な方法としての二大横綱が楕円曲線法と複数多項式二次ふるい法です。文献によれば最近因数分解された数字の一覧表を見るとほとんどが楕円曲線法か複数多項式二次ふるい法だそうです。
楕円曲線法は因数分解しようとする数字の性質(どのような素因数をもつか)によって因数分解にかかる時間が決まるようです。ですから桁数が多くても,その数の性質によっては短時間に因数分解できるそうです。
一方,複数多項式二次ふるい法は因数分解しようとする数字の性質には左右されず,桁数だけに依存するようです。
最近では数体ふるい法(NFS, Number Field Sieve)という素因数分解法もあるようですが,私は不勉強のため良く知りません。日本RSA社のFAQページ(サイト移転のため2008年現在はアクセス出来ません)を読んだかぎりでは,120~130桁を越える数字の因数分解については,いずれ複数多項式二次ふるい法にとって変わることになりそうです。
これらの方法を持ってしても素因数分解が困難な問題であることにはかわりがありません。Mintさんから頂いたメールによると『60桁の数字の素因数分解に 15~30分 程度,80 桁では 40時間程度(Pentium 200MHz),100 桁では 0.5~1 年程度で素因数分解されるであろう』と予測されています。
実際にRSA暗号で使われる200桁の数字の素因数分解は約十億年という時間がかかってしまうので,素因数分解の困難さがそのまま暗号の強度となっているわけです。
これら楕円曲線法や複数多項式二次ふるい法は,立教大学の木田祐司先生が作られた UBASIC というプログラムで実現されていますのでご一読をお勧めします。 http://www.rkmath.rikkyo.ac.jp/~kida/ubasic.htm にあります。ここに含まれるファイルは
- ubapl94 .lzh(UBASIC86 多倍長計算用BASIC用アプリケーション~1994)
- ubapl95 .lzh(UBASIC86 多倍長計算用BASIC用アプリケーション1995)
- ubcommon.lzh(UBASIC86 多倍長計算用BASIC用共通ファイル)
- ubdsv883.lzh(UBASIC86 多倍長計算用BASIC for DOS/V)
- ubfmr883.lzh(UBASIC86 多倍長計算用BASIC for FM-R)
- ubnec883.lzh(UBASIC86 多倍長計算用BASIC for PC98)
- ubgraph .lzh(UBASIC86 多倍長計算用BASIC グラフィックサンプルプログラム)
- ubhelp .lzh(UBASIC86 多倍長計算用BASIC HELP ファイル)
などです。UBASIC は BASIC を元にしながら 2700桁までの多倍長計算が出来るようにした優れたプログラムです。
本家本元は立教大学の木田祐司先生のホームページ http://www.rkmath.rikkyo.ac.jp/~kida/ です。学術方面(SINET)から GET するならこちらのほうが速いでしょう。木田先生のホームページには「数体ふるい法」の文献が置いてあります。数学屋には必見です。
前へ 次へ
メニューへ戻る