1. 同余式

基本概念

1. 设 $m$ 正整数，$f(x)$ 多项式 $f(x)=a_nx_n+\cdots +a_1x+a_0$，其中$a_i$是整数，则 $f(x)\equiv0 \pmod m$叫做模 $m$ 的同余式，若 $a_n \equiv 0 \pmod m$，则 $n$ 叫作 $f(x)$ 的次数，记为 $deg(f)$。$f(x)\equiv0 \pmod m$ 又称作模 $m$ 的 $n$ 次同余式。

2. 如果整数 $a$ 使得 $f(x)\equiv0 \pmod m$ 成立，则 $a$ 为其的解，表达为 $x\equiv a \pmod m$。

逆元

设 $a,m$ 是正整数，$\gcd(a,m)=1$，则有 $a’,1 \le a’ < m$，使得$aa’\equiv 1\pmod m$。且 $a’$ 唯一，所有解为 $a’+km$，在模 $m$ 情况下，均为 $a’$。

性质

1. 设 $a\nmid m$，则一次同余式 $ax \equiv b \pmod m$ 有解的充要条件是 $\gcd(a,m) \mid b$，且有解时，解的数量为 $d = \gcd(a,m)$。
   • 必要性：设有解 $x \equiv x_0 \pmod m$，则有 $ax_0-my_0=b$ 。因为$(a,m)\mid a,(a,m)\mid m$，所有 $(a,m)\mid ax_0-my_0=b$ 。
   • 充分性：考虑 $\frac a{\gcd(a,m)}x\equiv \frac b{\gcd(a,m)} \pmod {\frac m{\gcd(a,m)}}$。
     由于 $\gcd(\frac a{\gcd(a,m)},\frac m{\gcd(a,m)})=1$，所以 $x\equiv x_0\equiv(\frac a{\gcd(a,m)})^{-1}\frac b{\gcd(a,m)} \pmod {\frac m{\gcd(a,m)}}$ 是一个特解，所有的解可以表示为 $x_0+k\frac m{\gcd(a,m)} \pmod m$。
     接下来分析解的数量，$k\frac m{\gcd(a,m)}$ 在模 $m$ 的情况下，共有 $\gcd(a,m)$ 个不同取值，故解的数量为$\gcd(a,m)$。
2. 设 $\gcd(a,m)\mid b$，则一次同余式 $ax \equiv b \pmod m$ 的全部解为 $(\frac a{\gcd(a,m)})^{-1}\frac b{\gcd(a,m)}\%\frac m{\gcd(a,m)}+ k\frac m{\gcd(a,m)}\pmod m,k\in \lbrace 0,1,…,\gcd(a,m)-1 \rbrace$。

2. 中国剩余定理

设 $m_1,\cdots,m_k$ 是 $k$ 个两两互素的正整数。则对任意的整数 $b_1,..,b_k$，同余式组：

一定有解，且解唯一。令 $m=m_1m_2\cdots m_k,M_i=mm_i^{-1}$，则同组的解可以表示为:

其中 $M_i’=M_i^{-1} \pmod{m_i}$，证明方法代入即可。关于该解为啥是最小整数解，可设另一个解为 $x’$，则 $s=(x’-x)$ 需满足取余所有的 $m_i$ 均为0，故 $m\mid x$，解的集合为 $X =x+km$，取余 $m$ 时 $x$ 自然是最小的正整数解。

3. 原根

概念

设 $p$ 是正整数，$a$ 是整数，若 $a$ 模 $p$ 的阶等于 $\varphi(p)$，则称 $a$ 为模 $p$ 的一个原根。

素数情况

对于所有的 $a\in [2,p-1]$，$p_i$ 为 $p$的质因子，恒有：

原根性质

• 如果一个数有原根，那么它一共有 $\varphi(\varphi(m))$ 个原根。
• 如果 $p$ 为素数，那么素数 $p$ 一定存在原根，并且模 $p$ 的原根的个数为 $\varphi(p-1)$ 个。

4. Pohig-Hellman算法

整体流程

• 同小步大步方法，求解离散对数 $b\equiv a^x \pmod p$ 中的 $a$。($p$ 为素数)

• 当 $g$ 为 $p$ 的原根时，有 $a\equiv g^{a’} \pmod p,b\equiv g^{b’} \pmod p $

• 即当 $b\equiv a^x \pmod p$ 时，有 $g^{a’x} \equiv g^{b’} \pmod p$，又可以推出 $a’x \equiv b’\pmod {(p-1)}$，因为$g^{p-1} \equiv 1 \pmod {(p-1)}$。接下来关键在于如何求解 $a’,b’$

• 有$g^{a’} \equiv a \pmod p,g^{b’} \equiv b \pmod p$，利用 Pohig-Hellman 算法求得 $a’,b’$，再使扩展GCD求解 $a’x \equiv b \pmod {(p-1)}$，其中 $x$ 即为最终结果

Pohig-Hellman算法过程

下面开始介绍 Pohig-Hellman 算法，即求解$g^x \equiv b \pmod p$，要求 $g$ 是 $p$ 的最小原根

1. 将 $ n = \varphi (p)=p-1 $ 进行标准的素因子分解，$n = \prod _{i=0}^kq_i^{a_i}$，$q_i$ 为素因子，$a_i$为幂次
2. 对于每个素因子，将 $x$ 可以转写成 $q_i$ 进制，且对 $q_i^{a_i}$取模，即 $x = \prod_{j=0}^{a_i-1}b_jq_i^j$，其中$b_j$为系数
3. 由$b\equiv a^x \pmod p$，可得$b^{\frac n{q_i^r}} \equiv (a^{\frac n{q_i^r}})^x \pmod p$，开始令 $r=1$
4. 展开 $x$ 有 $(a^{\prod_{j=0}^{a_i-1}b_jq_i^j})^{n/q_i} \equiv b^{n/q_i} \pmod p$，$a^{b_0{\frac n{q_i}}}a^{b_1q_i^1{\frac n{q_i}}}\cdots a^{b_kq_i^k{\frac n{q_i}}} \equiv b^{n/q_i} \pmod p$
5. 由于 $a^n \equiv1 \pmod p$，故上式可化简为$a^{b_0{\frac n{q_i}}}\equiv b^{\frac n{q_i}} \pmod p$，其中 $b_0$ 在 $q_i$ 进制下小于 $q_i$，则可以在 $O(q_i)$ 的时间内暴力解得 $a_0$
6. 回到第 $3$ 步，逐步增加 $r$，求求得所有的 $a_i$，最后可以求得 $x \pmod{q_i^{a_i}}$ 的值
7. 最后有 $k$ 个同余方程，使用中国剩余定理求出最终的 $x \pmod p$

5. 高次同余方式的解数和解法

基本性质

求解 $f(x)\equiv0 \pmod m $ 可以转化为多个式子，其中 $m_i$ 两两互素：

假设解为：

考虑 $B_i$ 的所有组合情况，并使用中国剩余定理便可以求出所有解

同余式求解

• $f’(x)$ 是 $f’(x)$ 的导式
• 设 $x\equiv x_1 \pmod q$ 是$f(x) \equiv 0 \pmod q $的一个解，且 $\gcd(f’(x),q)=1$，则 $f(x)\equiv 0 \pmod {q^a} $ 有解 $x \equiv x_a \pmod {q^a}$
• 其中 $x_a$ 由下面的关系式递归得到：

• 可以通过归纳法证明

一些性质

• $f(x+yp^i) \equiv f(x )\pmod {p^i}$
• 设$x_0 \pmod p$ 是 $f(x)\equiv0 \pmod p$ 的一个根。则有 $f’(x) \not\equiv 0 \pmod p \Leftrightarrow x_0 \pmod {x_0}$ 是 $f(x) \equiv 0 \pmod p$的一个单根

6. 同余数解数

多项式欧几里得除法

设 $f(x)=a_nx^n+\cdots+a_1x+a_0$ 为 $n$ 次整系数多项式，$g(x) = x_m+\cdots+b_1x+b_0$ 为 $m\ge 1$ 次首一的整系数多项式，则存在整系数多项式 $q(x)$ 和 $r(x)$ 使得

性质：

1. 同余式 $f(x)=a_nx^n+\cdots+a_1x+a_0 \pmod p$ 与一个次数不超过 $p-1$ 模 $p$ 同余式等价。证明通过除法配出 $x^p+x$的项即可。
2. 设 $1\le k\le n$。如果 $x \equiv a_i \pmod p$ 是 $f(x)= a_nx^n + \cdots + a_1x +a_0 \equiv 0 \pmod p$ 的 $k$ 个不同解，则任何整数 $x$，都有 $f(x) \equiv (x-a_1)\cdots (x-a_k)f_k(x)\pmod p$ ，其中 $f_k(x)$ 是 $n-k$ 次多项式，首项系数是 $a_n$。证明通过逐渐提出 $(x-a_i)$的项即可。
3. 同余式 $f(x)=a_nx^n+\cdots+a_1x+a_0 \pmod p,\ p\nmid a_n$ 的解数不超过它的次数。基于第 $2$ 条反证即可以。