中国剰余定理
こんにちは。本当はもう少し暗号を続けたいのですが、比較的新しい暗号は数学による処理が用いられています。そのため、暗号の話と混ぜてしまうとアルゴリズムが見えにくくなるので、別扱いにした方が見通しがききます。そこで、今回は中国剰余の定理について取り上げます。
中国剰余定理の前に
先に具体例を用いて説明します。
ある数\(x\)は、\(5\)で割ると\(1\)余り、\(7\)で割ると\(2\)余るものとします。このとき、\(x\)を\(5 \times 7 =35\)で割ったときの余り\(r\)は、\(0 \leq r \lt 35\)の範囲に、１つだけ存在します。
確かめてみましょう。
\(0\)以上\(35\)未満の範囲で、\(5\)で割ったときに\(1\)余る数は、\(1,6,11,16,21,26,31\)の７個あります。このうち、\(7\)で割ったときに\(2\)余る数は、\(16\)だけで他にはありません。\(5\)と\(7\)のように互いに素である場合、このような数がただ１つだけ存在するというのが中国剰余定理です。
これを数式で表しておきます。
\(x \equiv 1 \bmod 5\)
\(x \equiv 2 \bmod 7\)
のとき、\(x \equiv r \bmod 35\)をみたす\(0 \leq r \lt 35\)は、ただ１つだけ存在します。これを満たすのは、\(r=16\)です。
中国剰余定理を数式で表す
先ほどの例を一般化すると次になります。
整数\(m_1 , m_2, \cdots m_k\)が互いに素ならば、任意に与えられる整数\(a_1 , a_2, \cdots a_k\)に対して
\(x \equiv a_1 \bmod m_1 \)
\(x \equiv a_2 \bmod m_2 \)
\( \cdots \)
\(x \equiv a_k \bmod m_k \)
を満たす\(x\)は、\(m_1 m_2 \cdots m_k\)を法として一意に存在します。
一意に存在する値を求めるには
アルゴリズムを紹介してそれをプログラムで実装しようと思っていました。このような値を効率的に求めるアルゴリズムにはGaussのアルゴリズム、Garnerのアルゴリズムがありますが、逆元（演算の結果、単位元となる値）を求める必要があることがわかってしまいました。
先にフェルマーの小定理を取り上げるべきでしたが、全体の流れをつかんでいなかったため、今回は短いですが、ここでおしまいにします。次回は逆元を求めるアルゴリズムについて取り上げたいと思います。それではまた。