暗号解読：スパコンで素因数分解は”一瞬”か？

暗号アルゴリズムは，桁数の大きい数の素因数分解が難しいことをベースにしています．しかし，スーパーコンピューター富岳(世界一の性能. ‘21.6現在）にとって，素因数分解などまったく問題にせず，”瞬殺“解答となるのでは？と思う方いますよね．

数年前，素因数分解の困難性への素朴な疑問，つまり，「スパコンなら一瞬即答ではないか」について，Ｋ氏（現在，ｈ高校長）に相談したところ，氏の学部時代の友人である方（関西方面の大学教授）から氏経由で本テーマに関するコメントを頂戴しました．

本稿は，そのコメントを基に作成した次第です．

素数×素数

整数Xが素数a,bの積で表されているとします．つまり，x=a･b です（ｘの素因数分解）．桁数にもよりますが，時間とPCがあれば計算可能ですね．

逆に，ｘからa,bを求めてみましょう．たとえば，91 なら，7×13 と即，求められます．しかし，3242249 が 3559×911 と分解されることを見出すのは容易ではないでしょう（なお，素因数分解の一意性により,3559×911 以外の解はなし）．

実際，素数列は｛2,3,5,7 ･･･}と続き，素数は無限にあることが証明されています（「学習の進んだ子供(part2)」参照）．ただし，素数列に規則性はなく，式化できないために，先程の例でも，911にたどり着くまでが大変です．

暗号理論は，この”素因数分解の困難さ”の上に構築されており，最新の超高速コンピューターをもってしても”超困難”とのこと．でも”たかが因数分解”です．実感が湧きますか？

ここで, X≓10²⁰⁰=10¹⁰⁰×10¹⁰⁰ を取りあげ，試しに 10¹⁰⁰ までの素数aについて”困難さ”を確認してみます．ここで，a=2,3,5,7,･････,(10¹⁰⁰近くの素数)

各素数aでXを割り算し，割り切れるかどうかを求めます．

ここで， X=(素数)×(素数)の整数であり，あらかじめ設定しておきます．← この設定自体が大変なコトなのですが，割り算に比べるとはるかにラクとのこと．

ここで気になる点．①対象となる素数はどれくらいあるのか　②a,b自体が素数であることはどうやって判定するのか　の２点です．

②「素数判定」についてですが，本稿では指摘だけにしておきます．意外なことに，素因数分解と比して困難度ははるかに低いからです（諸文献より）．

素数分布

素数の個数については，素数定理「1~N 間の素数の個数は，およそ，N/logN である」が基本です（logN:自然対数）．

例：N=10¹⁰⁰ とすると，

logN=log10¹⁰⁰=100･log10=230(∵ log10≓2.3)

素数の個数 → N/logN=10¹⁰⁰/230=100/23×10⁹⁷≓4.3×10⁹⁷

スパコンの性能

計算時間

割り算には”超簡単”もあればその逆もあります．

そこで，X≓10²⁰⁰  を，素数aで割る際の難易度がすべて同一と仮定します（したがって，各計算時間も同じ）．ここで，a=2,3,5,7,･････,(10¹⁰⁰近くの素数) であり，合計4.3×10⁹⁷ 個 

富岳の計算能力 → 1秒あたり44.2京回=44.2×10¹⁶ 回/秒

すると

計算時間 → (4.3×10⁹⁷)÷(44.2×10¹⁶)=9.73×10⁷⁹(秒) です．1年=365×24×3600(秒)≓3.15×10⁷(秒)ですから，単位は年が相当でしょう．

(9.73×10⁷⁹)÷(3.15×10⁷)≓3.1×10⁷²(年)

ナント約 3.1×10⁷²(年) ※となります．この数を歴史の中に置いてみましょう．縄文時代は概ね10⁴年前ころの始まりです･･･想像を絶する数値ですね．というか，宇宙が誕生するはるか前です．

このように，暗号解読の前には素因数分解という”素朴かつ高い壁”が立ちはだかっています．が，「今のところ」のようです．将来も安全とは限りません。コンピューターの性能向上や、新しいアルゴリズムの開発によって、暗号が解読されてしまう可能性も大いにありそうですね．

＜補足＞

■ 次回テーマは，「ねじれの位置」（予定）です．空間図形の基礎にもなる”ねじれの位置”ですが，「問題のための問題」に成り下がっていませんか？

■ にほんブログ村のバナーをclickしていだだければ幸いです(最初:左，次:右).