数学基础

最大公约数

设 a、b 为整数，且 a、b 中至少有一个不等于 0，令 d=gcd(a,b)，则一定存在整数 x、y 使得下式成立： $a \times x + b \times y = d$

素数与互素

若 gcd(a, b) = 1，则称 a、b 互素

模运算与同余

$a \equiv b \mod n$
可以理解为 a%n == b%n

逆元 (inverse)

加法逆元 $a + b = 0 \mod n$
- $明文 + 密钥 \equiv 密文 \mod n$ ， $密文 + 密钥逆元 \equiv 明文 \mod n$
乘法逆元 $a * b = 1 \mod n$
- $明文 \times 密钥 \equiv 密文 \mod n$ ， $密文 \times 密钥逆元 \equiv 明文 \mod n$
- 充要条件 $gcd (a, n) = 1$
- 求法：扩展欧几里得

拓展欧几里得

拓展欧几里得可以用来求乘法逆元，下面是一个例子：

例如求 13*x ≡ 1 (mod 35)
35 = 2*13+ 9
13 = 1*9 + 4
9  = 2*4 + 1

1 = 9-(2*4) 
  = (35 - 2*13) - (2*(13-1*9))
  = 35 - 2*13 - 2*(13-1*(35-2*13))
  = 35 - 2*13 - 2*13 + 2*(35-2*13)
  = 3*35 - 8*13
所以 (-8)*13 ≡ 1 (mod 35)
又因为 -8 ≡ 27 (mod 35)
所以 13*27 ≡ 1 (mod 35)
13在模35的情况下，乘法逆元为27

裴蜀定理 gcd(x,y) = ax + by

根据欧几里得算法

x = x0;
y = y0;
while(y){
	int q = y/x;
	int r = y%x;
	y = x;
	x = r;
}

证明，在每一轮循环中，都有

\begin{aligned} x_{i} = a_{i 1} x_{0} + b_{i 1} y_{0} \\ y_{i} = a_{i 2} x_{0} + b_{i 2} y_{0} \end{aligned}

使用数学归纳法

i = 1 时， $x = x_{0}$ ， $y = y_{0}$ ，即 $a_{i 1} = 1, b_{i 1} = 0, a_{i 2} = 0, b_{i 2} = 1$
i >= 1 时，若 i 满足上述条件，则
- $y_{i + 1} = x_{i} = a_{i 1} x_{0} + b_{i 1} y_{0}$ ， $a_{(i + 1) 2} = a_{i 1}, b_{(i + 1) 2} = b_{i 1}$
- $x_{i + 1} = y_{i} % x_{i} = (a_{i 2} x_{0} + b_{i 2} y) - k * (a_{i 1} x_{0} + b_{i 1} y_{0}) = (a_{i 2} - k a_{i 1}) x_{0} + (b_{i 2} - k b_{i 1}) y_{0}$ ， $a_{(i + 1) 1} = a_{i 2} - k a_{i 1}$ ， $b_{(i + 1) 1} = b_{i 2} - k b_{i 1}$

Q.E.D

中国剩余定理

设 $m_{1}, m_{2}, m_{3}, . . ., m_{r}$ 两两互素，则以下同余方程组
$x \equiv a_{i} \mod m_{i}, i = 1, 2, 3, . . ., r$
模 $M = m_{1} m_{2} m_{3} . . . m_{r}$ 的唯一解为
$x = \sum_{i = 1}^{r} a_{i} * M_{i} * (M_{i}^{- 1} m o d m_{i}) \mod M$ ，其中 $M_{i} = M / m_{i}$
（1）先证明 x 为同余方程的解
因为 $M_{i} \equiv 0 \mod m_{j} (i \neq j)$ ，所以 $x \equiv a_{j} \mod m_{j}$
（2）再证明 x 是唯一解
假设上述同余方程组有两个解 $0 \leq x_{1}, x_{2} < M$ ，
则

\begin{aligned} x_{1} & \equiv a_{i} \mod m_{i} \\ x_{2} & \equiv a_{i} \mod m_{i} \\ \to x_{1} - x_{2} & \equiv 0 \mod m_{i} \end{aligned}

又因为 $m_{1}, m_{2}, m_{3}, . . ., m_{r}$ 两两互素，所以 $x_{1} = k * M + x_{2}$ ，与假设矛盾
Q.E.D

Euler 准则

对于整数 x 和奇素数 p，x 是模 p 的平方剩余（ $y^{2} \equiv x \mod p$ ）的充要条件是 $x^{(p - 1) / 2} \equiv 1 \mod p$

证明：
（1）必要性
因为 gcd(x,p)=1, $y^{2} \equiv x \mod p$ ，
所以 gcd(y,p)=1
根据费马小定理， $y^{p - 1} \equiv 1 \mod p$
所以 $x^{(p - 1) / 2} \equiv 1 \mod p$
（2）充分性
不妨设 $x \in Z_{p}$ ，因为 $Z_{p}^{*}$ ={1,2,3,...,p-1} 在模 p 乘法下是循环群，所以一定存在 $Z_{p}^{*}$ 的一个生成元 b，使得 $x \equiv b^{i} \mod p$
因为 $x^{(p - 1) / 2} \equiv 1 \mod p$
所以 $b^{i (p - 1) / 2} = (b^{p - 1})^{i / 2} \equiv 1 \mod p$
又因为 $b^{p - 1} \equiv 1 \mod p$ ，所以 i 为偶数
所以 x 模 p 的平方根必有整数解，其值为 $\pm b^{i / 2}$
Q.E.D