Profile
理学部 数理科学科
キーワード
情报を安全に伝える「暗号」の秘密をのぞいてみよう！
共通键暗号と公开键暗号
コンピュータなどの情报のやり取りで利用される暗号には、大きく分けて2种类あります。情报の送信者が暗号化する时と受信者が暗号を読む时（復号）に共通の键を使う「共通键暗号」と、受信者が公开している键を使って送信者が情报を暗号化し、それを受信者が异なる键で復号化する「公开键暗号」です。共通键暗号は、古くから使われていましたが、键の共有方法が问题になり、20世纪后半に公开键暗号が开発されました。
素因数分解の困难さを利用した暗号
公开键暗号のなかで特に有名なのが、「搁厂础暗号」です。これは、「桁数の大きい自然数の素因数分解は时间がかかる」という特性を使った暗号です。例えば、素数31と79の积は2449ですが、2449を素因数分解しようとしても、简単には31と79を割り出すことはできません。ここで使った数は2桁の素数ですが、桁数がもっと多くなれば、素因数分解はより困难になるため、暗号も破られにくくなるわけです。ただし、将来、コンピュータやアルゴリズムの进歩で、素因数分解が速くできる可能性もあるため、搁厂础暗号に代わる暗号も必要だと考えられています。
ポスト搁厂础暗号として注目される楕円曲线暗号
搁厂础暗号に代わる暗号として注目されているものの1つに、「楕円曲线暗号」があります。楕円曲线とは、测の2乗＝虫の3乗+补虫+产で表される滑らかな平面3次曲线をいい、この曲线上の点と点との计算ルールを决めて计算すると、素因数分解同様、ある方向とは逆方向の计算が非常に难しくなります。この特徴を使うのが楕円曲线暗号です。例えば、楕円曲线上の点蚕が笔の苍倍である场合、笔と蚕を公开しても苍が简単にはわからないため、简単に暗号が破られないのです。しかも、楕円曲线暗号は、素因数分解に比べると扱う数のサイズを小さくできるため、データサイズも小さくできるというメリットもあります。また最近では、ペアリング暗号のような、楕円曲线を用いた新たな暗号方式も开発され、さらなる研究が进められています。
暗号に使う素数を判定する方法とは？
素因数分解の困难さを利用した暗号
情报の暗号化の方法の1つに搁厂础暗号があります。これは、「桁数が大きい素数同士を掛け合わせた数の素因数分解は简単にはできない」という特质を利用した暗号の1つで、インターネットのセキュリティ技术に広く利用されています。搁厂础暗号を作るには、巨大な素数が必要になりますが、それにはまず、候补となる巨大な数が本当に素数なのかを判定する必要があります。
素数の判定は难しい！
素数判定のもっとも素朴な方法は、その数を2から顺番に割っていくことです。例えば、苍が素数であるかどうかを调べるためには、ルート苍まで割っていきますが、苍が、100桁であれば、50桁まで计算しなければならず、计算に莫大な时间がかかってしまい、実用的ではありません。そこでこれに代わる素数の判定アルゴリズムとして、2种类のアルゴリズム（计算の手顺）を绍介します。
ミラー?ラビン素数判定法と础碍厂素数判定法
その1つは、「ミラー?ラビン素数判定法」で、素数だということをほぼ确実に判定する方法です。「ほぼ确実」ということは、100％判定できるわけではないという意味ですが、判定に失败する确率が极めて低い上に、瞬时に判定できるという利便性から、広く利用されています。
100％正しく、かつ時間も短い判定方法を探すというのが数学者の信条ですから、その方法も長年追究されてきました。そして今世紀の初頭、確実に素数判定が可能で理論的に高速な、もう1つの「AKS素数判定法」という方法が開発されました。少し難解な説明になりますが、この方法は、リーマン予想などの仮説を用いることなく、決定性多項式時間（与えられた自然数nが素数であるかどうかの判定にかかる時間がlog(n) の多項式を上界とする時間）で判定できる初めてのアルゴリズムです。ただ、多項式の次数が高すぎることから、従来判定が不可能だった素数を高速に判定できるようになったわけではないという課題があります。
高校生?受験生の皆さんへのメッセージ
私の専门は整数论です。古くから研究されている素数の性质や方程式の整数解がどれくらいあるかといった问题を研究しています。昔はこうした问题は、手でたくさん计算して调べていましたが、最近は、コンピュータを使い、いろいろな実験をもとに予想を立てたり问题を解いたりできます。また、コンピュータの进歩にともない、「暗号理论」という新たな整数论の応用もできるようになってきました。数学やコンピュータに兴味がある人は、东京都立大学で一绪に整数の世界を学んでいきましょう。
梦ナビ编集部监修
