\newcommand{\sg}{\sigma}\newcommand{\cd}{\cdots}\)今まで「高校数学で理解する・・・」という記事を何回か書きましたが、その中に暗号についての一連の記事があります。No.310「高校数学で理解するRSA暗号の数理(1)」No.311「高校数学で理解するRSA暗号の数理(2)」No.313「高校数学で理解する公開鍵暗号の数理」No.315「高校数学で理解する楕円曲線暗号の数理(1)」No.316「高校数学で理解する楕円曲線暗号の数理(2)」の5つです。数学的背景を書いたものです。情報通信をインフラとする現代社会は、この公開鍵暗号がなくては成り立ちません。典型的な例と言えるでしょう。これらの暗号では、10進数で数10桁~数100桁の素数が必要です。数10桁~数100桁の数が素数かどうかを判定する必要があります。2048ビットで、1024ビットの素数2つを掛け合わせて個人ごとに作られます。数であり、10進では約300桁の巨大数です。素数を生成する式はないので、作るためには1024ビットの数をランダムに選び、それが素数かどうかを実用的な時間で判定する必要があります。ビットコインのデジタル署名で使われているのは、256ビットの楕円曲線暗号です。この暗号の公開鍵は一般に公開されていますが(暗号の仕組みから個人ごとに作る必要はない)、この公開鍵を設計するときに必要なのは、256ビット=約80桁(10進)の数が素数かどうかを判定することです。公開鍵暗号の基礎となっている技術が「素数判定」なのです。テスト」の数学的背景を書きます。このテストを考案した数学者2人の名前です。本論に入る前に前提知識について整理します。「高校数学で理解する・・・」というタイトルは「高校までで習う数学の知識だけを前提とする」という意味です。従って、その前提からはずれるものはすべて証明するのが基本方針です。今回は、以前の「高校数学で理解する・・・」で証明した事項を前提知識とします。事項について、素数判定に関わるところを簡単に復習します。ある整数の集合とします(剰余類と呼ばれる)。余る整数の集合」で、\(\ol{2_9}=\{\:\cd,\:-16,\:-7,\:2,\:11,\:20,\:29,\:\cd\:\}\)です。\(Z/nZ=\{\ol{0_n},\:\ol{1_n},\:\cd\:,\:\ol{(n-1)_n}\}\)で示される「無限集合を元とする有限集合」です。\(Z/9Z=\{\ol{0_9},\:\ol{1_9},\:\ol{2_9},\:\ol{3_9},\:\ol{4_9},\:\ol{5_9},\:\ol{6_9},\:\ol{7_9},\:\ol{8_9}\}\)です。この演算について群の定義を満たし(=加法群)、この群を剰余群と呼びます。表しますが、剰余群の群位数は、\(|Z/nZ|=n\)です。以降、剰余類と整数を同一視して、\(Z/9Z=\{0,\:1,\:2,\:3,\:4,\:5,\:6,\:7,\:8\}\)というように書きます。\(\ol{1_n}\))を表すこともあります。どちらかは文脈で決まります。例をあげると、\(\begin{eqnarray}&&\:\:(Z/9Z)^{*}&=\{\ol{1_9},\:\ol{2_9},\:\ol{4_9},\:\ol{5_9},\:\ol{7_9},\:\ol{8_9}\}\\&&&=\{\:1,\:2,\:4,\:5,\:7,\:8\:\}\\\end{eqnarray}\)です。乗算を演算とする群になります(=乗法群)。a^{-1}=1\)が成り立ちます。乗算と除算が自由にできます。&7^{-1}&=4\\&&\:\:8^{-1}&=8&&\\\end{eqnarray}\)です。使って、\((Z/nZ)^{*}=\varphi(n)\)で表されます。互いに素な数の個数」です。異なる素数とすると、\(\begin{eqnarray}&&\:\:\varphi(p)&=p-1\\&&\:\:\varphi(pq)&=(p-1)(q-1)\\&&\:\:\varphi(p^2)&=p(p-1)\\\end{eqnarray}\)などが成り立ちます。