クラバートの樹

今まで「高校数学で理解する・・・」という記事を何回か書きましたが、その中に暗号についての一連の記事があります。 No.310「高校数学で理解するRSA暗号の数理（１）」 No.311「高校数学で理解するRSA暗号の数理（２）」 No.313「高校数学で理解する公開鍵暗号の数理」 No.315「高校数学で理解する楕円曲線暗号の数理（１）」 No.316「高校数学で理解する楕円曲線暗号の数理（２）」 の５つです。これらは公開鍵暗号と、その中でも代表的な RSA暗号、楕円曲線暗号の数学的背景を書いたものです。情報通信をインフラとする現代社会は、この公開鍵暗号がなくては成り立ちません。"数学の社会応用" の典型的な例と言えるでしょう。 これらの暗号では、10進数で数10桁～数100桁の素数が必要です。ないしは、数10桁～数100桁の数が素数かどうかを判定する必要があります。 たとえば、マイナンバー・カードの認証に使われている RSA暗号の公開鍵は 2048ビットで、1024ビットの素数２つを掛け合わせて個人ごとに作られます。1024ビットということは \(2^{1023}\) ～ \(2^{1024}-1\) の数であり、10進では約300桁の巨大数です。素数を生成する式はないので、作るためには1024ビットの数をランダムに選び、それが素数かどうかを実用的な時間で判定する必要があります。 ビットコインのデジタル署名で使われているのは、256ビットの楕円曲線暗号です。こ…