Mathematica で素数を発見−これが現在最大の素数−

1999年6月，世界的な数学者，コンピューターサイエンスの学者，そして数学好きの人々からなるグループが，メルセンヌ素数の巨大なものを発見しようというプロジェクトであるGreat Internet Mersenne Prime Search (GIMPS)で，2^6972593-1が素数であることを突き止めました．この数は現在のところ既知の最も大きな素数です．発見者は公式にはN. Hajratwala氏, G. Woltman氏, S. Kurowski氏です．このうちHajratwala氏がボランティアで自分の所有するマシンで実際に素数を見付け，後の2人はソフトウェア／ネットワークの設計者だったということです．この素数は十進数で2,098,960桁の長さになり，電子フロンティア財団(Electronic Frontier Foundation)が提供する5万ドルの賞金の対象となります．この件に付随したことですが，興味深いことに，1990年代の初めには Mathematica が発見を可能にする上で重要な役割を果たしていました．

最初に歴史的な背景：2^q-1の形の素数はフランス人の僧侶であるMarin Mersenne (1588-1648)の名前を取って「メルセンヌ素数」と呼ばれています．メルセンヌは偉大なるフェルマとの文通の中でメルセンヌ素数について語っています．メルセンヌ素数は数論の，例えばいわゆる完全数や暗号学において長い間重要な役割を果たしてきました．これらの分野ではある種の代数体に効率的なメルセンヌに基づく演算が利用されていました．メルセンヌ素数は何世紀にも渡って研究されてきましたが，メルセンヌ素数は無限に存在するのかなどの多くの基本的な問題がまだ残っています．

非常に大きな数が本当に素数かどうかを決定する唯一の方法はいわゆる素数判定で，メルセンヌ素数の場合にはLucas-Lehmerテストと呼ばれるものが非常に有効です．Lucas-Lehmerテストは桁数が数千から数百万の巨大数を平方します．

このような演算では，「irrational base discrete weighted transform」（略してIBDWT）という1990年代はじめにReed CollegeのR. Crandall氏とNeXT, Incによって Mathematica をプロトタイプ環境として使って開発されたアルゴリズムが基礎になっています．Woltman氏が1990年代の中頃にアセンブラの改良型として投げかけたのはこのアルゴリズムです．つまりプロトタイプ／開発サイクルを完結させるのに Mathematica は理想的だったのです．

IBDWTの考え方は巨大数を無理数を底としたものにまで拡げることです．そして，次に古典的なFFTの変形である離散重み変換を適用してこの底を持つ数を異例の速さで掛け合せたり平方したりします．Crandall氏が言っているように「Mathematica は記号と数値を混ぜ合せなければならないときの，またそのような新しい非標準的なアルゴリズムをインタラクティブな探究を通して見付けるための理想的な環境です．」

記録的な素数の十進法によるすべての数字（2百万個以上）を示した素数のポスターがPerfectly Scientific, Incで入手できます．

関連体験談