数论与群论密码学-03-模算术

同余

\(a, b \in \mathbb{Z}\)\(m \in \mathbb{Z}+\), 且有 \(rem(a, m) = rem(b, m)\),则称数 \(a\)\(b\) 对于模 \(m\) 同余。记为 \[a \equiv b \pmod m\]

易证,

\[ a \equiv b \pmod m \iff m \mid a-b \]

同时,有

\[ \begin{aligned} a \equiv a' \pmod m,~b \equiv b' \pmod m &\implies a \pm b \equiv a' \pm b' \pmod m\\ " &\implies ab \equiv a'b' \pmod m \end{aligned} \]

可证,同余关系符合自反性,对称性,传递性,因此为等价关系。据此,可将整数集 \(\mathbb{Z}\) 划分为非空,互不相交(相互排斥),且覆盖 \(\mathbb{Z}\)(全无遗漏)的子集。

由此,定义 \(\mathbb{Z}/m\mathbb{Z} := \text{模 $m$ 余数的集合} = \{[0], [1], \cdots, [m-1]\}\)。出于简便,从每一等价类中选取 \(0 \le a < m\) 作为代表,即将前述集合记为 \(\{0, 1, \cdots, m-1\}\). 称该集合为 整数模 \(m\)\(m\) 即约剩余类,后文使用前一种名称。

在有必要时通过下标指定等价类的模,如 \(\left[a\right]_m\).

模算术

定义

\[ [a] \pm [b] = [rem(a \pm b, m)]\\ [a][b] = [rem(ab, m)] \]

如此则有 \(\mathbb{Z}/m\mathbb{Z}\) 上的加法/乘法运算。因此 \(\mathbb{Z}/m\mathbb{Z}\) 构成一个代数环。

根据 \(\mathbb{Z}\) 中各运算的复杂度,可得 \(\mathbb{Z}/m\mathbb{Z}\) 中计算加法复杂度为 \(\Theta(log(m))\),乘法为 \(\Theta(log^2(m))\)

定义除法运算 \(\left[a\right]/\left[b\right] =: x\) 为满足下式的元素:

\[a x \equiv b \pmod m\]

\(a x \equiv b \pmod m\) 的解

  1. 上式有解当且仅当 \[gcd(a, m) \mid b\]

  2. \(g = gcd(a, m) \mid b\),那么上式有确切 \(g\) 个模 \(m\) 下截然不同的解,这些解由下式给出:

    \[ x \equiv \frac{b}{g} x_0 + \frac{m}{g} t \pmod m,~ t = 0, \cdots g-1 \]

    其中 \(x_0\)\(a x_0 \equiv g \pmod m\) 的任意一个解。

该定理可由以下事实注意到:

\[ \begin{aligned} ax \equiv b \pmod m &\iff m \mid ax-b\\ &\iff \exists y \in \mathbb{Z}, ax-b=my\\ &\iff \exists y \in \mathbb{Z}, ax-my=b \end{aligned} \]

定理 5 中的解可由 \(\Theta(log^2(m))\) 位操作求出。

元素 \([a] \in \mathbb{Z}/m\mathbb{Z}\) 有逆当且仅当 \(gcd(a, m) = 1\)

\[ \begin{aligned} \left[a\right]^{-1}~\text{存在} &\iff [a]x \equiv 1 \pmod m~\text{有解}\\ &根据定理 5 \\ &\iff gcd(a, m) \mid 1\\ &\iff gcd(a, m) = 1 \end{aligned} \]

整数模 m 乘法群 (整数模 n 乘法群)

我们记 \(\mathbb{Z}/m\mathbb{Z}\) 中可逆元素的集合为:

\[ (\mathbb{Z}/m\mathbb{Z})^\times := \{[a] \in \mathbb{Z}/m\mathbb{Z} : gcd(a, m) = 1\} \]

又记该集合的势为:

\[ \phi(m) := \big|(\mathbb{Z}/m\mathbb{Z})^\times\big| := \big| \{1 \le a\le m: gcd(a, m) = 1\} \big| \]

该函数被称为欧拉 \(\phi\) 函数。随后我们会证明,该函数不可在多项式时间内求解。

注:
1). \((\mathbb{Z}/m\mathbb{Z})^\times\) 在乘法下构成一个群,即其在乘法及乘法逆下封闭。
2). 对于任何环 \(R\),集合 \(R^\times := \{a\in R : ax=1~\text{在}~R~\text{中有唯一解}\}\) 被称作 \(R\) 的可逆元群。

欧拉 \(\phi\) 函数

根据定义,若 \(m=p\) 是素数,则 \((\mathbb{Z}/m\mathbb{Z})^\times = \{[1], \cdots ,[p-1]\}\),因此 \(\phi(p) = p-1\)

\(m = p^r\) 是指数的整数次方,则

\[ \require{cancel} \begin{aligned} (\mathbb{Z}/p^r\mathbb{Z})^\times = \{ &\bcancel{[0]}, [1], \cdots, [p-1],\\ &\bcancel{[p]}, [p+1], \cdots, [2p-1],\\ &\cdots,\\ &\bcancel{[p^{r-1}]}, [p^{r-1}+1]\cdots, [p^r -1] \} \end{aligned} \]

即排除所有 \(p^r\) 以内的 \(p\) 的倍数。因此:

\[\phi(p^r) = p^r - p^{r-1} = p^{r-1}(p-1)\]

更一般地,有以下

\(gcd(m, a) = 1\),则 \[ \phi(mn) = \phi(m)\phi(n) \tag{1} \]

因此,若 \(m = p_1^{r_1} \cdots p_t^{r_t}\),其中 \(p_i\) 为不同的素数且 \(r_i \ge 1\),则有

\[ \phi(m) = \prod_{i=1}^t p_i^{r_i-1}(p_i-1) = m \prod_{p \mid m} (1 - \frac{1}{p}) \tag{2} \]

注意到虽然这是一个显式的计算欧拉 \(\phi\) 函数的公式,由于目前没有人类已知的在多项式时间内计算 \(m\) 的素数分解的算法,该公式因此并非是多项式时间可计算的。

我们随后将要看到,式 (1) 是中国剩余定理 (CRT) 的结论。而通过对式 (1) 中的 \(t\) 进行数学归纳,可证式 (2) 的第一部分。下面给出第二部分的证明:

\[ p_i^{r_i-1}(p_i-1) = p_i(1-\frac{1}{i_i})\\ \prod_{i=1}^t p_i^{r_i-1}(p_i-1) = \underbrace{\prod_{i=1}^t (p_i^{r_1})}_{m} \prod_{i=1}^t (1-\frac{1}{p_i}) \]

欧拉使用该函数证明了以下定理:

欧拉定理(费马-欧拉定理)

\(gcd(a, m) = 1\),有 \(a^{\phi(m)} \equiv 1 \pmod m\).

该定理是以下定理的推广,彼为此的直接推论。

费马小定理

\(p\) 为素数,则 \[ \forall a \in \mathbb{Z}, a^p \equiv a\pmod p \]

\(gcd(a, m) = 1\),则根据定理 6,有 \[a^{p-1} \equiv 1 \pmod m\] 因此有 \[a^p \equiv a \pmod m\]\(gcd(a, p) > 1\),则必然有 \(p \mid a\),那么 \(a \equiv 0 \pmod p\),那么式两边皆于模 \(p\) 下同余 0,因此相等。

我们将在随后证明定理 7,作为一个更一般的定理的结论。