零、前情提要

总所周知，我是一个纯血web狗，可能会些misc，会点reverse，会一点点pwn，但是密码绝对是0基础，被某二比密码手骗入职了新公司，新公司给我的第一任务就是准备熵密杯…既然躲不掉，那就只能重拾数学课本开始了。

一、初等数论

基本数学概念

整除

若 $a = b \times k$（k为整数），则称b整除a，记作 $b \mid a$。 例如 $3 \mid 12$，因为 $12 = 3 \times 4$。

质数与合数

质数：大于1且只能被1和自身整除的数（如2、3、5、7…）。 合数：大于1且能被其他数整除的数（如4、6、8、9…）。 1既不是质数也不是合数。

质因数分解

每个大于1的整数都可以唯一分解为质数的乘积。 例如 $60 = 2^2 \times 3 \times 5$。

模运算

a除以m的余数，称为a在模m下的余数，记作 $a \mod m$。 例如 $17 \mod 5 = 2$，因为 $17 = 5 \times 3 + 2$。

同余

若两个整数a和b除以m的余数相同，则称a与b在模m下同余，记作 $a \equiv b \pmod{m}$。 例如 $17 \equiv 2 \pmod{5}$，$-3 \equiv 4 \pmod{7}$。

乘法逆元

若 $a \times x \equiv 1 \pmod{m}$，则称x为a在模m下的乘法逆元，记作 $a^{-1}$。 只有当 $gcd(a,m)=1$ 时，a在模m下才存在乘法逆元。 例如 $3^{-1} \equiv 4 \pmod{11}$，因为 $3 \times 4 = 12 \equiv 1 \pmod{11}$。

费马小定理

若p为质数，a不是p的倍数，则 $a^{p-1} \equiv 1 \pmod{p}$，如果是倍数则是$a^{p-1} \equiv 0 \pmod{p}$。 等价形式：$a^p \equiv a \pmod{p}$。

欧拉函数 $\varphi(n)$

小于n且与n互素的正整数个数。质数p时 $\varphi(p) = p-1$。 若 $n = p \times q$（p、q为质数），则 $\varphi(n) = (p-1)(q-1)$。

欧拉定理

若 $gcd(a,m)=1$，则 $a^{\varphi(m)} \equiv 1 \pmod{m}$。 费马小定理是欧拉定理在m为质数时的特例。

二次剩余定理

设 $p$ 为奇质数，$a$ 为整数且 $p \nmid a$，若同余方程

$$x^2 \equiv a \pmod{p}$$

有解，则称 $a$ 是模 $p$ 的二次剩余，否则称为二次非剩余。 例如模 7 下，$1^2\equiv1$，$2^2\equiv4$，$3^2\equiv2$，故 $\{1,2,4\}$ 是二次剩余，$\{3,5,6\}$ 是二次非剩余。

二次剩余基本性质

1. 模 $p$ 下恰好有 $\frac{p-1}{2}$ 个二次剩余和 $\frac{p-1}{2}$ 个二次非剩余。
2. 乘法规律：$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$。
3. $-1$ 是模 $p$ 的二次剩余 $\iff p \equiv 1 \pmod 4$。
4. 2 是模 $p$ 的二次剩余 $\iff p \equiv \pm 1 \pmod 8$。
5. 二次剩余之积仍为二次剩余；二次剩余与二次非剩余之积为二次非剩余。

基础算法

欧几里得算法 (GCD)

两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。 例如求252和101的最大公约数，那么首先就是$252\mod101=42$，那么252和101的最大公约数就等效为101和42的最大公约数，依此类推，直至余数变为0，剩下那个数就是最大公约数。 欲求最大公约数的两个数为 $a,b$ ，第$i$步带余除法得到的商为 $q_i$ ,余数为 $r_{i+1}$ 。

$$a = b · q_0 + r_1 (0\leq r_1 \leq b)$$

gcd(a,b)=gcd(b,r_1)

同时假设$r_0 = a,r_1 = b$那么公式就变成了

$$r_{i+1}=r_{i-1}-q_i r_i$$

$r_{i+1} = 0$ 时计算结束 求两数最大公约数一般简写为 $gcd(a,b)$，如果$gcd(a,b)=1$则ab互素(两数最大公因数为1)。 python实现

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

扩展欧几里得算法(EXGCD)

代入额外两个数求出 $ax+by=gcd(a,b)$ 中的x、y，其主要作用是用来求解模反元素、线性同余方程等。

扩展欧几里得算法在欧几里得算法的基础上加了两个序列，记 $s_i$ 和 $t_i$ ，且初始 $s_0 = 1$ ,$s_1 = 0$和 $t_0 = 0$和 $t_1 = 1$，然后在原算式算完后多加两步额外计算。$s_{i+1} = s_{i-1}-q_is_i$ 和 $t_{i+1} = t_{i-1}-q_it_i$ 。 python实现

def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    d, x, y = exgcd(b, a % b)
    return d, y, x - (a // b) * y

求解模线性方程

解

$$ax \equiv c\pmod{b}$$

等价于

$$ax+by=c$$

求乘法逆元

若 $gcd(a,m)=1$，则存在x使 $ax\equiv1(mod\ m)$，即x为a模m的逆元。通过扩展欧几里得解 $ax+my=1$得到 x，然后调整到 $[0,m−1]$ 范围。

中国剩余定理(CRT)

设模数 $m_1,m_2,…,m_n$ 两两互素，即对任意 $i \neq j$，都有 $gcd(m_i,m_j)=1$ 。 那么对于任意整数 $a_1,a_2,…,a_n$ ，同余方程组

$$\begin{cases} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ ...\\ x\equiv a_i\pmod{m_i} \end{cases}$$

在模 $M=m_1,m_2,…,m_i$ 有唯一解，即存在x满足所有条件 公式

$$x=\sum a_iM_iN_i$$

最后去模得到答案

$$x\pmod{M}$$

举例

$$\begin{cases} x\equiv 2\pmod{3}\\ x\equiv 3\pmod{5}\\ x\equiv 2\pmod{7} \end{cases}$$

先求$M$

$$M=2\times5\times7=105$$

然后构造$M_i=\frac{M}{m_i}$，得到$M_1=35,M_2=21,M_3=15$ 求$N_i$，即求

$$N_i=M_i^{-1}\pmod{m_i}$$

得到$N_1=2,N_2=1,N_3=1$ 最后带入公式

$$x=\sum a_iM_iN_i$$ $$x=2×35×2+3×21×1+2×15×1=140+63+30=140+63+30=140+63+30=233$$

取模 $233\mod105=23$，所以x的解就是23

扩展中国剩余定理(EXCRT)

常规CRT只能解决m互素的问题，即$gcd(m_i,m_j)=1$ 那么EXCRT就是解决CRT解决不了的问题，同时存在无解，对于同余方程组

$$\begin{cases} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2} \end{cases}$$

令$g=gcd(m1,m2)$，那么就绪满足$g\mid a_2−a_1$，即$(a_2−a_1)\equiv 0 \pmod{g}$，否则无解 然后来看核心推导 第一条等同于，$x=a_1+km_1$ 带入第二条就变成了$a_1+km_1\equiv a_2\pmod{m_2}$ 整理一下就变成这样

$$m_1k\equiv a_2-a_1 \pmod{m_2}$$

那么接下来就是exgcd的作用求出k即可，因为上式子变形得到

$$m_1k-m_2t=a_2-a_1$$

那么不就是$m_1k+m_2(-t)=a_2-a_1$的形式吗，然后就是$exgcd(m1,m2)$求出k的值带回算式$x=a_1+km_1$得到最终答案

举例

$$\begin{cases} x\equiv 1\pmod{4}\\ x\equiv 3\pmod{6} \end{cases}$$

得到

$$4k\equiv 2 \pmod{6}$$

即

$$4k-6t=2\Rightarrow 4k+6(-t)=2$$

变一下

$$4u+6v=2$$

扩展欧几里得求解

$i$	$q_{i-1}$	$r_i$	$u_i$	$v_i$
0		6	1	0
1		4	0	1
2	1	2	1	-1
3	2	0

所以$u=1,v=-1$，k=1的情况带回前面$4k-6t=2$不成立，那么就是k=-1

$$x=1+4\times -1=-3$$

最后如果要取正整数解x就为9

如果同余方程组有多组的话，一步一步合并即可

持续学习中…