千桁の数をかけ算する方法 ― 桁の壁を越えた数たち

How Computers Multiply Thousand-Digit Numbers

読み物

$1234 \times 5678$ なら筆算で答えが出せる。では、千桁どうしのかけ算は？　百万桁どうしは？　円周率の計算記録や暗号の安全性は、まさにこの「とんでもなく大きな数のかけ算」の上に成り立っている。けれど、ふつうのコンピュータが一度に扱える数は、たかだか $20$ 桁ほど（$64$ ビット）でしかない。

では、その小さな箱しか持たない計算機が、どうやって桁の壁を軽々と越えていくのか。この記事では、巨大な数を相手にする知恵 ―― そして、その先で人々が追い求めてきた途方もない素数の物語を、肩の力を抜いて眺めてみたい。

大きな数は「塊」に切って持つ

発想はいたって素朴だ。一個の箱に入らないなら、たくさんの箱に分けて入れればよい。多倍長整数は、数を固定幅の塊 ―― この分野ではリム（limb）と呼ぶ ―― に区切り、その並びを配列として持つ。ちょうど私たちが大きな数を三桁ごとにカンマで区切るように、計算機は $64$ ビットごとに区切って、配列の一マスずつに詰めていくのである。

こうしてしまえば、足し算は小学校の筆算とまったく同じだ。下のリムから順に足し、あふれた分（繰り上がり）を上のリムへ送る。引き算も同様。表現の細かな選び方 ―― 符号をどう持つか、どちら向きに並べるか ―― には流儀があるが、考え方は驚くほど身近である。詳しくは「多倍長整数の表現」が語っている。

図 1: 多倍長整数の持ち方。人が $3$ 桁ごとにカンマで区切るのと同じ要領で、計算機は数を $64$ ビットの塊（リム）に区切り、配列の一マスずつに詰める。$60$ 桁の数はどれも $196$〜$200$ ビットなので、$3$ リム（$192$ ビット）では足りず $4$ リムに収まる。図では最上位のリムを左に置いたが、どちら向きに並べるかは実装の流儀である。

かけ算で立ちはだかる壁

足し算は桁数に比例した手間で済む。問題はかけ算だ。筆算でかけ算をするとき、上の段の一桁ずつを下の段の全桁にかけていく。$n$ 桁どうしなら、桁の組み合わせは $n \times n$ 通り ―― つまり手間は桁数の二乗に比例して膨らむ。

$10$ 桁が $100$ 桁になれば手間は $100$ 倍、$1{,}000$ 桁になれば $10{,}000$ 倍。円周率を百万桁計算しようとすれば、この素朴なかけ算のままではたちまち手に負えなくなる。長らく「かけ算は二乗の手間がかかるもの」と誰もが信じていた。ある若者がそれを覆すまでは。

ひとくちメモ：二乗の重さを体感する

計算量が「二乗に比例する」とは、入力が $10$ 倍になると手間が $100$ 倍になるということ。$O(n^2)$ と書く。一方このあと出てくる賢い手法は $O(n^{1.585})$ や、さらに速い $O(n\log n)$ 級に下がる。指数の小さな差が、桁数が大きくなるほど天と地ほどの差になる ―― それがアルゴリズムの面白さだ。

分割統治の魔法 ― 4 回を 3 回に

$1960$ 年、まだ学生だったアナトリー・カラツバが、巨匠コルモゴロフのセミナーで「かけ算は二乗より速くできる」ことを示してしまった。コルモゴロフ自身が二乗が最善だと予想していた、その目の前でである。

仕掛けはこうだ。二つの数をそれぞれ上半分と下半分に割る。素朴にやると、上×上・上×下・下×上・下×下と四つのかけ算が要る。ところがカラツバは、足し算をうまく挟むことで、これを三つのかけ算で済ませてしまった。一回分のかけ算を、ずっと手間の少ない足し算と引き算に化けさせたのだ。

そして半分にした数を、また半分に割って同じ手を使う。割って・割って・割り続けるこの「分割統治」によって、手間は二乗から $O(n^{1.585})$ へと落ちる。たった一回のかけ算を節約する小さな工夫が、再帰で雪だるま式に効いてくる ―― 計算機科学でいちばん美しい逆転劇の一つである。この発想をさらに推し進めたのが Toom-Cook や NTT といった高速乗算で、百万桁のかけ算を現実的な時間に収めている。

図 2: カラツバ法。$x=12,\ y=34$ を上位・下位に分け、$ac,\ bd,\ (a+b)(c+d)$ の3 回のかけ算だけで $x\cdot y = ac\cdot B^2 + \bigl((a+b)(c+d)-ac-bd\bigr)\cdot B + bd$ を組み立てる（$B=10$）。素朴な 4 回が 3 回に減るこの工夫が、再帰で効いて $O(n^{1.585})$ を生む。

そして、巨大な素数を狩りに出る

大きな数を自在に計算できるようになると、人はもっと大きな獲物を追いたくなる。その筆頭が巨大な素数だ。

$2$ のべき乗から $1$ を引いた形 $2^p - 1$ の素数をメルセンヌ素数という。この形には、素数かどうかを比較的速く判定できる特別な検査法（リュカ–レーマー判定）があるため、記録更新の常連になっている。いまでは GIMPS という分散プロジェクトが、世界中の人々の余ったパソコンの計算力を束ね、新しいメルセンヌ素数を掘り当てている。誰でも参加できる、史上最大級の宝探しだ。

その到達点を一つ挙げておく。$2024$ 年 $10$ 月に見つかった $2^{136{,}279{,}841} - 1$ は、十進で $41{,}024{,}320$ 桁 ―― 四千万桁を超える。この一個の数を紙に印刷しようとすれば、それだけで本が何十冊にもなる。

ある数が素数かどうかを「割り算せずに」見抜く技も発達した。素数判定のミラー–ラビン法などは、巨大な数でもごく短時間で「ほぼ確実に素数」と言い当てる。割り切る相手を直接探すのではなく、素数なら必ず満たす合同式を調べ、それが破れれば合成数だと確定させるのである。ただし合成数でもたまたま通ってしまう底があるので、底を変えて何度も試す ―― 「ほぼ確実に」と付くのはそのためだ。

ひとくちメモ：作るのは易しく、ばらすのは難しい

二つの大きな素数をかけ合わせて積を作るのは一瞬だ。ところが、できあがった積から元の二つの素数を当てる ―― 素因数分解 ―― は、桁が大きくなると気が遠くなるほど難しい。この「作るのは易しく、ばらすのは難しい」非対称性が、RSA 暗号を成り立たせている基本原理である。いまの Web 通信では鍵そのものの交換は楕円曲線を使う方式が主流になったが、通信相手が本物であることを示す署名では RSA が今も広く使われている。巨大な数を速く扱う技術は、公開鍵暗号を含む現代の計算基盤を静かに支えているのである。

結び ― 小さな箱で大きな世界を

$64$ ビットの小さな箱しか持たない計算機が、数を塊に切って配列に並べ、かけ算の手間を分割統治で削り、ついには四千万桁もの素数を狩り出すまでになった。桁の壁は、賢いアルゴリズムの前にいくらでも譲歩する。「大きな数は遅い」という素朴な予感を、人類はひとつずつ覆してきたのである。

その逆転劇の中身をのぞいてみたくなったら、次は、実際の手順を見に行こう。中級では、高速乗算・高速除算・モジュラー算術・GCD という、巨大整数を支える四本柱が待っている。

よくある質問

Q: コンピュータはどうやって何千桁もの整数をかけ算するのか

A: 数を「リム」と呼ぶ固定幅の塊（たとえば $64$ ビットごと）に区切り、配列として持つ。短い数なら筆算と同じ方法でかけるが、桁数が増えると筆算は桁数の二乗に比例して重くなる。そこで大きな数は半分ずつに割って賢く組み合わせる Karatsuba 法や、さらに進んだ Toom-Cook・FFT / NTT 系の手法を使い、計算量を大きく減らす。

Q: なぜ人々はそんなに大きな素数を探すのか

A: 理由はいくつかある。第一に純粋な好奇心と記録への挑戦で、GIMPS のような分散プロジェクトが世界中のパソコンをつないで新しいメルセンヌ素数を見つけている。第二に応用で、RSA 暗号などはふたつの大きな素数のかけ算が簡単なのに対し、その積を素因数分解するのが極めて難しいという性質を安全性の土台にしている。大きな素数を扱う技術は、こうした暗号の根を支えている。

Q: カラツバ法はいつでも筆算より速いのか

A: そうではない。カラツバ法はかけ算の回数を減らす代わりに、足し算・引き算と再帰呼び出しの手間が増える。桁数が小さいうちはこの追加分のほうが大きく、素朴な筆算のほうが速い。実用のライブラリは桁数に閾値を設け、閾値を超えたところで筆算から Karatsuba へ、さらに大きくなれば Toom-Cook や NTT へと切り替えている。

参考資料

カラツバ法 ― Wikipedia：$1960$ 年のカラツバのアルゴリズムと、計算量 $O(n^{\log_2 3})$ の導出。
メルセンヌ数 ― Wikipedia：$2^n - 1$ の形の数、リュカ–レーマー判定、発見の歴史。
GIMPS (Great Internet Mersenne Prime Search)：分散プロジェクトの公式サイト。既知最大のメルセンヌ素数 $2^{136{,}279{,}841} - 1$（$41{,}024{,}320$ 桁、$2024$ 年 $10$ 月発見）の情報もここにある。
RSA 暗号 ― Wikipedia：素因数分解の困難性を安全性の根拠とする公開鍵暗号。