サマーウォーズ：曜日の求め方とか2056桁の暗号とかの解説

本エントリは現在上映中の映画『サマーウォーズ』のネタバレを含む可能性があるので、未見の人は注意されたい。

主人公の健二が数学オリンピック代表候補であるという設定、最初に健二がShorのアルゴリズムに関する教科書を読んでいるのを見て、サイモン・シンが描き出した迫真のドキュメンタリー『フェルマーの最終定理 』*1ばりの展開が待っているのかと思いきや、まともな数学的要素は皆無で肩すかしを食らってしまった。

気を取り直して、本エントリでは『サマーウォーズ』における数少ない数学的要素を取り上げたい。なお、無粋なツッコミは無用だという人は読まない方が良いだろう。

誕生日の曜日の求め方

さて、夏希先輩の誕生日、1992年7月19日は何曜日か。劇中で健二はモジュロ演算(mod)を用いて一瞬で日曜日だと回答していたが、その間にどのような演算がなされていたのか見てみよう。

曜日換算を実現するために、ツェラーの公式が知られている。求めたい日の年の千位と百位の連続の数字(例えば2310年ならば23)をJ、年の下2桁(年 mod 100)をK、月をm、日をq、曜日をhとする（ただし求めたい日の月が1月、2月の場合はそれぞれ前年の13月、14月とする）と、曜日は次で与えられる（x以下で最大の整数をで表す）。

　　

modはモジュロ演算（剰余演算）であり、余りを求める演算子である。ここでは7で割った余りを求める事となるが、余りhが0なら土曜日、1なら日曜日、2なら月曜日、……、6なら金曜日となる。

夏希先輩の誕生日1992年7月19日を考える。J=19, K=92, m=7, q=19を代入すると、

　　
　　
　　
　　

つまり夏希先輩の誕生日は日曜日だと言うことがわかる。演算量としては（筆者には当然できないが）暗算が可能な範囲だ。また、ツェラーの公式を知らなくても、特定の日の曜日を予め暗記しておけば、その日との差の日数を計算しmod 7を求めることで曜日を知ることもできる*2。実際、サヴァン症候群の患者であるキム・ピークは、生年月日を言えばそれが何曜日であるか即座に答えることができるという。そのため健二がこの程度の暗算能力を持っていてもおかしくはない。

健二が解いた暗号の謎

健二が最初に解いた暗号は2056桁の10進数の羅列であった*3。なぜ2048ではなく2056なのか理解に苦しむ*4が、2048bitと256bitを混ぜてしまったのだろうか。数字だけ並べられて"Solve Me"と言われても、普通は何を解くのかさっぱり分からないと思うが、健二がShorの因数分解アルゴリズムの教科書を見ていたことから、おそらく2056桁の数字をp*qの因数に分解するのだと思われる*5。

現在インターネットで広く使われるRSA暗号においては、1024-4096bit（10進数で300-1000桁程度）の鍵が利用されている（RSA-640は2005年に解読されたため、最低でも1024bit以上を利用すべきである）。RSA暗号の安全性は素因数分解の困難性に依っており、素因数分解に成功すれば暗号を解くことができる。健二は2056桁の数字の素因数分解に成功したのだろうか？

CRYPTECが2006年度に発行した「CRYPTREC Report 2006 暗号技術監視委員会報告書」において1024bitRSA暗号の安全性についての調査を行っているが、そこでは当時の素因数分解世界記録保持者の一人であるKleinjung 博士に評価依頼し、1536bit, 2048bitの素因数分解についてAtholon64 2.2GHzのPCを基準にして計算時間を見積もっている*6。

ここでRSA-2048は次のような数字だ。健二の携帯電話に送られてきたメールと同様に数字の羅列となっている。ただしたった617桁であり、健二が解いた2056桁の1/3に満たない。

RSA-2048 = 25195908475657893494027183240048398571429282126204032027777137836043662020

           70759555626401852588078440691829064124951508218929855914917618450280848912

           00728449926873928072877767359714183472702618963750149718246911650776133798

           59095700097330459748808428401797429100642458691817195118746121515172654632

           28221686998754918242243363725908514186546204357679842338718477444792073993

           42365848238242811981638150106748104516603773060562016196762561338441436038

           33904414952634432190114657544454178424020924616515723350778707749817125772

           46796292638635637328991215483143816789988504044536402352738195137863656439

           1212010397122822120720357

この数字を素因数分解するための計算時間見積もりを次のグラフに示す。

Athlon2.2GHzのPCを連続稼働させて2048bit（10進数で617桁）の因数分解にかかる時間はおおよそ10,000,000,000,000,000年だ*7。つまり10進数2056桁の因数分解は手計算では何兆年かかっても解けない。一晩で手計算なんてとんでもない。暗算なんてできっこない。鼻血をだすぐらいじゃ絶対無理である。

よい映画だけに、まともな科学考証がなされてないことが実に惜しい。誰かアドバイスできる人はいなかったのか。

関連アイテム

サマーウォーズ [Blu-ray]

サマーウォーズ [DVD]

*1:『フェルマーの最終定理 』は実に面白い小説で、以前も取り上げたが、筆者のお気に入りである。当blogの常連さんなら嗜好的に読んで損はないはずだ。もっとも映画の内容的には、同じくサイモン・シンの『暗号解読〈上〉』『暗号解読 〈下巻〉』の方がマッチしている。本エントリで述べる公開鍵暗号方式にも言及があるし、エニグマ暗号機の解説などは知的好奇心をくすぐられる。こちらもオススメである。

*2:2000年1月1日が土曜日だと知っているとする。閏年以外は1年で1日、曜日がずれる（365 mod 7 = 1）ので1992年1月1日のオフセットは-8-2（1992年と1996年の2回の閏年分）で-10となる。1月3月5月7月8月10月12月の大の月は3日、曜日がずれ(31 mod 7 = 3)、4月6月9月11月は2日、曜日がずれる。2月は閏年以外は曜日がずれず、閏年には1日ずれる。とすると1992年9月1日のオフセットは-10+3+1+3+2+3+2で4となり、1日から19日まで18日分進めて22日。7で割ると1余るため、1992年7月19日は土曜日から1日進めて日曜日となるわけだ。さらに4月1日の曜日が7月1日の曜日と同じであり、また9月1日の曜日と12月1日の曜日が同じ事を知っていればいくつかの計算を省略することも可能だ。

*3:コミック版によれば、最初に解いたのが2056桁、2回目以降は516桁らしい。

*4:仮に10進数の桁数が2のべき乗になっても意味はないが。

*5:それにしては健二が入力した答えが10進数ではなくアルファベットが混じっている点、公開鍵は流出するとは言わない点（そもそも公開するものだ）、そもそもShorのアルゴリズムは量子コンピュータで利用するものであり、通常のコンピュータや手計算、暗算で用いるものではない点など納得できない点が多い。そのため本エントリの考察は的外れで全然別の暗号である可能性ももちろん存在する。未読のガイドブックやノベライズ版に何らかの設定があるのだろうか。

*6:T. Kleinjung, “Evaluation of Complexity of Mathematical Algorithms,” CRYPTREC technical report No.0601 in FY2006, 2007

*7:利用が推奨される暗号強度は世界最高のスーパーコンピュータの性能が今後10年20年のスパンで拡大したと仮定して、それでも実用的な時間で解けないように設定される。健二の解いた暗号が何であれ、手計算で一晩で解けるようなモノは決して暗号とは言わない。