|
 |
 |
|
講師： 織田孝幸（おだ・たかゆき）
日時： 2006年７月２７日 |
|
| 数学カフェ 「素数」 |
|
 |
|
 |
＞＞＞ 因数分解するための時間は、どれくらいかかるんですか。
寺杣： あるコンピュータの会社（RＳA Security Inc.）で、
100桁以上の合成数を素因数分解するという問題を出していて、懸賞金がかかっていると思いますが、
それが解けたらニュースになったりします。それは、１年くらいで解けるものだと思いますけど、桁数がそれよりも2倍、
4倍というふうになったら、今のコンピュータでは、宇宙が終わるまでに解けないという感じです。
＞＞＞ 公開鍵とか秘密鍵という観念的なメカニズムは分からないこともありませんが、
暗号を元に戻す、これを復号と言いますが、復号が容易ではないという実際の仕組みを、分かりやすく説明してもらえますか。
織田： 実際には、合同式というのを使って計算しています。例えば、素数をpとqにしましょう。
そして、pとqを掛け合わせた数をmとします。このmで割った余りの数、1からm-1だけに注目して、その数の世界で計算するんです
（mを法とする世界）。この世界では、ｐｑと素な全ての数が、一定の回数べき乗されると、
必ず元の数と同じになるという特徴があります。その乗数は、素数のpとqで決まるのです
（nを任意の正の整数とするとき、n×(p-1)×(q-1)+1）。そこで、元の数に戻すための乗数を、たとえば、αとβに分割します
（α×β=n×(p-1)×(q-1)+1）。このαを公開鍵、βを秘密鍵に割り当てるわけです（mも公開）。
最初のステップは、誰でも読める平文の数値を、公開鍵のαでべき乗します。そして、そのα乗した数を、
mで割った余りの数にして（mを法とする世界の数にして）、それを暗号として送ります。
それを元に戻すとき、αを知っていても、α乗根を求めることは簡単にできないんです。しかし、秘密鍵であるβを知っている人は、
α乗根を求めなくても、それをβ乗すれば元に戻ることを知っているわけです。
そういう計算の仕方が基本になっています。もう少し複雑な楕円曲線暗号では、曲線上の点と点との計算をします。
＞＞＞ 複雑な計算に見えますけど、それはコンピュータでやれば、サーッと解けちゃう話で、
素因数分解するのが難しいというのが暗号解読の障壁になっていると考えておけばよいのでしょうか。
織田： そうですよ。素数を二つ掛け合わせるときに、あまり近い素数だとすぐバレちゃうので、
桁数が違う大きい素数を掛ける。そして、データを受け取る人は、べき乗の逆演算をやるための数を知っている。それだけのことです。
＞＞＞ 暗号の話から外れますが、生物の形態や、
生成のメカニズムに素数が関係しているという事例はあるんでしょうか。オウムガイのきれいな曲線には、
数学的なメカニズムが関係しているんじゃないかと思うんですけど。
三井： ご質問の中にも、美しいものの中には素数が潜んでいると思うが、
どうかというのがあったんですよ。
織田： 生物だと有名な例があります。北米大陸にいる素数蝉です。
Stephen Jay Gould（1941-2002）というHarvard大学のNatural Historyというか博物学の教授で、『パンダの親指』など、
大量の本を書いておりますが、そのどれかの中に、素数蝉といって、13年と17年という素数の年の間隔をおいて、
北米大陸で大量発生する蝉がいると書かれています。なぜ、蝉は素数を知っているかというのは、こういうふうに説明されております。
たとえば、天敵がいたとします。そして、その天敵が4年毎に大量発生し、蝉のほうは3年毎に大量発生したとする。
そうすると、3年と4年の最小公倍数の12年毎にかち会って、蝉が大量に食べられてしまうわけです。
そういう蝉は滅びてしまうけれど、13年毎に発生する蝉であれば、かち会うのは 4×13=52 で、52年に一度だけ。
素数蝉は、素数を知らなくても、生き延びる可能性が高くなる。そういうふうな説明です。
三井： 私も素数蝉のことをインターネットで探してみました。すると、吉村仁さんという方が、
「素数蝉の謎」という本を文芸春秋から出していらっしゃるんですね。今の織田さんの解釈とは少し違うんですが、
それを私が説明するのも何ですから、興味のある方はご覧になって下さい。素数蝉がどんな声で鳴くかとか、
いろいろ書いてあるんですが、ミシガン大学のウェブサイトに行くと聞くことができるそうです。
（おもちゃの蝉を取り出して、鳴かせる！）
これは、素数蝉ではなくて、フランスのプロバンス地方の蝉なんですが、こういう声で鳴くんです。
吉村さんの説によりますと、日本のように、「ミーン、ミーン」とか、
「ツク、ツク、オーシー」とか音楽的に鳴く蝉は他にいないんだそうですね。外国の蝉は、みんな雑音的な鳴き方しかしないそうです。
もうそろそろ、お終いの時間に近づいてきたんですけど、この際、是非、お聞きになりたいという方はいらっしゃいませんか。
普段、こうした専門家の方にいろいろなお話を聞く機会はないんじゃないかと思うのですけど。
|
|
|
|
|
|
|
