RSA暗号化アルゴリズムの証明「n を法とする世界」というとき、全ての数は「n で割った余り」になります。たとえば、3を法とする世界では、1と4と7はすべて同じ値です。「n を法とする世界」であることを「 mod n 」と書きます。上の表は「 mod 15 」です。 この表は私がプログラムでつくり出したものです。太字になっているところを見てください。5乗・9乗・13乗はすべてもとの値に戻っています。これがRSA暗号の暗号化と復号化の基本的なアルゴリズムのもとになっています。 x * (p - 1) * (q - 1) + 1 上の表で確認した5乗・9乗・13乗はすべて、「4で割った余りが1」の数です。要するに「 mod n 」を使って、このように表すことができます。 1 = 5 = 9 = 13 (mod 4) ここで「4」という数字に注目してください。実は、上の表のもとになった「 mod 15 」の 15 は以下のよ
