メルセンヌ数を10進表示する - inamori’s diary「これまでで最大の素数」を発見 << WIRED.jp 久しぶりに新たなメルセンヌ素数が発見されたようです。メルセンヌ数は、 Mn = 2n - 1 という形をしているのですが、なぜこの形の素数を求めようとするかというと、非常に高速な素数判定法があるからです。 さて、新たに得られたメルセンヌ素数を仮にMとしましょう。これは M = 257885161 - 1 と表されます。2進数で表すのは簡単ですが、実は10進表示するのは難しいです。例えばPythonで、 print 2 ** 57885 - 1 とすると0.064秒、 print 2 ** 578851 - 1 とすると6.4秒かかりました。一桁指数が増えると100倍の時間がかかるということです。この調子だと64000秒かかりそうです。 この10進表示するというのは多項式の計算のようなものと考えることができます。2桁なら2項の多項式と考
