RSA暗号に紹介には、必ず次のような式がでてきます。
これ
今日は、この式について解説します。
といっても・・・すみません。言い訳になりますが、
数学科出身ではなく、間違ったこというかもしれません。
それをふまえていただいて・・・解説させていただきます。
まず、m = (p – 1)(q – 1) とすると、式は次のようになります。
さて、この式、意味が分かりますでしょうか。
ここで、mod mというのは、mで割った余りとなります。
つまり、式通りの意味を考えると x-1 =(1/x) を計算して、
m で割った余りが y となります。
しかし、よく考えてください。
言い忘れていましたが、x, y, m とも整数なのです。
x が整数の時点で、 x-1 =(1/x) という式を計算すると、
小数点付きの数値となり、小数点付きの数値に対して、
整数 m で割る？というよく分からないことが起きます。
じつは、これは逆数とはいってもモジュラ逆数と呼ばれるものなのです。
つまり、(1/x)みたいなことをしてはいけないのです。たぶん？
さて、モジュラ逆数となると、
上記のこれまでの式は一体どういう意味なのか。
実は、次のような意味になります。
x と y を掛け算して、m で割った後の余りが 1 となります。
つまり、これまでの式は、
上記の計算結果を満たすような y を求める式なのです。
例題と行きましょう。
x = 3, m = 10 としたときの y は一体いくつでしょうか。
これの y を求めてみましょう。
・・・
求める過程は、モジュラ逆数の紹介にある
拡張ユークリッド互除法で最大公約数など、
いくつか値を求める必要がありまして、
ここでは省略します。
そして、答えを求めると y = 7 が導かれます。
実際に計算してみると・・・
余りが 1 となり、ぴったりとなります。
なお、Java などでは、
この y の値を BigInteger の modInverse メソッドで計算することが可能です。
public static void main(String[] args) {
System.out.println(new BigInteger("3").modInverse(new BigInteger("10")));
}
