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

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

09 20210714暗号5

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

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

素数×素数

数Xが素数a,bの積で表されているとします.つまり,x=a・b です(xの素因数分解).桁数にもよりますが,時間とPCがあれば計算可能ですね.

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

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

09 20210712暗号2

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

こで, X≓10200=10100×10100 を取りあげ,試しに 10100 までの素数aについて”困難さ”を確認してみます.ここで,a=2,3,5,7,・・・・・,(10100近くの素数)

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

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

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

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

素数分布

数の個数については,素数定理1~N 間の素数の個数は,およそ,N/logN である」が基本です(logN:自然対数).

例:N=10100 とすると,

logN=log10100=100・log10=230(∵ log10≓2.3)

素数の個数 → N/logN=10100/230=100/23×1097≓4.3×1097

スパコンの性能

09 20210713暗号3

パコン富岳の計算処理能力 → 44.2京 回/秒,つまり,1秒間で 44.2×1016 回 です(‘21.6).※計算処理能力の実際は,小数点以下15桁の数による四則演算を用いるとのこと.

(前述)素数の個数 → 4.3×1097 くらい

巨大な整数の素因数分解ですが,条件を極端に単純化して,”必要時間”を把握しましょう.

計算時間

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

そこで,X≓10200  を,素数aで割る際の難易度がすべて同一と仮定します(したがって,各計算時間も同じ).ここで,a=2,3,5,7,・・・・・,(10100近くの素数) であり,合計4.3×1097 

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

すると

計算時間 → (4.3×1097)÷(44.2×1016)=9.73×1079(秒) です.1年=365×24×3600(秒)≓3.15×107(秒)ですから,単位は年が相当でしょう.

(9.73×1079)÷(3.15×107)≓3.1×1072(年)

ント約 3.1×1072(年) ※となります.この数を歴史の中に置いてみましょう.縄文時代は概ね104年前ころの始まりです・・・想像を絶する数値ですね.というか,宇宙が誕生するはるか前です.

09 20210714暗号4

の場合,有限とは言え,素数列が果てしなく延々と続く光景が思い浮かばれませんか?

※素因数分解の実際は,素数一つ一つで割り算するような呑気な方法ではなく,極めて有効な手法を用いるとのこと.が,それでも非常に長い時間がかかるようです.

あるサイトでは10億(109)年という説明(cf.地球の誕生:46億年前),筑波大計算科学・スーパーコンピュータサイトでは,232桁の整数で3年(これまでの比較では極端に短い!しかし,暗号解読にはやはり長い!)という説明があります.

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

<補足>

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

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

  

 

次に

なるほど算数&数学 - にほんブログ村

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です