素因数分解
壊せない建物は無い。壊すのに宇宙の寿命より長くかかる建物があるだけだ。
〜 素因数分解 について、全日本整数解体業協会 会長
素因数分解(そいんすうぶんかい、英: prime factorization)とは、数という建物を、それ以上ばらせない部材である素数になるまで壊す工事のことである。古代ギリシアに始まる世界最古の解体業で、日本では今も毎年およそ 100 万人の中学 1 年生が、資格を持たないまま現場に出ている。

工事の手順は決まっている。建物から一番小さい部材を外せるだけ外し、外れなくなったら次に小さい部材に移る。たとえば 12 を壊すと、2 が二本と 3 が一本出てくる。現場ではこれを「22×3」と書き、廃材の伝票にする。伝票は検査のときに掛け算で組み立て直され、元の建物に戻らなければ、現場の責任者はもう一度壊し直しになる。
この業界でいちばん大事な決まりは、どの業者がどの順番で壊しても、出てくる部材の種類と本数は必ず同じになる、ということである。これを算術の基本定理という。おかげで見積もりがどの業者でも同じになり、この業界は、建設業界でただ一つ、談合をする理由が無い業界として知られている。
1 は建物ではなく更地なので、工事の対象にならない。昔は 1 を部材の名簿に載せる業者もいたが、そうするとどの建物からも 1 がいくらでも出てきて、伝票が一枚に収まらなくなった。そこで業界は 1 を名簿から外した。今でも、更地にいくら重機を入れても何も出てこない。見積書だけは出てくる。

紀元前 300 年ごろ、エウクレイデスが業界でいちばん古い工法書『原論』をまとめた。その中で、部材の種類が無限にあることが証明され、業界は仕事が尽きないことが約束された。続く紀元前 3 世紀には、エラトステネスが篩い分け機を作った。数を一列に並べ、2 の倍数、3 の倍数と順にふるい落として、残ったものを部材として出荷する仕組みである。篩い分け機は 100 までなら手で回せるが、それより先は、回す人の人生のほうが先に終わる。
17 世紀、フェルマーは、22n+1 の形の建物はどれも部材そのものなので壊せない、と保証した。1732 年、オイラーがその五番目にあたる 4294967297 に手をかけ、641 と 6700417 に分けた。フェルマーは 1665 年に亡くなっていたので、どこからも苦情は来なかった。
1801 年、ガウスが 24 歳で『整数論』を出し、どう壊しても同じ部材になることを、初めてきちんと証明した。これで業界の決まりが、口約束から契約書になった。
1903 年 10 月、アメリカ数学会の会合で、フランク・ネルソン・コールが壇上に上がった。コールは一言も話さないまま、黒板の左に 267−1 を計算して 147573952589676412927 と書き、右に 193707721×761838257287 を筆算して、同じ数になるのを見せた。会場は立ち上がって拍手をした。あとで、この工事に何日かかったのか聞かれたコールは、「3 年分の日曜日」と答えた。

1977 年、リベスト、シャミア、エーデルマンの 3 人は、壊すのに手間がかかる建物は、そのまま金庫に使えると気づいた。大きな部材を二本つなげた建物を誰でも見られるように置き、二本の部材が何かを知っている人だけが中身を出せるようにする。これが RSA暗号である。今ではネット銀行、通信販売、確定申告の電子申告まで、世の中の大事な扉の多くが「壊すのが面倒だから大丈夫」という理由で閉まっている。
同じ年、マーティン・ガードナーは雑誌のコラムに 129 桁の建物を載せ、壊せた人には中の言葉を渡すと約束した。リベストは、壊すのにおよそ 4 京年かかると見積もった。1994 年、世界の約 600 人のボランティアが約 1600 台のコンピュータを持ち寄り、8 か月ほどで壊し終えた。4 京年の見積もりは 17 年で済んだ。中から出てきたのは「魔法の言葉は神経質なヒゲワシ」という一文だった。
その後、建物はだんだん大きくなった。2020 年には 250 桁の建物が壊されたが、使った計算はおよそ 2700 CPU コア年で、パソコン一台なら縄文時代から休まず働いてやっと終わる量である。工事が終わったと知らされた金庫の持ち主たちは、すぐに金庫をもっと大きく建て直した。業界ではこれを「いたちごっこ」と呼ばず、「受注の安定」と呼んでいる。

1994 年、ピーター・ショアは、量子コンピュータという新型重機を使えば、大きな建物でもすぐに壊せることを理論で示した。業界は大騒ぎになり、金庫の持ち主たちは青ざめた。
2001 年、IBM は実際にこの重機を動かし、15 を 3 と 5 に分けることに成功した。2012 年には 21 を 3 と 7 に分けた。中学 1 年生なら 10 秒でできる工事を、世界の研究所が 11 年かけて一歩ずつ進めていることになる。業界紙は毎年のように「RSA 崩壊まであと一歩」と書いており、その一歩は、2026 年の今も同じ場所にある。
日本では長いあいだ、この工事は中学 3 年で習うことになっていた。2021 年度に学習指導要領が変わってから中学 1 年に下ろされ、現場の働き手はいきなり 2 歳若くなった。人手不足の業界がよくやる手である。
毎年 1 月になると、全国の塾講師と数学の先生は、その年の西暦を壊して、年賀状と入試問題に使う。2025 年は 34×52 で、45 の 2 乗でもあり、問題を作る人にとっては大豊作の年だった。2026 年は 2×1013 で、部材が二本しか出ず、出題者たちは肩を落とした。2027 年はそれ自体が素数で、まったく壊せない。出題者は「2027 が素数であることを示せ」と出して、それで手を打つ見込みである。
現場では、部材だと思って運び込んだものが、実は壊せる建物だった、という事故がよく起きる。中でも有名なのは、大数学者グロタンディークが部材の例に 57 を挙げたという話で、57 は 3×19 である。この話は「グロタンディーク素数」と呼ばれ、新人研修で必ず話される。57 を部材として運び込んだ現場の責任者は、どれほど偉くても始末書を書く。
素因数分解は、工法が 2000 年あまりほとんど変わっていない、珍しい業界である。仕事は簡単なものから始まり、少しずつ大きくなり、ある大きさを過ぎると、急に誰にもできなくなる。そして、誰にもできないことを売り物にした金庫が世界中に建てられた。多くの専門家は、壊せないことを当てにして経済を回すのは、いちばん安心な方法ではないかもしれない、と考えている。ただ、ほかに良い方法を思いついた専門家もまだいない。