大阪府立大学 生命環境科学域 理学類／理学系研究科 公開セミナー開始

大阪府立大学 生命環境科学域 理学類／理学系研究科 公開セミナー開始

大阪府立大学 生命環境科学域 理学類／理学系研究科では、社会的に関心の高いテーマにそった公開セミナーを毎年開催。13回目にあたる今回は「計算アーキテクチャーと素因数分解」をテーマに開催されました。
会場は大阪府立大学中百舌鳥キャンパスのA12 サイエンスホール。前衛的なアートが飾られるなどモダンな雰囲気の中、数学の最先端に少しでも触れてみようと開場から多くの方々が来場されました。

お昼ご飯を食べ終わり、ちょうどお腹も落ち着いてきた頃に理学系研究科長 溝口 幸司のご挨拶によりセミナーが開始されました。

素因数分解って中学校で習った？

まずイントロダクションで、理学系研究科 川添 充 教授より「素因数分解はなぜ重要なのか？暗号の視点から」という演題で素因数分解について解説いただきました。

2以上の自然数で、1とそれ自身以外に正の約数を持たない数=素数。正の整数をこの素数の積で表すのが素因数分解。さらに素因数分解を用いると最大公約数を導きやすくなることなど、川添先生が算数・数学の先生ならよかったのにと思ってしまうくらいのわかりやすさでお話が進みます。次に素数や素因数分解の歴史です。数学のバイブルと言われているユークリッドの「原論」では、
◯素数は無限に存在する
◯ユークリッドの補題
◯ユークリッドの互除法
これらについての記述がなされていることをご紹介頂き、紀元前の数学世界に連れていっていただきました。
紀元前の数学世界に思いを馳せていると、いきなり赤いアルファベットで「RSA」の文字が。
一気に20世紀のデジタルな世界に引き戻されました。
RSAとは1977年に誕生した公開鍵暗号方式で、実用化第一号の公開鍵暗号なのだそう。1977年にR.Rivest氏、A.Shamir氏（半袖のポロシャツがトレードマーク）、L.Adleman氏の三名によって提唱されたもので彼らの頭文字をとってRSA暗号と命名され、現在でも最も利用されている公開鍵暗号の一つだそうです。

共通鍵暗号方式と公開鍵暗号方式

そもそも暗号とは、特定の人以外には読めないようにメッセージを交換することで、内容を秘匿する技術のこと。

具体的な暗号として、紀元前1世紀のシーザー暗号と16世紀の上杉謙信の暗号、20世紀のエニグマをご紹介頂きました。シーザー暗号はアルファベットを3つ後ろへずらすというシンプルなもの。上杉謙信の暗号は平仮名を七マス四方の表に配置し縦横に数字を割り振り、平文に対応する数字を暗号文とするもので、7マス四方の表が鍵となります。エニグマは第二次世界大戦でドイツ軍が使用したもので、連合国側は解読が大変だったようです。

ご紹介頂いた3つの暗号は「共通鍵暗号方式」と呼ばれ、
◯暗号化と復号に用いられる鍵は同じ。
◯暗号通信を始める前に、鍵を共有する必要がある。
これらの特徴があります。

本題、RSA暗号とは「公開鍵暗号方式」と呼ばれ、
◯暗号化用の鍵と復号用の鍵を分離して、暗号化用の鍵を公開できるようにした暗号
◯事前の「鍵共有」が不要

公開鍵暗号の概念はW. Diffie氏（長髪がトレードマーク）とM. Hellman氏によって提案されました。
この「公開鍵暗号方式」を含め、暗号は様々なところで使われているそうで、無線でつながっているものには暗号が入っているということ。
携帯電話や交通系ICカード、ETCやネット上でのオンライン決済などで暗号が活躍しているのは、わかる気がするのですが、ワイヤレス接続のBluetoothにも暗号化技術が使われているのは、目からウロコでした。よく考えたらわかることなのですが、考える暇もないぐらい、便利な世の中ということでしょうか。

RSA暗号は破られる!?

暗号の世界にどっぷり浸かりきったところで、RSA暗号の概要が解き明かされます。

なんと、公開鍵のNが素因数分解されると、RSA暗号は破られるんですって!!
p,qがわかる→（p-1）（q-1）とeからdが求められる【ユークリッドの互除法】
どれくらい大きな数が素因数分解できるかは、RSA暗号の安全性にとって非常に重要だそうです。
インターネットや便利な決済システムなどの暗号技術が破られるとどれほどの影響がでるのか・・・。ただ、現状では10進法で600桁以上のNが必要とのこと。安心できるのか、できないのか、天文学的数字がよくわからず、お話を聞き終えました。

素因数分解法はRSA暗号を攻撃する武器である

ここからは、大阪府立大学 生命環境科学域 理学類／理学系研究科 公開セミナーのメインテーマ「計算アーキテクチャーと素因数分解」の演題で、富士通研究所 セキュリティ研究所の伊豆哲也先生にご登壇頂きました。伊豆先生は、Trust and Co-creationというスローガンのもと、富士通からの研究依頼を受け、研究成果を返す役割の富士通研究所セキュリティ研究所に所属。現場の生の声を聞けるとあって、会場全体が前のめりに。そんな緊張感のある雰囲気を「先生と呼ばれることがこそばゆい」と、はにかみながら一瞬で柔らかな空気に変えてしまいました。
素因数分解の軽いご説明の後の一言、「素因数分解法はRSA暗号を攻撃する武器である」この一言のインパクトで、素因数分解とRSA暗号との関係がより明白に浮き上がった気がしました。
武器（素因数分解法）の攻撃力 ＜ 防具（RSAの公開鍵N）の防御力のため、素因数分解に時間がかかりすぎ、現在の暗号化システムの安全が確保されているということ。
その素因数分解法の攻撃力を上げるための研究をご紹介いただきました。

様々な素因数分解法

まずはシンプルな分解法「素朴法」です。
小さな素数から順番に割っていくというもの。
◯Nの素因数は必ず√N以下になるので、√N以下の素数で割っていけばよい
◯素数だけを生成するのは大変なので、PCのプログラムでは、代わりに「2と奇数」で割っていくことが多い

この方法の計算時間を見積もると
（仮定）奇数を生成し整数がその奇数で割れるかを計算するのに300クロック必要
■市販のPC（CPU:3GHz）1台は、1秒間に3000000000クロックの処理が可能
＝1秒間に1000万個の奇数による計算が可能（3000000000÷300=10000000）
・20桁までの整数なら10分以内で素因数分解が可能
・40桁までの整数なら159万年で素因数分解が可能
・10桁増えるたびに、計算時間は10000倍に
となり、40桁の素因数分解の答えを見ようと思うと、不老不死にでもならない限り、お目にかかれないようです。
ならば、クラウドならどうだ！？ということで、
■市販のPCを1億台つなげて計算を行うと（クラウドコンピューティング）
・40桁までの整数なら14時間以内で素因数分解が可能
・50桁でも159年以内で素因数分解が可能
・10桁増えるたびに結局、計算時間は10000倍になる
50桁なら、健康に思いっきり、気を使えば答えにお目にかかれるかも・・・・
結局壁にぶち当たってしまいます。

その他にもp法や、p-1法、楕円曲線法、Dixon法、連分数法、2次篩法、数体篩法など、聞いたこともないような方法があるそうです。その中で最も高速な方法として一般数体篩法があり、どれほどの結果が出ているのかということを重点的にお話し頂きました。計算の処理概要については難しいということで割愛（ホッと一安心）。
世界記録としてはRSA768という整数の分解（232桁）があり、様々な叡智の結集で分解するにいたった点、計算時間は1700年コア（600台の計算機で2.5年）かかったこと、この分解によってRSA暗号では617桁以上の整数利用が必須になったことについてお話しいただきました。

一般数体篩法の変遷では、富士通研究所も2005年5月に176桁を分解したこと、ただ、同じ月に破られたことや、その後、2010年以降、素因数分解記録が更新されていないことについて、伊豆先生の見解、
・莫大な費用を使って世界記録を達成する動機が薄い
・アルゴリズムに進展/新規性がなく学術論文になりにくい
・分解の目標となる合成数がない
などをお話頂き、現在までの素因数分解法の限界を感じました。
その後、一般数体篩法のハードウェア化競争にステージが移りますが、
・多くの提案は理論検討だけで実装までには至っていない
・ハードウェア化によるメリットは思ったほど大きくない
などの理由で、停滞している様子も伺えました。

新しい計算機でもっと速く素因数分解ができるのでは？？

既存の計算機（一般数体篩法）での素因数分解が頭打ちの今、どうすれば大きな整数の素因数分解をもっと速くできるのか？
そうです、新しい計算機（四則演算ではない、別の物理現象を用いる）を利用すれば、もっと速い素因数分解法が生まれるのではないか？ ということで、次は新しい計算法のお話です。

①粘菌計算機
粘菌（アメーバ）を使った迷路の抜け道探索で、粘菌が餌を求めて餌と餌の最短距離をつなぐ形に変形する性質（物理現象）を利用し、最短経路を求めるというもの。言葉で聞くと年金の方を思い出してしまったのですが、粘菌＝アメーバの方。面白い性質を示すんですね。
その性質が巡回セールスマン問題解決に使えるのだとか。都市と都市の間で移動するときの経路で最短経路を見つける問題で、虱潰しに計算してしまう既存のPC（計算機）が苦手な分野だそう。シラミよりもアメーバが最短経路探索には適しているようです。ただ、残念ながら素因数分解の計算には適さないそうです。

②スパゲッティ計算
スパゲッティの乾麺の端を揃えるという物理現象を用いた計算で、ソート問題に適しているそうです。
ソート問題とは「5個の異なる整数を小さい順に並べなさい」というもの。
一般的な解法例はバブルソートと言われ、
・上と下を比較
・上が大きければ交換
小さい数が上へ上へ上がっていく様子から、泡に見立ててバブルソートと命名されたとか・・・

・要素数が5個の場合、10回の比較・交換が必要
このソート問題を1回の操作でソートできるのがスパゲッティ計算です。
スパゲッティをまとめて持ち、フラットな台で端を揃えれば、スパゲッティの長さ順が一発でわかります。要素の個数にかかわらず1回の操作でソートが可能です。
ソート自体は1回の操作でいいのですが、スパゲッティの長さを調整するのに手間がかかりそうです。やっぱり素因数分解の計算には使えないみたいです。

③量子計算法
量子計算法とは量子力学（量子素子）を利用した計算。量子素子は0と1を重ね合わせて保持し、3つの素子（3ビット）なら0〜7の値を重ね合わせて保持可能。また、観測すると各素子の値は0または1に定まるという性質を利用する計算です。ただ、いろんな数値を重ね合わせて持てるということは、欲しい値を得る確率を高めたりすることや、多ビット化が難しかったりするので、適当なアルゴリズムを生成する必要がありました。

量子アニーリング計算による素因数分解

そこで登場したのがPeter Shor氏。1994年に量子計算機向けにShorアルゴリズムという素因数分解法を提唱しました。量子計算機が実現すればRSA暗号を素因数分解を用いて効率的に解読することができるようになると、当時の研究者たちの間でにわかに色めき立ったそう。
近年はインテルやIBM、Googleがビットチップやプロセッサ、量子計算機を発表するなど、量子計算機の開発が一気に加速しています。しかし、素因数分解記録は未だに更新されていません。理由としては多量子ビット化に伴うノイズのためにShorアルゴリズムが正しく動作しないのだとか。
量子計算法もまだまだ、発展途中でなかなか思ったように研究が進まない中、量子アニーリング計算が登場しました。
まずは量子がつかない、アニーリング計算の説明から。アニーリングとは熱した金属をゆっくりと冷ますと分子構造が安定するという、焼き鈍し（物理現象）のこと。分子構造が安定=分子のエネルギーが最小というところから最小値を求める計算法として、考え出されてもの。ただ、ニセの最小値も出てくるため、広く使われていなかったそう。そこで、量子テレポーテーションが起こる量子計算機を用いれば最小値を求める確率がより高くなるのではということで、量子アニーリング計算が登場しました。

でも最小値を求められたからって、何かいいことがあるの？という問いに対して、伊豆先生は先回りして、次のスライドで解答されました。
粘菌計算でも紹介頂いた巡回セールスマン問題などの組み合わせ問題を解くことができたり、他にも創薬では新しい有機化合物の効率的探索、がんの放射線治療では、がんの形に合わせた照射方向・量・パターンなどの算出に応用できるようです。
ここでD-Waveという計算機が登場します。カナダのD-Waveという会社が開発したもので、世界初の量子アニーリング計算機として脚光をあびました。もともとは量子計算機をつくりたかったようですが、多量子ビット化がうまくいかず、量子アニーリング計算機開発に方向転換し、世界初となったそうです。正直、これまで生きてきて聞いたこともない会社が世界初で開発したことに驚かされました。スライドでは黒光りする大きなボックスが映し出され、無限の可能性を垣間見ることができました。富士通でも全ての組合せを完全・高速・正確に解くアニーリング計算機「Digital Annealer」を開発しており、創薬や渋滞緩和、生産性向上に活躍してくれそうです。

最後に

現在の素因数分解の研究では量子アニーリング計算機が一番Hotな話題のようで、そんなHotな話題に触れたり、それまでの経緯をお聞きすることができ、少し大げさかもしれませんが感動させていただきました。
会場からの質問で、量子コンピュータ計算機ができれば素因数分解は解けてしまう。そうなったときにはどうするのかという質問がありました。素因数分解の代替の問題として、格子問題などの他の問題が検討され始めているというご解答でした。日頃、気づかなくても身近にある暗号化技術。その根底を覆すようなことが、そう遠くない未来に起こるかしれません。