aRiSA

第24話 完全なる素数学者

　柴山は田中からプログラミングのレクチャーを受けたあと、自宅で簡単に夕飯を済ませて、Pythonに様々な処理をさせていた。女子大生の夜の過ごし方としてはかなり異質である。

「凄い。田中さんが教えてくれたSymPyって、色々できるのね。大学入試でやるような積分計算なんて一発だわ」

　SymPyは記号計算に特化したPythonのライブラリである。Pythonの標準ライブラリで 2 の平方根を利用する場合、次のようにして math モジュールを用いる。

　　　from math import sqrt

　　　a ＝ sqrt(2)

　　　print(a**2)

このプログラムを実行すれば、整数の 2 が表示されるのを期待するが、実際は

　　　2.0000000000000004

という 2 に限りなく近い小数が返ってくる。これは、 a に

　　　1.4142135623730951

という近似値が代入されているためだ。Pythonに限らず一般的なプログラミング言語は、無理数を小数の近似値として取り扱う。一方で、sympyモジュールのsqrtを用いて

　　　from sympy import sqrt

　　　a ＝ sqrt(2)

　　　print(a**2)

とすると、整数の 2 が返ってくる。SymPyにおいて 2 の平方根は、近似値ではなく正真正銘 2 乗するとぴったり 2 になる数として扱われるのである。もし、近似値が欲しければ、 sympy モジュールの N 関数を用いればよい。

　柴山はインターネット上にあるSymPyのドキュメントを読みながら、素数に関する機能を調べていた。

「素数判定は isprime 関数か……」

　　　In [1]: def str2int(s):

　　　　　　　　　return int(s.encode().hex(), 16)

　　　　　　　def int2str(n):

　　　　　　　　　return n.to_bytes((n.bit_length() ＋ 7) // 8, 'big').decode()

　　　In [2]: from sympy import isprime

　　　In [3]: p, q ＝ str2int('すずき'), str2int('ありさ')

　　　In [4]: isrpime(p), isprime(q)

　　　Out[4]: (True, True)

「やっぱりね……確か素因数分解をするには……」

　　　In [5]: from sympy import factorint

　　　In [6]: n ＝ p*q

　　　　　　　factorint(n)

「あれ？　結構時間かかるなー」

　　　Out[6]: {4196743176259748725141: 1, 4196749650180186538381: 1}

「大体30秒くらいかな？　田中さんはPythonはそんなに処理は速くないって言っていたけど、この桁数でこれだけ時間かかるってことは、700桁以上の素因数分解は……想像もできないわ」

　　　In [7]: isprime(str2int('先輩'))

　　　Out[7]: True

「ふふ、やっぱり。さすが先輩だわー」

　柴山は考えていた。

「先輩は……素数。素数学者？　もしかして……」

　素数学者とは、井上昭一がTwitterで発言していた謎の言い回しである。素数に関する目覚ましい結果を残した数学者、という説があるが、基準が不明瞭である。柴山の調べによると、井上は以下のような発言をしている。

「ユークリッドやアルキメデスは素数学者ではないが、エラトステネスは素数学者のようだ」

「まあ、当然だが、素数学者は少ないみたいだ」

「おお、ラグランジュも一応素数学者。しかしちょっと弱いかな」

「残念ながらオイラーは素数学者ではない」

「さすがは数学王。ガウスは完璧な素数学者だ」

「ざっと有名な数学者を調べていたが、素数学者はこれくらいかな。残念ながら私は素数学者ではないようだ（笑）」

　慈道によれば、フェルマーやオイラーなど、素数に関する目覚ましい定理を残している者たちが素数学者ではないことには違和感があるという。

　柴山は思うことがあってなにかに取り憑かれたようにタイピングを行う。

　　　In [8]: isprime(str2int('井上昭一'))

　　　Out[8]: False

　　　In [9]: isprime(str2int('Shoichi Inoue'))

　　　Out[9]: False

　　　In [10]: isprime(str2int('ShoichiInoue'))

　　　Out[10]: False

　　　In [11]: isprime(str2int('SHOICHI INOUE'))

　　　Out[11]: False

　　　In [12]: isprime(str2int('SHOICHIINOUE'))

　　　Out[12]: False

　　　In [13]: isprime(str2int('ShoichiInoue'))

　　　Out[13]: False

　　　In [14]: isprime(str2int('shoichiinoue'))

　　　Out[14]: False

「井上昭一は、素数学者ではない……もしかしてこういうこと？　確か、エラトステネスは素数学者だって……」

　　　In [15]: isprime(str2int('エラトステネス'))

　　　Out[15]: False

「うーん。エラトステネスのスペルは……」

　柴山はエラトステネスのWikipediaの記事をみる。

　　　In [16]: isprime(str2int('Eratosthenes'))

　　　Out[16]: False

「違うか……いや、もしかしたら」

　　　In [17]: isprime(str2int('ERATOSTHENES'))

　　　Out[17]: True

「あ！　素数！　エラトステネスは素数学者……」

　　　In [18]: isprime(str2int('EUCLID'))

　　　Out[18]: False

　　　In [19]: isprime(str2int('ARCHIMEDES'))

　　　Out[19]: False

「井上先生によればユークリッドやアルキメデスは素数学者ではない……確かラグランジュは素数学者だった」

　　　In [20]: isprime(str2int('LAGRANGE'))

　　　Out[20]: True

「なーるほど。もしかして謎は解けたかも！」

　　　In [21]: isprime(str2int('GAUSS'))

　　　Out[21]: False

「嘘……ガウスは完璧な素数学者のはずなのに……なんで……？」

　柴山は記録してある井上のツイートをよく読んだ。

「ラグランジュは弱い……ガウスは完璧……」

　　　In [22]: str2int('LAGRANGE')

　　　Out[22]: 5494751438977255237

「これじゃ弱い……桁数の問題かな。暗号に使うには小さすぎる……」

　柴山は急いでWikipediaのガウスの記事を開く。

「カール・フリードリヒ・ガウス」

　　　In [23]: str2int('CARL FRIEDRICH GAUSS')

　　　Out[23]: 383959099194908454567263877940525258923343958867

「300桁はないけど、普通に大きいよね」

　　　In [24]: isprime(str2int('CARL FRIEDRICH GAUSS'))

　　　Out[24]: False

「ち、違うのー？」

　柴山はキーボードの上に伏せて唸るが、すぐにむくりと起き上がる。

「そういえば、あの電子式の金庫、小文字が打てなかったし、スペースも打てなかった……」

　　　In [25]: isprime(str2int('CARLFRIEDRICHGAUSS'))

　　　Out[25]: True

「で、出た……！　完璧な素数学者。フルネームの文字コードが素数になっている！　凄い偶然だけど、ガウスマニアの井上先生だったら絶対に絡めたくるなる、よね」

　　　In [26]: str2int('CARLFRIEDRICHGAUSS')

　　　Out[26]: 5858750904014301194923422446599664605418323

「それに結構大きいし……えっと、第2の試練の公開鍵 N は……」

　柴山はメモアプリからコピーアンドペーストを行う。

　　　In [27]: N ＝ 1128978236891718557718481606113687635358

　　　　　　　　　1054185495904208921003522878546092100008

　　　　　　　　　7489409479235053183143635448869112004017

　　　　　　　　　6364681414935884605195103101991754640555

　　　　　　　　　3820883293118646721952726956079780271759

　　　　　　　　　0171727957074228889138072562945701554568

　　　　　　　　　1728829500071936534693122476314215667414

　　　　　　　　　5767444022112763801524330774010639710291

　　　　　　　　　5888503707108094390044681881956451533508

　　　　　　　　　6438216386211001155444150875108790746746

　　　　　　　　　4723556995877696435933681447393826125887

　　　　　　　　　7037155053339228856637297926719854403000

　　　　　　　　　3217396143937836026709895010219447609412

　　　　　　　　　7551680782422933535609844079551131147930

　　　　　　　　　4876174117493347728618426639214052169078

　　　　　　　　　0166559881752751821603521251475453588671

　　　　　　　　　2122319846085439977927045979125784009637

　　　　　　　　　0117361513473975534555907186442467587972

　　　　　　　　　86460809

「さて……お願い！」

　柴山は祈りながら次の処理をさせる。

　　　In [28]: p ＝ str2int('CARLFRIEDRICHGAUSS')

　　　In [29]: N/p

　　　Out[29]: OverflowError: integer division result too large for a float

「桁が大きすぎる？　参ったなあ。あ、違う。確か / は小数にしちゃうんだった。商と余りを求めるには divmod だった」

　　　In [30]: divmod(N, p)

　　　Out[30]: (1926994773097734562656929295220491737282

　　　　　　　0254135124423561975037956045205856733759

　　　　　　　5303328466380167493272058251645008821995

　　　　　　　8434374159158678947584837120000724196395

　　　　　　　7978363898522340943453558421924149143585

　　　　　　　2697972529577481968461335865670030294340

　　　　　　　0333820998819503190862783572003281469506

　　　　　　　1442813183086751741226452163646308986309

　　　　　　　0246500484552031059054518840189257106970

　　　　　　　8263005284405173552652673700792040612698

　　　　　　　2371318301750708466048719467000070294161

　　　　　　　3149149294088363548304949436623846690696

　　　　　　　2314768654834268543340802078864837217237

　　　　　　　9199554701544673660818586490410118431704

　　　　　　　0718974289227428357223374145277712575249

　　　　　　　9121482138917708645565066742375894621387

　　　　　　　8454033173429261225809472817080764826383

　　　　　　　80083, 0)

柴山は自分の目を疑った。

「あ……！　これって余りが 0 ってことだよね？

　思わず乗り出して液晶の画面に瞳を限りなく近づける。

「や、やったわ……素因数分解ができた……」

　柴山の表情には驚きと笑いが混在していた。

　　　In [31]: q ＝ N//p

　　　　　　　isprime(q)

　　　Out[31]: True

　　　In [32]: N ＝ ＝ p*q

　　　Out[32]: True

「間違いない。 q も素数。この p と q が、あの暗号の秘密鍵……す、すぐに電話しないと！」

　柴山は無意識に慈道へコールした。

「おかけになった電話は、現在電源が入っていないか電波の届かないところに……」

　柴山は時計を確認した。

「九時かー。あーもう！　めんどくさい！」

　慈道は夜八時以降は携帯の電源を切って自分だけの世界に引きこもる習慣を続けている。

「とりあえずアリサに連絡っと」

　柴山は以下のようなメッセージを送った。

「秘密鍵が分かったから、明日、井上先生の家に行ってもいい？」

　五分ほどで返信され、次のようなやりとりがスピーディに行われた。

「本当ですか？　凄いです！　あ、だけど。明日は予定があるので……明後日でも構いませんか？」

「日曜ね。オッケー。今、先輩と連絡が付かないけど、絶対に行かせるから」

「了解しました」

　柴山は歓喜の雄叫びを内にしまって、秘密鍵 d の計算を始めた。それには、拡張ユークリッド互除法を実装する必要があるので、柴山にとっていいプログラミングの勉強となった。