prime

巨大素数と計算機

-- 目次 --

巨大素数に関しての話は極めてポピュラーで, 以下の文献 [4] のような本は昔から人気があり, 計算機が身近になってからは更にずっと多くの種類の本が出まわっています。しかし, 巨大素数はなかなかパソコンで処理がしにくく, しばらくはスーパーコンピュータの独壇場でしたが, 最近事情が変ってきたようでそこまで紹介したいと思います。

参考文献

Hardy and Wright, An Introduction to the Theory of Numbers, Oxford
A. Weil, Number Theory, an approach through history from Hammurapi to Legendre, Birkhauser
(邦訳, 数論, 歴史からのアプローチ, 日本評論社)
P. Ribenboim, The Book of Prime Number Records, Springer-Verlag
(邦訳素数の世界, 共立出版)
コンスタンス・レイド, ゼロから無限へ, 数論の世界を訪ねて, 講談社 BLUE BACKS
Gauss, Disquisitiones Arithmeticae, English Edition, Springer-Verlag
(邦訳, ガウス整数論, 共立出版)

1. Mersenne (メルセンヌ) 素数

自然数 n が合成数のとき, n = ab と書けば

2ⁿ - 1 = (2^a - 1)((2^a)^b-1 + (2^a)^b-2 + ... + 2^a + 1)

となって, 2ⁿ - 1 は合成数となります。では n が素数のとき 2ⁿ - 1 はどうなるでしょうか ? このようなことを考えた人にフェルマー(Fermat, 1601-1665) がいます。彼は

2³⁷ - 1 = 137438953471 = 223 × 616318177

の分解を与えました。フェルマーの方法は次の 3 つの命題によっています。

n が素数でなければ 2ⁿ - 1 は素数でない。
n が素数でなければ 2ⁿ - 2 は 2n の倍数。
n が素数で p が 2ⁿ - 1 の素因子であれば p - 1 は n の倍数。

この事実は Weil (文献 2, p 55) に書いてあり, それによるとフェルマーは 1640 年にメルセンヌ (Mersenne, 1588-1647) に以上の事実を伝えたようです。 (i) は非常に簡単で上で既に示しましたが, (ii), (iii) に関しては, 今日フェルマーの小定理と称するもの, すなわち

a^p ≡ a mod p

となることからの帰結です。肝心なフェルマーの小定理に関しては, フェルマー自身は (a + 1)^p の 2 項展開の式から

(a + 1)^p ≡ a^p + 1 mod p

を得て, a に関する帰納法で示しています。またこの事実も同時期, 知己の一人に手紙で教えているようです。 Weil (文献 2) では主に, フェルマーとその知己との交流の様子を描いていて, それ以外に関してはあまり触れてはいませんがフェルマー以外にも何人かの人達が 2ⁿ - 1 の形の数を考えていたようです。今日

M_p = 2^p - 1

をメルセンヌ数と言いますが, これはメルセンヌが 1644 年に次のように断言したことに始まります。

p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 のとき M_p = 2^p - 1 は素数で,
p < 257 のとき, これ以外の M_p は合成数である。

M₂₅₇ は 38 桁もあり, 計算機がなかった時代には驚異的に大きな数でした。その後しばらく, 道具らしい道具が見つからないまま時間が過ぎましたが, 1866 年 Lucas は M_p が素数であることの判定法を見つけ, これを使って M₁₂₇ が素数であることを発見しました。その後手計算による試みで, メルセンヌの主張は必ずしも正しくないことは, 判明したのですが, ルーカスが発見した M₁₂₇ は 1951 年に至るまで人類最大の素数でした。
1951 年以降, メルセンヌ数が素数であるかどうかの検証は, すべて計算機によることとなり, 計算機の発展とともに巨大素数が発見されていきました。しかし, 使用された方法はいずれも Lucas の方法を改良した Lucas-Lehmer テストと呼ばれるものです。

Lucas-Lehmer テスト

M_p = 2^p - 1 (p > 2) に対して次のような数列を考える。
4, 　4² - 2 = 14, 　14² - 2 = 194, 　 194² - 2 = 37634
このとき M_p が p-1 番目の項を割りきるときに限り M_p は素数である。

Lucas-Lehmer テストは 2 進計算機に非常に都合のよいアルゴリズムであったため, 計算機の性能が上がる度により大きなメルセンヌ素数が, 発見されていきました。1970 年代末に 2 人のアメリカの高校生がメルセンヌ素数 (M₂₁₇₀₁, M₂₃₂₀₉) を発見するというハップニングがありましたが (高校に大型機の端末があったようです), 1980 年代に入ってからごく最近に至るまでスーパーコンピュータ (Cray) の独壇場でした。
しかし最近事情が変わってしまったようです。インターネットで検索しているときに偶然出てきたページに本当かと思うことが書いてありました。少し意訳をすると

1996 年 11 月 13 日, Joel Armengaud は新しいメルセンヌ素数 M_1398269 を発見した。彼はこれを発見するために, インターネット上の 700 人以上の仲間と一緒に George Woltman の製作した Lucas-Lehmer テストを実行するフリーソフトを使用した。

前後を調べると, ソフトは Pentium 搭載のパソコン用のソフトです。このソフトはフリーソフトで誰もが自由に手に入れることができ, 誰もが自由に Pentium 機によるメルセンヌ素数発見の仲間となることができるようです (700 台の Pentium 機で手分けして, チェックする方がスーパーコンピュータより高性能なためのようです)。そして現在では仲間も更に増え, 全員して次の怪物 -- 巨大素数 -- を追い求めています。彼らは人類がまだ見たことがない巨大な怪物を狩り立てる現代の狩人たちです。

リンク

2. Fermat (フェルマー) 数

今度は

2^m + 1

の形の数を考えましょう。2^m + 1 が素数であれば m は 2 の累乗になります。実際 m = ab (a 自然数, b 奇数) とすれば, 以下のように 2^m + 1 は合成数となって矛盾します。

2^m + 1 = (2^a + 1) ((2^a)^b-1 - (2^a)^b-2 + ... - 2^a + 1)

従って, 素数を問題とするときは

F_n = 2^2ⁿ + 1

の数を考える必要があります。これをフェルマー数と言います。フェルマーは n = 6 まで計算しました :

F₀ = 3, 　
F₁ = 5, 　
F₂ = 17, 　
F₃ = 257,　
F₄ = 65537,　
F₅ = 4294967297,　
F₆ = 18446744073709551617

簡単にわかることですが, F₀, F₁, F₂, F₃, F₄ は全部素数です。そこでフェルマーは F_n はすべて素数であろうと予測しました。フェルマーの時代は今日ほど日進月歩ではありません。 100 年後オイラー (Euler, 1707-1783) は 5 番目のフェルマー数を

2³² + 1 = 641 × 6700417

の形に分解して, フェルマーの予想を崩してしまいました。オイラーがとった論法はフェルマーが 2³⁷ - 1 が合成数であることを示したものと本質的に同じです。そのため Weil (文献 2, p 58) は非常に不思議がっています。フェルマー数はガウス (Gauss, 1777-1855) によって別の意味が与えられた :

p が素数のとき, 正 p 角形が定規とコンパスで作図できるためには, p がフェルマー素数であることが必要十分である (Disquisition Arithmeticae, 365)

こうなると F₅ が合成数であるにせよ, 続きが知りたくなります。ここも計算機の発展につれ, 素数の狩人たちが獲物を求めた場所です。しかし一匹もとれなかった。 n が 5 以上のときフェルマー数は, 計算してみるとすべて合成数だったのです。しかしだからといって悲観してはいけません。メルセンヌ数ほど大物の獲物はいませんが, もうちょっと小振りな獲物がいます。

2³² + 1 が合成数であることを示したときのオイラーの論法の一般化から, フェルマー数 F_n の素因子は

h 2^k + 1

の形をしている。フェルマー数がよしんば合成数であっても, 一般に非常に巨大であるから, その素因子の中にかなり大きな素因子があっても, 不思議ではない。そこで上の形の数が素数となるための条件があるであろうか ? 実はある !

Proth の定理

n = h 2^k + 1, 2^k > h のとき　 a^(n-1)/2 ≡ -1 mod n　となる a があれば n は素数である。

この証明もフェルマーやオイラーと同様な議論によって示すことができる。

Proth の定理を使って, 素数を見つける Windows 95 用のソフトもあり, メルセンヌ数で述べた Web サイトの中に見つけることができる。メルセンヌ数の場合はアセンブラーで記述してあるが, これは違うようだ。。

Proth's Theorem (このページからソフトをダウンロードできる)