暗号の数学
剰余演算とは
剰余類と既約剰余類
整数 $n$ を整数 $q\ (q \geq 2)$ で割った余りからなる集合
\[ Z_q = \{0,1, 2, \ldots, q-1\} \]
を剰余類 (residue class)という.
集合 $Z_q$ の中で $(a_i, q) = 1$ を満たす元の集合
\[ {Z_q}^* = \{a_1, a_2, \ldots, a_{\varphi(q)}\} \]
を既約剰余類という.
オイラー関数
正整数 $n$ に対して,$1 \le m \lt n$ で $(n,\ m)=1$ を満たす $m$ の総数をオイラー関数(Euler's Function)といい,$\varphi(n)$ で表す.
例えば,
$n = 12$ のとき,$m = 1, 5, 7, 11$ であり,$\varphi(12) = 4$ である.
$n$ の素因数分解を $n=p_1^{e_1}p_2^{e_2}\ldots p_j^{e_j}$ ($1, \cdots p_j$ は異なる素数) とするとき,オイラー関数 $\varphi(n)$
は,次式で求められる.
\[ \varphi(n) = n(1- \frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_j}) \]
$(m,\ n)=1$ のとき,$\varphi(mn)=\varphi(m)\varphi(n)$ となる.
$d_1,d_2,\cdots,d_r$ を $n$ の約数全体とするとき,
\[\varphi(d_1)+\varphi(d_2)+\cdots+\varphi(d_r) = n\]
が成立つ.
(例)
$n = 15\qquad (1, 3, 5, 15)$
\[ \varphi(1)+\varphi(3)+\varphi(5)+\varphi(15)=1+2+4+8=15 \]
剰余還元
剰余演算は,法と呼ばれる固定整数 $m\ (\gt 1)$ に基づく演算である.基本的な演算は,法 $m$ による還元である.すなわち,$m$ で割った余り $r$ を求める演算である.
この演算は,次のように書かれる.
\[ r := a \bmod m \]
余り $r$ は,$0 \le r \lt m$ を満たさなければならない.
以下に例を示す.
\[ 11 \bmod 8 = 3 \]
\[ 7 \bmod 9 = 7 \]
\[ -2 \bmod 11 = 9 \]
\[ 12 \bmod 12 = 0 \]
合同式
合同式とその性質
整数の集合 $Z$ の任意の元 $x, y$ を整数 $m$ で割った余りが等しいとき,$x$ および $y$ は $m$ を法として合同であるという.
この関係は以下のように表される.
\[ x \equiv y \pmod{m} \]
$x$ と $y$ の合同性は次と同値である.
$x$ を $x = y + mt$ ($t$ は整数)という形に表すことができる.
$x - y$ を $m$ で割り切ることができる.
合同式の性質
$a \equiv a \pmod{m}$ $\cdots$ 反射律
$a \equiv b \pmod{m} \Longrightarrow b\equiv a \pmod{m}$ $\cdots$ 対称律
$a \equiv b \pmod{m},\ b \equiv c \pmod{m} \Longrightarrow a \equiv c \pmod{m}$ $\cdots$ 推移律
$a\equiv b \pmod{m},\ c \equiv d \pmod{m} \Longrightarrow$
$a+c \equiv b+d \pmod{m}$,
$a-c \equiv b-d \pmod{m}$,
$ac \equiv bd \pmod{m}$,
自然数 $n$ に対し,$a^n \equiv b^n \pmod{m}$.
$a+b \equiv c \pmod{m} \Longrightarrow a \equiv c-b \pmod{m}$
加算,乗算について交換法則および結合法則が成立つ.
分配法則 $a(b + c) \equiv ab + ac$ が成り立つ.
$ac \equiv bc \pmod{m},\ c$ と $m$ は互いに素 $\Longrightarrow a \equiv b \pmod{m}$
$ac \equiv bc \pmod{mc}$,$c$ と $m$ は互いに素
$\Longleftrightarrow$ $a \equiv b \pmod{m}$
法 m における整数
法 $m$ における整数は,法 $m$ による還元の結果であり,次の集合である.
\[ Z_m = \{0,1,\ldots,m-1\} \]
$Z_m$ に対する加算,減算,乗算は,対応する整数の演算であり,法 $m$ による還元が行われる.
$0 \le a, b \lt m$ な数に対して,
\[ a + b \bmod\ m = \left\{
\begin{array}{ll}
a + b & a + b \lt m の場合,\\
a + b - m & 上記以外.\\
\end{array}\right.
\]
\[ a - b \bmod\ m = \left\{
\begin{array}{ll}
a - b & a - b \ge 0 の場合,\\
m + a - b & 上記以外.\\
\end{array}\right.
\]
\[ a \cdot b \bmod\ m = r\quad (a \cdot b = q\cdot m+r),\ 0\le r \lt m \]
\[ a^{-1} \bmod\ m = a'\quad (a \cdot a'=q\cdot m+1) \]
例えば,$Z_7$上では,
\[ 3 = 6 + 4 \]
\[ 5 = 1 - 3 \]
\[ 6 = 4 \times 5. \]
剰余除算
法 $m$ における $h$ の乗法逆元は,$hk \equiv 1 \pmod{m}$ なる法 $m$ における整数 $k$ である.
整数 $h$ の乗法逆元は,$h^{-1} \bmod m$ と表される.
$h$ が $m$ と互いに素ならば,$h$ の逆元は存在する.
$g$ と $h$ を法 $m$ における整数,$h$ が $m$ と互いに素ならば,剰余除算 $g/h \bmod m$ は,
\[ g h^{-1} \pmod m \]
で定義される.
べき乗剰余
$v$ を正の整数,$g$ を法 $m$ における整数とするとき,べき乗剰余は $g^v \bmod m$ を計算する演算である $(exp(g, v) \bmod m$ とも書かれる).
オイラーの定理
フェルマー(Fermat)の小定理
$p$ が素数で,$(a, p) = 1$ のとき,
\[ a^{p-1} \equiv 1 \pmod p \]
が成立つ.
上式の両辺に $a$ を掛けることにより,合同式
\[ a^p \equiv a \pmod{p} \]
を得る.これはすべての整数 $a$ に対して成立つ ($p$ の倍数である $a$ に対しても成立つため).
オイラー(Euler)の定理
$q \gt 1$ かつ $(a, q) = 1$ のとき,
\[ a^{\varphi(q)} \equiv 1 \pmod q \]
が成り立つ.
$q$ が素数 $p$ のとき,$\varphi(n)= p-1$ でありフェルマーの小定理になる.
オイラーの定理を用いて逆元計算を行うことができる.
$(a, q) = 1$ のとき,
\[ a^{\varphi(q)- 1} \equiv a^{-1} \pmod q \]
により逆元が求まる.
1次合同式
1次合同式は,次の形式の合同式である.
\[ ax \equiv b \pmod{m} \]
$(a, m) = d$ とする.合同式 $ax \equiv b \pmod{m}$ は,$b$ が $d$ で割り切れない場合には成立しない.$d$ の倍数である $b$ に対しては,この合同式は $d$
個の解をもつ.
$(a, m)=d \gt 1,\ a=a_1d,\ b=b_1d,\ m=m_1d$ とするとき,
\[ a_1x \equiv b_1 \pmod{m_1} \]
となる.この合同式は,$(a_1, m_1) = 1$ より1つの解 $x_1$ をもつ.
すなわち,
\[ a_1x_0 + m_1y_0 = 1\]
なる $x_0$,$y_0$ が拡張ユークリッドの互除法により求められる.両辺を $b_1$ 倍して,
\[ a_1(b_1x_0) + m_1(b_1y_0) = b_1\]
となることから
\[ a_1(b_1x_0) \equiv b_1 \pmod{m_1} \]
となり,$x_1 = b_1 x_0$ となる. このとき,法 $m$ に対する解は,
\[ x_1,\ x_1+m_1,\ x_1+2m_1, \cdots,\ x_1+(d-1)m_1 \]
で与えられる.
平方剰余
平方剰余と平方非剰余
$a$ に対し,次の2次合同式
\[ x^2 \equiv a \pmod{q} \]
が解を持つとき $a$ を $q$ を法とする平方剰余という. 解を持たないとき平方非剰余という.
一般に $p$ を法とする平方剰余は $(p - 1)/2$ 個存在する. また,
$GF(p)$ において,ランダムに選んだ $p - 1$ 以下の整数 $x$ が $p$ を法として平方剰余となる確率は $1/2$ になる.
(例) $x^2 ≡ 3 \pmod{11}$ は,$x = 6$ の解をもつので,$3$ は $11$ の平方剰余である.
Legendre 記号とJacobi 記号
Legendre 記号
\[ \left(\frac{a}{p}\right) = \left\{
\begin{array}{ll}
1 & (a: 平方剰余),\\
-1 & (a: 平方非剰余).\\
\end{array}\right.
\]
任意の奇素数 $p$ および $p$ と互いに素な任意の整数 $a$ に対して,以下の関係が成立つ (Euler 基準).
\[ \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p} \]
Legendre 記号は,$a \equiv b \pmod{p}$ のとき次の関係が成立つ.
$ \left(\frac{a}{p}\right) \equiv \left(\frac{b}{p}\right) $
$ \left(\frac{1}{p}\right) \equiv 1 $
$ \left(\frac{a_1a_2\cdots a_k}{p}\right) \equiv \left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right)
\cdots \left(\frac{a_k}{p}\right)$
$ \left(\frac{ab^2}{p}\right) \equiv \left(\frac{a}{p}\right) $
平方剰余の相互法則
$p$ と $q$ が奇素数のとき次式が成立つ.
\[ \left(\frac{q}{p}\right) \equiv (-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}}\left(\frac{p}{q}\right) \]
Jacobi 記号
任意の整数 $a$ と $a$ と互いに素な整数 $q$ が,
\[ q = p_1^{m_1}p_2^{m_2}\cdots p_n^{m_n} \]
であるとき ($p_i$ は異なる素数),
\[ \left(\frac{a}{q}\right) \equiv
\left(\frac{a}{p_1}\right)^{m_1}\left(\frac{a}{p_2}\right)^{m_2} \cdots
\left(\frac{a}{p_n}\right)^{m_n}\]
をJacobi記号という.
Jacobi 記号に対しても,Legendre 記号と同様な関係が成立つ. 任意の相異なる奇素数 $p$, $q$ に対して以下の関係が成立つ.
\[ \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) \equiv
(-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}}\]
\[ \left(\frac{-1}{p}\right) \equiv (-1)^{\frac{p-1}{2}} \]
\[ \left(\frac{2}{p}\right) \equiv (-1)^{\frac{p^2-1}{8}} \]
Jacobi 記号の計算
入力 : 整数 $a$,奇整数 $n \gt 1$
出力 : $\left(\frac{a}{n}\right) \in \{1,0,-1\}$
$x \leftarrow a,\ y \leftarrow n,\ J \leftarrow 1$
While $y \gt 1$
$x \leftarrow (x\ \bmod\ y)$
If $x \gt y/2$ then
$x \leftarrow y - x$
If $y ≡ 3 \pmod{4}$ then $J \leftarrow -J$
If $x = 0$ then $x \leftarrow 1,\ y \leftarrow 0,\ J \leftarrow 0$
While $4$ divides $x$
$x \leftarrow x/4$
If $2$ divides $x$ then
$x \leftarrow x/2$
If $y \equiv \pm 3 \pmod{8}$ then $J \leftarrow -J$
If $x ≡ 3 \pmod{4}$ and $y ≡ 3 \pmod{4}$ then $J \leftarrow -J$
Switch $x$ and $y$
Return $J$
$n$ が素数 $p$ に等しい場合,Jacobi 記号は次の式で求めることができる.
\[ \left(\frac{a}{p}\right) = a^{(p-1)/2} \pmod{p} \]
原始根
原始根とは
$(a, m) = 1$ であれば,$a^r = 1 \bmod m$ となる整数 $r$ が存在する.そのうちの最小のものを法 $m$ に関する $a$ の位数という.
法 $m$ に関するある数の位数は $\varphi(m)$ の約数である.
位数が $\varphi(m)$ の数を,法 $m$ の原始根と呼ぶ.
$a$ が原始根ならば,次のべき乗は $m$ を法としてすべて異なる.
\[ a, a^2, a^3, \cdots , a^{m-2}, a^{m-1} \pmod{m} \]
原始根定理
任意の素数 $p$ は原始根をもつ.$p$ を法とした原始根は $\varphi(p-1)$ 個存在する.
原始根と指数
$p$ を法とする原始根 $g$
$p$ を法として $0$ でない整数すべてが $g$ のべきで表せる.
指数
$g$ を底とした法 $p$ に関する $a\ (1\le a\le p)$ の指数: $I(a)$
$g^{I(a)}$ = $a \bmod p$
指数法則
$I(ab) \equiv I(a) + I(b) \pmod{p-1}$
$I(a^k) \equiv k I(a) \pmod{p-1}$
原始根の求め方
$c=\varphi(m)$ とし,$q$1 , $q_1,q_2,\cdots,q_k$ を数 $c$ の互いに異なる素な約数とする.$m$ と互いに素な数 $g$ が法 $m$
に関する原始根であるためには,この数 $g$ が合同式
\[ g^{(c/q_1)}\equiv 1 \pmod{m},\ g^{(c/q_2)} \equiv 1 \pmod{m},
\cdots,\ g^{(c/q_k)} \equiv 1 \pmod{m} \]
を一つも満足しないことが必要十分である.
(例)法 $41$ に関する最小の原始根を求める.
$\varphi(41)=40=2^3・5,\ 40/5=8, 40/2=20$
$g^8 \equiv 1,\ g^{20} \equiv 1 \pmod{41}$ を一つも満足しないことを検査する.
$2^{20} \equiv 1,\ 3^8 \equiv 1,\ 4^{20} \equiv 1,\ 5^{20} \equiv 1 \pmod{41}$ より,$2, 3, 4, 5$ は原始根ではない.
$6^8 \equiv 20,\ 6^{20} \equiv 40 \pmod{41}$ より,$6$ は原始根である.