第3回 素因子分解と暗号|理工ミニレクチャー
和田秀男(わだひでお)
上智大学理工学部教授 理学博士
専門は整数論
先生、私は理工系に進みたいと思っていますが、皆が理工系に進むと理屈っぽくなり、論理ばかり大切にして、冷たい人間になってしまう、と言うのですが、どうしたらよいでしょうか。
論理とは、心の情熱を相手に正確に伝える手段にすぎないのだよ。興奮して話しても、自分の思っていることは相手に伝わらない。だから少し心を冷やして、論理的にはなさなければいけない。それに、論理的に話さなければ、気が狂っていると思われてしまう。
情熱って素敵な言葉だわ。
情熱が無く、論理ばかりを大切にすると、理屈っぽくなるのさ。それに、情熱が無く、心を冷やして話せば、本当に心が冷たくなってしまう。
なるほど、心が晴れたわ。興味あるものを追い求めればよいのね。そこで質問したいのですが、このごろパソコンを使っていると、暗号化しなければいけない、という記事をよく読むのですが、暗号化ってどうするのですか。よくスパイが使っている暗号表を使うのですか。
暗号表を盗まれると、暗号が解けてしまう。だからパソコンでは暗号表を皆に公開するのさ。私のところに暗号を送るには、この暗号表を使いなさい、と公開するのさ。
変ね。暗号表を公開したら、暗号は解けてしまうでしょう。先生の言うことは論理的でないわ。
もちろん特別に工夫された暗号表で、暗号化することは誰にでも出来るけれど、暗号化されたものを元に戻すのは、暗号表を作った人にしか出来ないのだよ。
そんな暗号表ってあるのかしら。信じられない。
たとえば p と q を2つの100桁ほどの素数とし、n をこの2つの素数の積 pq として、n を暗号表として公開するのだよ。ただし、p と q は公開しない。p と q がわからなければ、暗号化されたものは、元に戻せない。そのような暗号化があるのだよ
n がどうして暗号表なのか、さっぱりわからないわ。それに、n を公開すれば、コンピュータを使えば、素因子分解して、p や q はすぐわかってしまうのではないかしら。
200桁ほどの大きな n は現在のコンピュータ技術では、素数でないことは、すぐ判定できるけれど、素因子分解するのは、100年かかっても出来ないのだよ。
素因子分解しなくても、素数でないとわかるなんて、変ね。
たとえば、n が 2 以外の素数ならば、2n-1 を n で割ると、1余るのだよ。そのような定理がある。だから対偶をとれば、、余りが、1でなければ、n は素数でないと分かる。
余りが1のときは、どうするのかしら。n は素数かしら。逆必ずしも真ならず、というから、判定できないわ。
まいった! 実はもっと複雑な判定法があって、必ず素数か合成数かわかるのだよ。
そんな不思議な判定法があるなら、素因子分解する不思議な方法がないかしら。
いま世界中の暗号学者がそのような不思議な方法を探しているのだよ。もし見つかれば、多くの暗号文が解かれてしまう! たとえば楕円曲線法というのがあって、だいぶ大きな数も素因子分解されてしまう。
放物線、双曲線と楕円はよく習うわ。
楕円曲線は楕円と違うのだよ。たとえば、
y2=(x+5)(x-1)(x-4)
というような曲線だ。下の図のようになる。
貝殻と双曲線のようね。
その曲線の上のどんな3点 P, Q, R にたいしても、不思議な性質がある。P と Q を通る直線が、曲線とまたぶつかる点を P*Q とし、x 軸に対して対称な点を P+Q と名付ける。
妙な名前ですね。
深い意味があるのだけれど、先に進もう。同じように Q+R を求める。さて、ここで不思議なことが起こる。P と Q+R を結ぶ直線と R と P+Q を結ぶ直線は、曲線上でぶつかるのだよ。
偶然かしら。
そうではなく、ちゃんと証明できるのだよ。どんな3点から始めても最後は曲線上でぶつかるなんて不思議だろう。これを素因子分解に利用することができるのだよ。
どのように利用するのかしら。それに最初の疑問だった n が暗号表であるということの意味がまだわからないわ。
おや、忘れていなかったね。その答えは、きみが、理工学部に入って、もう少し数学を勉強してからにしよう。