1.整数が互いに素となる
整数$n$と$m$の最大公約数が1となるとき、「$n$と$m$は互いに素となる」という。
具体的な例をあげると、
$n=9\,\,m=4,n=3\,\,m=2 , n=14\,\,m=9,n=12\,\,m=7$ など
なお、最大公約数は｢$\gcd$｣という記号で表され、$n$と$m$の最大公約数は、$\gcd(n,m)$と表記される。(ちなみにphython3.5以降はmathモジュールにmath.gcdが実装されている。またアリゴリズムはユークリッドの互除法という。）
そして、素数は約数が１とその数そのもののみ(素数7の約数は1と7のみ)だから、必然的に素数$p$は$1,2,3,4,$･･･$p-2,p-1$の全ての整数（素数7なら1,2,3,4,5,6の全て)と互いに素となる。
2.整数が法nに関して合同
2以上の整数$n$について、整数$a$と$b$の間に$a \bmod n = b \bmod n$が成り立つとき、「$a$と$b$は法$n$に関して合同である」という。
$n$を12とすれば、4と16、2と14、26と2などが法12に関して合同となる(時計の針)。$n$=60とすれば、12と72、45と105、601と1など。
なお、$a$と$b$は法$n$に関して合同であるとは「$a \equiv b \pmod n$」と表記される。
また、$a_1 \equiv b_1 \pmod n$ 及び $a_2 \equiv b_2 \pmod n$の場合、次の式が成り立つ。
a_1 a_2 \equiv b_1 b_2 \pmod n \tag{2-1}
a_1 + a_2 \equiv b_1 + b_2 \pmod n \tag{2-2}
a_1^m \equiv b_1^m \pmod n \qquad \text{(mは1以上の整数)} \tag{2-3}
(証明）
$a_1 \equiv b_1 \pmod n$ 及び $a_2 \equiv b_2 \pmod n$であるとき、$a_1 = nn_1 + k_1, \quad b_1 = nn_1' + k_1, \quad a_2 = nn_2+k_2, \quad b_2 = nn_2' + k_2 \quad$($n$は2以上の整数, $n_1, n_1', n_2, n_2', k_1$及び$k_2$は整数)と表すことができる。
従って、
$a_1 a_2 = n^2 n_1 n_2 + n(k_1 n_2 + k_2 n_1) + k_1 k_2$
$\therefore a_1 a_2 \equiv k_1 k_2 \pmod n$
$b_1b_2=n^2n_1'n_2'+n(k_1n_2'+k_2n_1')+k_1k_2$
$\therefore b_1 b_2 \equiv k_1 k_2 \pmod n$
よって、（2-1）が成り立つ。
同様に、
$a_1+a_2 \equiv k_1 + k_2 \pmod n$
$(b_1+b_2) \pmod n=(k_1+k_2) \pmod n$
よって、（2-2）が成り立つ。
また、
a_1^m = n_1^m n^m + {_{m}C_1} n_1^m n^{m - 1 } k_1 + \dots + {_{m}C_{m - 1}} n_1 n k_1^{m - 1} + k_1^m
b_1^m = n_1^m n^m + {_{m}C_1} n_1^{\prime m} n^{m - 1} k_1 + \dots + {_{m}C_{m - 1}} n_1' n k_1^{m - 1} + k_1^m
$\therefore a_1^m \equiv k_1^m \pmod n, \qquad b_1^m \equiv k_1^m \pmod n$
よって、(2-3)が成り立つ。
□
3.オイラー関数
$n$以下の自然数で$n$と互いに素であるものの個数を$\varphi(n)$と表し、これをオイラー関数という。
例えば、$n=8$なら8以下の自然数で8と互いに素であるのは{1,3,5,7}の4個なので、$\varphi(8)=4$
$n=7$なら7以下の自然数で7と互いに素るものは{1,2,3,4,5,6}の6個なので、$\varphi(7)=6$
同様に、$\varphi(1)=1$ $\varphi(2)=1$ $\varphi(3)=2$ $\varphi(4)=2$ $\varphi(5)=4$ $\varphi(6)=2$ etc
そして、$n=p$で$p$が素数であるならば、当然に、
\varphi(p) = p - 1 \tag{3-1}
が成り立つ。
また、$p$と$q$を別々の素数とすると、$pq$は$p$の倍数と$q$の倍数以外の整数とは素となる。そして、${ 1,2,3,･･･,pq-1,pq }$のうち、$p$の倍数となるのは$q$個、$q$の倍数となるのは$p$個、$p$の倍数かつ$q$の倍数となるのは1個($pq$)であるため、
\varphi(pq) = pq - p - q + 1 = (p - 1)(q - 1) \tag{3-2}
となる。
4.フェルマーの小定理
$p$を素数とし、$a$を$p$と素である整数とすると、
a^{p - 1}\equiv 1 \pmod p \tag{4-1}
(証明)
まず、$m$を整数として、
(m + 1)^p \equiv m^p + 1 \pmod p \tag{4-2}
を証明する。
(m + 1)^p = m^p + {_{p}C_1} + {_{p}C_2} + \dots + {_{p}C_{p - 1}} + 1
ここで$k$を$0 < k < p$の整数とすると、
{_{p}C_k} = p(p - 1)(p - 2) \dotsm (p - k + 1) / k!
であり、$p$が素数であるため分子の$p$は約分されず、また${_{p}C_k}$は場合の数であり必ず整数となる。
従って、${_{p}C_k}$は$p$の倍数となり、上式は$m^p$及び1の項以外は全て$p$で割り切れる。
よって、式(4-2)が成り立つ。
続いて、
a^p \equiv a \pmod p \tag{4-3}
を証明する。
式(4-2)に$m = 1$を代入すると、$2^p$を$p$で割った余りは、$1^p + 1 = 2$であり式(4-3)が成り立つ。
次に、$a = k$の場合も成り立つものと仮定する。（$k^p \equiv k \pmod p$）
式(4-2)より、$(k + 1)^p \equiv k^p + 1 \pmod p$。$a = k$の仮定より、$k^p$を$p$で割った余りは$k$となり、また$1$を$p$で割った余りは$1$である。よって、$(k + 1)^p \equiv k + 1 \pmod p$で、$k = m + 1$でも式(4-3)が成り立ち帰納法により式(4-3)は証明された。
そして、$a$と$p$は互いに素あるため、式(4-3)の両辺を$a$で割ることができ、式(4-1) が成り立つ。□
5.ベズーの等式
$a$と$b$を0でない整数とした時、次の等式を満たす整数$x$と$y$が存在する。
ax + by = \gcd(a, b) \tag{5-1}
$\gcd(a,b)$は最大公約数
(証明)
整数$a$と$b$を固定して、$x$と$y$を任意の整数とし、$ax + by$が与える解の整数の集合を$S$とする。
また、$u$と$v$を集合$S$の要素(当然、整数)、$k$を任意の整数とする。
そのとき、$u = ax_1 + by_1$ $v = ax_2 + by_2$とすれば、$u + v = a(x_1 + x_2) + b(y_1 + y_2)$となり、
また、$u - v = a(x_1 - x_2) + b(y_1 - y_2)$、さらに、$ku = a(kx)_1 + b(ky_1)$となり、いずれも集合$S$の要素となる。
ここで、集合$S$に含まれる最小の正整数を$h$とすると、集合$S$の要素は$ax + by$が与える解で全て整数なのだから集合$S$の要素は全て$h$の整数倍となることが自明である。
今、$x = 1, y = 0$とすると$ax + by = a$、また$x = 0, y = 1$とすると$ax + by = b$であるが、いずれも$ax + by$が与える解であるから$a$と$b$はいずれも集合$S$の要素であり、$h$は$a$と$b$の最小公約数である。従って、$h \leq \gcd(a, b)$である。
また、$a$と$b$は$\gcd(a,b)$の倍数なので、$a = a' \gcd(a, b)$及び$b = b' \gcd(a, b)$($a'$と$b'$はいずれも整数)とおくと、
$ax + by = (a'x + b'y) \gcd(a, b)$となり、集合$S$の要素は$\gcd(a, b)$の倍数となる。$h$も集合$S$の要素の要素だから$\gcd(a, b)$の倍数となり$h \geq \gcd(a, b)$。
$h \leq \gcd(a, b)$かつ$h \geq \gcd(a, b)$であるから、$h = \gcd(a, b)$が成り立つ。従って、式(5-1)を満たす$x, y$が存在する。
6.RSA暗号
6.1 秘密鍵と公開鍵の準備
①２つの素数$p, q$を用意し、$n = pq$とする。(秘密鍵:$p, q$ 公開鍵:$n$)
（ex: $p = 3, q = 5, n = 15$)
②オイラー関数$\varphi(n)$を計算する。(秘密鍵:$f$)
式(3-1)より、$f = \varphi(n) = \varphi(pq) = (p - 1)(q - 1)$
（ex: $f = 2 \cdot 4 = 8$)
③$\gcd(f, c) = 1$であるような正整数$c$を選ぶ。(公開鍵:$c$)
（ex: $c = 7$)
④ $cd \equiv 1 \pmod f$であるような$d$を求める。(秘密鍵:$d$)
ここで$cd = fn + 1$($n$は$cd/f$の商となる整数)、つまり$cd - fn = 1$に対して$d$を整数とする解が存在することは、$\gcd(f, c) = 1$であることからベズーの等式(5-1)により担保される。
（ex: $d = 7$)
⑤これで秘密鍵と公開鍵は全てそろう。
公開鍵: $n, c$
秘密鍵: $p, q, f, d$
（$n = 15, c = 7, p = 3, q = 5, f = 8, d = 7$)
6.2 発信者の暗号の作成
$x$を平文として暗号文$y$を
$x^c \equiv y \pmod n$
によって生成する。
(ex: $x = 12, y \equiv 11^7 \equiv 3 \pmod {15}$)
6.3 受信者の暗号の復号
$y$を暗号として受け取り
$y^d \equiv x \pmod n$
により平文$x$が復号される。
ここで$cd \equiv 1 \pmod f$であるので、$cd = 1 + kf$であるような正整数$k$が存在する。
従って、$y^d \equiv (x^c)^d \equiv x^{cd} \equiv xx^{kf} \pmod n$
また、$f = \varphi(n) = (1 - p)(1 - q)$であるから、
$y^d \equiv xx^{k(1 - p)(1 - q)} \pmod n \tag{6-1}$
ここで$n=pq$であるからまず$p$で$\text{mod}$をとる。
$xx^{k(1 - p)(1 - q)} \pmod p \equiv xx^{(1 - p)}{k(1 - q)} \pmod p$
小フェルマーの定理(式(4-1))より、
$\equiv x(1)^{k(1 - q)} \equiv x \pmod p$
同様に、$q$で$\text{mod}$をとると、
$xx^{k(1 - p)(1 - q)} \pmod q \equiv xx^{(1 - q)}{k(1 - p)} \pmod q$
同じく小フェルマーの定理(式(4-1))より、
$\equiv x(1)^{k(1 - p)}\equiv x \pmod q$
つまり、$x^{k(1 - p)(1 - q)}$は$p$で割っても$q$で割っても余りが1となる。
従って、$m$を正の整数とすると$x^{k(1 - p)(1 - q)} = (pqのいずれもが一次以上の項) + 1 = (nが一次以上の項) + 1$であるから、式(6-1)は、
$y^d \equiv xx^{k(1 - p)(1 - q)} \equiv x \pmod n$
となり、復号できることがわかる。
（ex: $3^7 \equiv 12 \pmod{15} x=12$が復号された！！）