13. 素因数分解の難しさ

「素因数分解」 は、中学生三年生で習うはずです。 ある数が与えられたら、その数と 1 でしか割りきることができない 2 以上の整数…すなわち素数を使った掛け算の式に分解することです。 例えば、 33 なら 3×11 という式に分解できますね。 3 も 11 もそれぞれ素数ですよね。

あら、そんな方法があるのなら、法とする数 P×Q = 33 を公開してしまえば、誰にでも P=3, Q=11 であることが分かってしまいまいますョ…。 そして公開する鍵 E は公開されてるから秘密の鍵 D を求められてしまいます。う〜ん、これは困りましたね…。 でもこの 33 の素因数分解、 あなたはどのような方法で 3×11 に分解できることが分かったのですか？

実はこれ、人間の勘と長年の経験によるところが非常に大きいのです。 その証拠に、それでは6887はどう素因数分解されますか？ これも２つの素数に分解できるのですが、 一体どうしたら分解できるかなんてきっと思い付かないでしょう。 思い付いたとして、きっと2 から順に 3, 5 ...って 割れないかどうか順に試してみるくらいがオチじゃないですか？

それもそのはず、なんと現在のところ巨大な 二つの素数を掛け合わせた数を素因数分解する 効率的な方法が見つかっていないのです…。 つまり二つの素数 P=3 と Q=11 を掛けて P×Q = 3×11 = 33 を求めることは簡単にできますが、逆に掛けた結果の P×Q = 33 から P と Q ( 3 と 11 ) を知ることは極めて難しいのです。これが重要なのです。 6887 を素因数分解できなかったのは、 決してあなたの頭が悪かったからではないのです。 ちなみにこれは 71 と 97 に素因数分解できます。 実際に掛けてみて下さい、71 と 97 を掛けて 6887 を求める方は簡単ですから。

先ほどの ＲＳＡ暗号 は 試しに P=3, Q=11 で P×Q = 33 という小さな数で行ったために P×Q = 33 から P=3 と Q=11 を割り出せてしまいましたが、 これが巨大な素数を掛けたものとなると決して割り出せなくなってしまうのです。 この結果、法とする数 ( P×Q ） と 公開鍵 E を公開してしまっても、 P, Q を使って秘密鍵 D を求めた本人以外に、秘密鍵 D を知られずに済むのです。 ＲＳＡ暗号は、暗号のしくみは 「奇跡が起きるべき乗数」 に、 そして安全性はこの素因数分解の難しさによって保証されているのです。