暗号に使う素数を判定する方法とは？

素因数分解の困難さを利用した暗号

情報の暗号化の方法の1つにRSA暗号があります。これは、「桁数が大きい素数同士を掛け合わせた数の素因数分解は簡単にはできない」という特質を利用した暗号の1つで、インターネットのセキュリティ技術に広く利用されています。RSA暗号を作るには、巨大な素数が必要になりますが、それにはまず、候補となる巨大な数が本当に素数なのかを判定する必要があります。

素数の判定は難しい！

素数判定のもっとも素朴な方法は、その数を2から順番に割っていくことです。例えば、nが素数であるかどうかを調べるためには、ルートnまで割っていきますが、nが、100桁であれば、50桁まで計算しなければならず、計算に莫大な時間がかかってしまい、実用的ではありません。そこでこれに代わる素数の判定アルゴリズムとして、2種類のアルゴリズム（計算の手順）を紹介します。

ミラー・ラビン素数判定法とAKS素数判定法

その1つは、「ミラー・ラビン素数判定法」で、素数だということをほぼ確実に判定する方法です。「ほぼ確実」ということは、100％判定できるわけではないという意味ですが、判定に失敗する確率が極めて低い上に、瞬時に判定できるという利便性から、広く利用されています。
100％正しく、かつ時間も短い判定方法を探すというのが数学者の信条ですから、その方法も長年追究されてきました。そして今世紀の初頭、確実に素数判定が可能で理論的に高速な、もう1つの「AKS素数判定法」という方法が開発されました。少し難解な説明になりますが、この方法は、リーマン予想などの仮説を用いることなく、決定性多項式時間（与えられた自然数nが素数であるかどうかの判定にかかる時間がlog(n) の多項式を上界とする時間）で判定できる初めてのアルゴリズムです。ただ、多項式の次数が高すぎることから、従来判定が不可能だった素数を高速に判定できるようになったわけではないという課題があります。

※夢ナビ講義は各講師の見解にもとづく講義内容としてご理解ください。

※夢ナビ講義の内容に関するお問い合わせには対応しておりません。

先生情報 / 大学情報

東京都立大学理学部数理科学科准教授内田幸寛先生

興味が湧いてきたら、この学問がオススメ！

数理科学

メッセージ

私の専門は整数論です。古くから研究されている素数の性質や方程式の整数解がどれくらいあるかといった問題を研究しています。昔はこうした問題は、手でたくさん計算して調べていましたが、最近は、コンピュータを使い、いろいろな実験をもとに予想を立てたり問題を解いたりできます。また、コンピュータの進歩にともない、「暗号理論」という新たな整数論の応用もできるようになってきました。数学やコンピュータに興味がある人は、首都大学東京で一緒に整数の世界を学んでいきましょう。

先生への質問

先輩たちはどんな仕事に携わっているの？

東京都立大学に関心を持ったあなたは

東京都立大学は「大都市における人間社会の理想像の追求」を使命とし、東京都が設置している公立の総合大学です。人文社会学部、法学部、経済経営学部、理学部、都市環境学部、システムデザイン学部、健康福祉学部の7学部23学科で広範な学問領域を網羅。学部、領域を越え自由に学ぶカリキュラムやインターンシップなどの特色あるプログラムや、各分野の高度な専門教育が、充実した環境の中で受けられます。