ikautak.log

C/C++, Python, CUDA, Android, Linux kernel, Network, etc.

暗号理論入門 3.16〜3.18

暗号理論入門 原書第3版

暗号理論入門 原書第3版

3.16 剰余環の分解

中国人の剰余定理を使うと、大きな剰余環  \mathbb{Z}/m \mathbb{Z} の代わりに、多くの小さな剰余環  \mathbb{Z} / m_i \mathbb{Z} で計算することができる。

 m_1,\ \ \ \  ...,\ \ \ \  m_n を互いに素な整数とし、 m = m_1 m_2 ...\ , m_n であるとする。このとき、写像
  \displaystyle \mathbb{Z} / m \mathbb{Z} \to \prod_{i=1}^{n} \mathbb{Z} / m_i \mathbb{Z}, \hspace{15pt} a + m \mathbb{Z} \to (a + m_1 \mathbb{Z},\ \ \ ...,\ \ \ a + m_n \mathbb{Z})
は環の同型写像である。

 \mathbb{Z} / m \mathbb{Z} での計算が  \displaystyle \prod_{i=1}^{n} \mathbb{Z} / m_i \mathbb{Z} での計算に帰着できる。
 mod\ m の剰余類を  mod\ m_i の剰余類の組に移し、組の各成分ごとに計算し、中国人の剰余定理で結果を  mod\ m の剰余類に戻す。

3.17 オイラー \varphi 関数の決定

 m_1,\ \ \ \  ...,\ \ \ \  m_n を互いに素な自然数とし、 m = \prod_{i=1}^{n} m_i とする。
このとき、 \varphi(m) = \varphi(m_1) \varphi(m_2) \ \ ...\ \ \varphi(m_n) である。

 m自然数 m = \prod_{p | m} p^{e(p)} をその素因数分解とする。そのとき

  \displaystyle \varphi(m) = \prod_{p|m} (p - 1) p^{e(p)-1} = m \prod_{p|m} \frac{p-1}{p}
が成立する。

例. \varphi(100) = \varphi(2^{2} * 5^{2}) = 1 * 2 * 4 * 5 = 40 が成立する。

 m因数分解がわかっている場合、 \varphi は時間 O((size\ m)^{2}) で計算される。

3.18 多項式

 R は単位元 1 \ne 0 をもつ可換環とする。R 上の一変数の多項式(polynomial)とは
  f(x) = a_n x^{n} + a_{n-1} x^{n-1} +\ \ \ ... \ \ \ + a_1 x + a_0
と表されるもののことである。
変数 x についての R 上のすべての多項式の集合は R[x] で表される。
 a_n \ne 0 とする。このとき n多項式の次数といい、 n = deg\ f と書く。