【信息安全数学基础】同余式

可以简单点理解为上一章学习的同余的概念中混入了x（手动滑稽）

同余式的基本概念

• 什么是同余式？

设m是一个正整数，f（x）为多项式；

$f(x) = a_nx^n + \cdot \cdot \cdot +a_1x +a_0$

其中$a_i为$整数，则：

$f(x) \equiv 0(mod \ n)$

叫做模m的同余式，如果$a_n \not\equiv 0(mod \ m)$,则n叫做f(x)的次数，记作degf. 如果整数x=a满足：

$f(a) \equiv 0(mod \ m)$

则a叫做该同余式的解；$x \equiv a (mod \ m)$的所有整数都使得同余式成立，即a所在的剩余类。

一次同余式🌿

由于1次以上的同余式都太复杂了，所以手算程度上我们主要掌握的是一次同余式；

一次同余式解的存在性判定：🌟

$ax \equiv n(mod \ m)$

有解的充分必要条件是(a,m)=n,而且，解是唯一的

模m的可逆元

设m是一个正整数，a是一个整数，如果整数a‘存在使得：

$a \cdot a' \equiv a' \cdot a \equiv 1 (mod \ m)$

成立，则a叫做模m的可逆元；

模m的同余的求解：🌟

• 第一步：均是判断解的存在性，存在之后再去进行下一步的求解，运用到上面那一个问题的解答；
• 对于一次同余式$ax \equiv 1 \ mod \ m$就是解，且具有唯一性； P92
• 一次同余式一般式$ax \equiv b \ mod \ m$; P94

一道例题：

求解一次同余式

$33x = 22(mod \ 77)$

解：首先计算（33.77）= 11 ｜22，所以该同余式有解；

接下来对上述同余式同时除以11，可以得到：

$3x = 2(mod \ 7)$

现在把2用1来替换可以得到：

$3x=1(mod \ 7)$

很容易可以求得特殊解：$x_0' = 5$

再次写出：

$3x = 2(mod \ 7)$

的一个特解是$x_0 \equiv 2 \cdot x_0' \equiv 2 \cdot 5 \equiv 3 (mod \ 7)$

最后可以写出同余式的解：

$x = 3+t \cdot 7(mod \ 77),t=0,1,2 \cdot \cdot \cdot \cdot$

注意这里的为模77

中国剩余定理 🌿

用于求解同余式组 P97

设$m_1,m_2,\cdot \cdot \cdot$同余式组：

$\begin{cases} x \equiv (mod \ m_1) \\ ...\\ x \equiv (mod \ m_k) \\ \end{cases}$

一定有解，且解是唯一的；

若令：

$m=m_1 \cdot \cdot \cdot m_k,m = m_i \cdot M_i, i=1, \cdot \cdot \cdot,k$

则同余式组的解可表示为

$x \equiv b_1 \cdot M_1' \cdot M_1 + b_2 \cdot M_2' \cdot M_2 + \cdot \cdot \cdot + b_k \cdot M_k' \cdot M_k(mod \ m)$

其中

$M_i' \cdot M_i \equiv 1 (mod \ m_i), i=1,2,\cdot \cdot \cdot,k$

中国剩余定理的应用 ==》 一些例题

计算$2^{1000000}(mod \ 77)$

解：令x = $2^{1000000}$ . 因为 77 = 11 * 7 ，所以计算x mod 77 可以等价于求解两个同余式：

$\begin{cases} x \equiv b1 \ (mod \ 11) \\ x \equiv b2 \ (mod \ 7) \\ \end{cases}$

由Euler定理可得：

$2^{\phi(11)} \equiv 2^{10} \equiv 1 (mod \ 11)$

那么就可以得到：

$x \equiv (2^{10})^{100000} \equiv 1 (mod \ 11)$ 则 b1 = 1

同理有:

$x \equiv (2^{6})^{166666} \cdot 2^4 \equiv 2 (mod \ 7)$

则b2 = 2 令m2 = 11 , m1 = 7，则 m = 11 * 7 = 77.
$M_1 = m_2 = 11,M_2 = m_1 = 7$

可以得到：

$11M_1' \equiv 1(mod \ 7)\\ 7M_2' \equiv 1 (mod \ 11)$

最后可以得到结果：

$x \equiv 2 \cdot 11 \cdot 2 + 1 \cdot 8 \cdot 7 \ (mod \ 77) \\ x \equiv 23 \ (mod \ 77)$

---

计算 $312^{13}(mod \ 667)$ （中国剩余定理和模重复平方法的结合）

解：令x = $312^{13}$, 667 = 23 * 29

则同余式可以化为：

$\begin{cases} x \equiv b1 \ (mod \ 23) \\ x \equiv b2 \ (mod \ 29) \\ \end{cases}$

由模重复平方法可得：$b1 \equiv 313^{13} \equiv 8(mod \ 23)$;

令m1 = 23；m2 = 29：

则M1 = 29，M2 = 23；

可以得到：

$29M_1' \equiv 1(mod \ 23)\\ 23M_2' \equiv 1(mod \ 29)$

解得：

$x \equiv 8 \cdot 4 \cdot 29 + 4 \cdot (-5) \cdot 23 (mod \ 667) \equiv 468 (mod \ 667)$