Pebble's Diary

プログラマーの作業メモ

RSA暗号の原理を理解するための数学知識

RSA暗号に関する文章を読んでいてもその数学的な原理がさっぱり理解できなかったのですが、色々読んでいるうちになんとなく分かってきましたので、メモしておきます。

 a = b \mod n, \\
c = d \mod n 

のとき、

 a + c = b + d \mod n

 a * c = b * d \mod n

 a^{m} = b^{m} \mod n

である。

 ef = eg \mod n で gcd(e, n) = 1 ならば
 f = g \mod n
である。

合同式の意味とよく使う6つの性質 | 高校数学の美しい物語

オイラーの定理

nが正の整数で、gcd(a, n) = 1 のとき、  a^{\phi(n)} = 1 \mod n である。
ここで、gcd は greatest common divider の略で最大公約数を意味する。
 \phi(n) は1からnまでの自然数のうちgcd(b, n)=1となる数bの個数を意味する関数とする。

nが素数の場合は、bは1, 2, 3, … , n-1となり、 \phi(p) = p-1 となる。

また、p, qが素数の場合、2つをかけた合成数 pq に対して \phi(pq) = (p-1)(q-1)が成り立つ。

RSA暗号の世界 | サルにも分かるRSA暗号

RSAのひ・み・つ - 小人さんの妄想

オイラーのφ関数 - Wikipedia

中国人剰余定理によりgcd(p, q) = 1のとき、
 m = n \mod p
 m = n \mod q
であれば
 m = n \mod pq   である。

中国剰余定理の証明と例題(二元の場合) | 高校数学の美しい物語