RSA暗号に関する文章を読んでいてもその数学的な原理がさっぱり理解できなかったのですが、
色々読んでいるうちになんとなく分かってきましたので、メモしておきます。
まずモジュラー演算記号(mod)を覚えましょう。
これは整数aを整数nで割った余りとbを整数nで割った余りが等しいことを表します。
例:
モジュラー演算には以下の性質があります。
のとき、
である。
で gcd(e, n) = 1 ならば
である。
ここで gcd(a, b) は整数a,bの最大公約数(Greatest Common Divisor)を表します。
nが正の整数で、gcd(a, n) = 1 のとき、
である。
は1からnまでの自然数のうちgcd(b, n)=1となる数bの個数を意味する関数とする。
nが素数の場合は、bは1, 2, 3, … , n-1となり、 となる。
また、p, qが素数の場合、2つをかけた合成数 pq に対してが成り立つ。
中国人剰余定理によりgcd(p, q) = 1のとき、
であれば
である。