2013å¹´ã¨ç´ å› æ•°åˆ†è§£

あけましておめでとうございます。

新年を迎えて、ふと、今年の西暦である2013を素因数分解したらどんな数に分解されるのか気になったので考えてみた。桁をすべて足し合わせると 2+0+1+3=6 と3の倍数になり、3で割り切れることは明白だ。3で割ると671となる。671に対し桁を一つ飛ばしにして足し合わせた数の差が (6+1)-7=0 で11の倍数(0を含む)なので11で割り切れることも簡単にわかる。671を11で割ると61の素数となる。つまり、2013の素因数分解は 3×11×61 となる。

大きな素数同士による合成数の素因数分解は非常に困難であることが知られている。この性質を利用して多くの暗号アルゴリズムで大きな素数による合成数が利用されている。現在のところ、素因数分解アルゴリズムとしては、楕円曲線法(ECM; Elliptic Curve Method)や複数多項式二次ふるい法(MPQS; Multiple Polynomial Quadratic Sieve)がよく使われているらしい。で、手軽にこれらを利用できるライブラリがないかと軽く調べたところNZMATH(ニジマス)という数論のためのPythonモジュールがあることを知ったので、早速インストールして使ってみた。

ところで、大きな素数といえばメルセンヌ素数が有名だが、マラン・メルセンヌは、2ⁿ-1 に対してnが257以下のとき、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257のときにのみ素数となると主張した。しかし、一部に間違いがあり、n = 61, 89, 107のときも素数であり、また、n = 67, 257は素数ではなく合成数であった。

そこで、誤って素数としていたn = 67のときの 147573952589676412927 について楕円曲線法(ECM)で解かせると、すぐに 193707721×761838257287 と結果が出力された。

>>> import nzmath.factor.methods as methods >>> methods.factor(147573952589676412927, method="ecm") [(193707721L, 1), (761838257287L, 1)]

更に、メルセンヌが見落としていた9番目と10番目のメルセンヌ素数である 2305843009213693951 (2⁶¹-1) と 618970019642690137449562111 (2⁸⁹-1) を掛け合わせた46桁の合成数 1427247692705959880439315947500961989719490561 を複数多項式二次ふるい法(MPQS)で解いてみたところ、30分ほどで正しく2つの素数に分解できた。

>>> methods.factor(1427247692705959880439315947500961989719490561, method="mpqs") [(2305843009213693951L, 1), (618970019642690137449562111L, 1)]

ソースコードも簡単に確認できるし、NZMATHはなかなか楽しい。

それでは、本年もよろしくお願い申し上げます。