余数 #
若整数m, n, k, r满足 m = kn + r，且 n ≠ 0，0 ≤ r < n，则称 r 是 m 对 n 的余数(Reminder)
举例来说，13 = 2 * 5 + 3，其中 3 就是 13 除以 5 的余数
质数 #
质数(Prime)也叫素数，定义为只能被1和其自身整数的正整数，如 2，3，5，7，11，13 等
质数是一类非常特别的数据，相关研究非常多
著名的哥德巴赫猜想的内容就是“任何一个大于2的偶数是否都可以表示为两个质数的和”，如20 = 13 + 7（目前数学界还无法证明，也无法证伪）
分解质因数 #
每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。
并且如果把质因数按照由小到大的顺序排列在一起，相同的因数的积写成幂的形式，那么这种分解方法是唯一的
如 60 = 2 * 2 * 3 * 5 = 2^2 * 3 * 5
最大公约数 #
GCD(greatest common divisor)表示不全为0的2个或多个整数的最大公有约数
12、16的公约数有1、2、4，其中最大的一个是4，记作
gcd(12, 16) = 4
互质和公约数的关系
两数互质(Relatively Prime)的充分必要条件是两数的最大公约数为 1，如3和10互斥，gcd(3, 10) = 1
裴蜀定理 #
裴蜀定理，又称贝祖定理，是一个关于最大公约数的定理
若a，b是整数，且gcd(a, b) = d，那么对于任意的整数x, y，ax + by都一定是 d 的倍数
特别地，一定存在整数x, y，使ax + by = d成立
推论：a, b互质的充分必要条件是存在整数x, y使ax + by = 1
换句话说gcd(a, b)可以表示为a, b的整系数线性组合
同余 #
同余（congruence modulo，符号≡）是数论中的一种等价关系。两个整数a, b，若它们除以正整数 m 所得的余数相等，则称a, b对于模 m 同余
记作
a ≡ b (mod n)
即存在非零整数 k，使得a = b + nk
模逆元 #
对整数 a 和 b，若
ab ≡ 1 (mod n)
则称 a 和 b 关于模 n 互为模倒数，也叫数论倒数、模反元素或模逆元（modular multiplicative inverse）还有如倒数、-1记法
模逆元和互质的关系
根据以上裴蜀定理，已知整数 a, b，gcd(a, b) = d 则一定存在整数x, y，使ax + by = d成立（可以使用扩展欧几里得算法可以求出整数x, y见下）
对 ax + by = d 两边同模n
根据分配律：(ax + by) mod b = [(ax mod b) + (by mod b)] mod b = ax mod b = d mod b 即
ax ≡ d (mod b)
当a, b互质时，d = 1，此时 x 就是 a 关于模 b 的逆元
a, b互质的充分必要条件是d = 1，也就是说，a 关于模 b 的模逆元存在的充分必要条件是 a 和 b 互质，a? ≡ 1 (mod b)
（扩展）欧几里得算法 #
欧几里得算法(Euclidean algorithm)又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数
古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法，所以被命名为欧几里得算法
计算方法
gcd(a, b) = gcd(b, a mod b) = ... = gcd(?, 0) = ?
求 1997 和 615 两个正整数的最大公约数：
1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1
def gcd(a, b):
if a == 0:
return b
return gcd(b % a, a)
if __name__ == "__main__":
a = 10
b = 15
print(gcd(a, b)) # 5
a = 1997
b = 615
print(gcd(a, b)) # 1
a = 5
b = 7
print(gcd(a, b)) # 1
扩展欧几里得算法是在原有求出最大公约数基础上进行了扩展，根据裴蜀定理：一定存在整数x, y，使ax + by = d成立，扩展在于不但能求出 d = gcd，而且能求出这个特解 x 和 y
计算方法
gcd(a, b) = ax1 + by1
gcd(b, a mod b) = bx2 + (a mod b)y2
...
gcd(?, 0) = ?
ax1 + by1 = bx2 + (a%b) y2
ax1 + by1 = bx2 + (a-(a/b)*b) y2 = ay2 + bx2 -(a/b)*by2
令 a/b = k
ax1 + by1 = bx2 + (a-k*b)y2 = ay2 + b(x2-k*y2) = ay2 + b(x2-a/b*y2)
根据恒等定理得：
x1 = y2, y1 = x2 - [a/b]y2，x1，y1的值基于x2，y2
上面的思想是以递归定义的，递归基为x = 1, y = 0
（即a = gcd(?, 0), b = 0，此a b为x y的系数，gcd = 1*a + 0*b）
求二元一次不定方程252x + 198y = 18的整数解，gcd(252, 198) = 18
252 ÷ 198 = 1 (余 54)
198 ÷ 54 = 3 (余 36)
54 ÷ 36 = 1 (余 18)
36 ÷ 18 = 2 (余 0)
得出gcd(252, 198) = 18
根据递归关系得到以下式子，注意对角线/方向，体现 x1 = y2
18 = [1]*18 + [0]*0
= [0]*36 + [1 - (36/18)*0]*18 简化0*36 + 1*18
= [1]*54 + [0 - (54/36)*1]*36 简化1*54 + (-1)*36
= [-1]*198 + [1 - (198/54)*(-1)]*54 简化(-1)*198 + 4*54
= [4]*252 + [-1 - (252/198)*4] 简化4*252 + (-5)*198
得出特解x = 4, y = -5
注意x = 4为 252 关于模 198 的逆元
def gcdExtended(a, b):
# Base Case
if a == 0:
return b, 0, 1
gcd, x1, y1 = gcdExtended(b % a, a)
# Update x and y using results of recursive call
x = y1 - (b//a) * x1
y = x1
return gcd, x, y
if __name__ == "__main__":
a, b = 252, 198
g, x, y = gcdExtended(a, b)
print(g, x, y) # (18, 4, -5)
模(Mod)运算法则 #
模运算定义： 对于任意实数x, y，可以有
x mod y = x - y[x/y], y ≠ 0。
在一些场合，可以使用符号%表示，它是一个二元运算
x mod y的值都介于 0 和模之间：
0 <= x mod y <= y, y > 0
0 >= x mod y >= y, y < 0
其中y = 0时，为了避免用零做除数，为了完整起见，我们定义 x mod 0 = x
模运算类似基本四则可以进行加减乘等，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = [(a % p) ^ b] % p ^ 表示指数幂
模运算满足结合律、交换律、分配律，具体如下：
((a + b) % p + c) % p = (a + (b + c) % p) % p
((a * b) % p * c) % p = (a * (b * c) % p) % p
(a + b) % p = (b + a) % p
(a * b) % p = (b * a) % p
(a + b) % p = (a % p + b % p) % p
((a + b) % p * c) % p = ((a * c) % p + (b * c) % p ) % p
数论四大定理 #
威尔逊定理、欧拉定理、孙子定理（中国剩余定理）、费马小定理并称数论四大定理
威尔逊定理 #
威尔逊定理给出了判定一个自然数是否为素数的充分必要条件
简述为，若一个数(p - 1)！+ 1能被 p 整除，那么 p 为质数，定义
(p - 1)! ≡ -1 (mod p) 是 p 为素数的充分必要条件
欧拉定理 #
欧拉函数 φ(n) 定义 #
∀ n ∈ N+，φ(n) = ∣A∣，where A = { m ∣ 1 ≤ m < n, (m, n) = 1}
注：∣S∣ 表示集合S元素的个数
给定一个正整数 n，欧拉函数就是求在 [1, n)区间上，与 n 互质的整数的个数，1和任何数都互质
举例来说，设 m = 8，则与 8 互质的正整数集合 A = {1, 3, 5, 7}，此集合共有4个元素，所以 φ(8) = 4。注：φ 读作 fài
欧拉函数性质 #
欧拉函数的定义域与值域有一一对应关系，即已知 m 可以求出唯一的 φ(m)，但是已知 φ(m) 却可能有多个 m 与之对应。如已知 φ (m) = 4，除了8，结果还可以是其他值，如10(A = {1, 3, 7, 9}，尤其是当 φ(m) 的值很大时，有更多的解
怎么计算φ(n)先分以下情况讨论：
- n = 1，则 φ(n) = 1，因为1和任何数都互质，当然包含了自身
- n 是质数，则 φ(n) = n − 1，因为任何一个质数与比自身小的数都只有 1 这个公约数，[1,n) 共有n-1个数，每个数都与n互指
- n = p^k，其中 p 为质数, k ≥ 1，则φ(p^k) = p^k - p^(k-1) = (p − 1) * p^(k − 1)
- n = pq，其中p, q均为质数，则 φ(n) = φ(pq) = φ(p)φ(q)
关于情况3，我们可以简单证明： 由于 p 是质数，所以在 [1, p^k) 中与 p^k 不互质的数是 p 的倍数，即： p, 2p, 3p, ... , p^k - p 一共p^(k - 1) - 1个，所以 φ(p^k) = p^k - 1 - [p^(k - 1) - 1] = p^k - p^(k - 1) = (p − 1) * p^(k − 1)关于情况4，我们可以简单证明： 由于 p, q 是质数，所以与 pq 不互质的数只有两种情况： 1：p的整数倍： p, 2p, 3p, ... ,(q − 1)p 共 q − 1 个； 2：q的整数倍： q, 2q, 3q, ... ,(p − 1)q 共 p − 1 个； 所以在区间 [1, pq)上，与 pq 互质的正整数个数为 φ(pq) = (pq - 1) - (q - 1) - (p - 1) = pq - q - p + 1 = (p - 1)(q - 1)
欧拉函数通式 #
φ(n) = n(1 - 1/p1)(1 - 1/p2)...(1 - 1/pr)
n = p1^k1 p2^k2 ... pr^kr，为 n 的质因数分解
如n = 100我们就可以写成 100 = 2^2 * 5^2，所以 2 和 5 分别是 p1 和 p2
φ(100) = 100 * (1 - 1/2) * (1 - 1/5) = 40
可以使用容斥原理证明，略
欧拉定理 #
a^φ(n) ≡ 1 (mod n)
其中，a 与 n 均为正整数，且两者互质
中国剩余定理（孙子定理） #
中国剩余定理(Chinese Remainder Theorem)是数论中的一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法
一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理
明朝数学家程大位在《算法统宗》中将解法编成易于上口的《孙子歌诀》：
三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知
形式描述 #
给出了以下的一元线性同余方程组 x ≡ ai (mod mi) (S):
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ an (mod mn)
假设整数 m1, m2, … , mn 其中任两数互质，则对任意的整数：a1, a2, … , an，方程组(S)有解，并且通解可以用如下方式构造得到：
- 设 M = m1 * m2 * … * mn 是整数 m1, m2, … , mn 的乘积，并设 Mi = M/mi，即 Mi 是除了 mi 以外的 n − 1 个整数的乘积
- 设 ti 为 Mi 模 mi 的数论倒数：tiMi ≡ 1 (mod mi)
- 方程组 (S) 的通解形式为：x = a1t1M1 + a2t2M2 + … + antnMn + kM
- 在模 M 的意义下，方程组 (S) 只有一个解：x = a1t1M1 + a2t2M2 + … + antnMn
使用中国剩余定理来求解上面的“物不知数”问题。这里的线性同余方程组 (S) 是：
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
三个模数 m1 = 3, m2 = 5, m3 = 7 的乘积是 M = 105，对应的 M1 = 35, M2 = 21, M3 = 15，而可以计算出相应的数论倒数：t1 = 2, t2 = 1, t3 = 1
70 = 2 * 35 ≡ 1 (mod 3)
≡ 0 (mod 5)
≡ 0 (mod 7)
≡ 0 (mod 3)
21 = 1 * 21 ≡ 1 (mod 5)
≡ 0 (mod 7)
≡ 0 (mod 3)
≡ 0 (mod 5)
15 = 1 * 15 ≡ 1 (mod 7)
所以《孙子歌诀》中的 70、21 和 15 其实是这个“物不知数”问题的基础解
而将原方程组中的余数相应地乘到这三个基础解上（aitiMi），再加起来，其和就是原方程组的解：
≡ 2 * 1 + 3 * 0 + 2 * 0 ≡ 2 (mod 3)
2 * 70 + 3 * 21 + 2 * 15 ≡ 2 * 0 + 3 * 1 + 2 * 0 ≡ 3 (mod 5)
≡ 2 * 0 + 3 * 0 + 2 * 1 ≡ 2 (mod 7)
这个和是 233，实际上原方程组的通解公式为：
x = 233 + k * 105
《孙子算经》中实际上给出了最小正整数解，也就是 k = -2 时的解：x = 23
从假设可知，gcd(mi, mj) = 1, i != j, 所以 gcd(mi, Mi) = 1
gcd(mi, Mi) = 1 说明存在整数ti 使得 tiMi ≡ 1 (mod mi)，这样的 ti 叫做 Mi 模 mi 的数论倒数
观察乘积
aitiMi ≡ ai * 1 ≡ ai (mod mi)
ajtjMj ≡ 0 (mod mi), i != j
所以 x = a1t1M1 + a2t2M2 + … + antnMn 满足
x ≡ ai + 0 ≡ ai (mod mi)
即 x 就是方程组 (S) 的一个解
另外，假设 x1 和 x2 都是方程组 (S) 的解，那么：
x1 - x2 ≡ 0 (mod mi)，而 m1, m2, …, mn 两两互质，这说明 M = m1 * m2 * … * mn 整除 x1 - x2，所以方程组 (S) 的任何两个解之间必然相差 M 的整数倍，所有形式为：
x = a1t1M1 + a2t2M2 + ... + antnMn + kM
from libnum import invmod, gcd
# Define the moduli and residues
moduli = [3, 5, 7]
residues = [2, 3, 2]
# Compute the product of the moduli
M = 1
for m in moduli:
M *= m
# Compute the solution using the CRT
solution = 0
for i in range(len(moduli)):
mi = M // moduli[i]
mi_inv = invmod(mi, moduli[i])
solution += residues[i] * mi * mi_inv
# Reduce the solution modulo M
solution %= M
print(solution)
费马小定理 #
费马小定理给出的是关于素数判定的必要非充分条件。假如 a 是一个整数，p 是一个质数，那么 a^p - a 是 p 的倍数，可以表示为
a^p ≡ a (mod p)
如果 a 不是 p 的倍数即 gcd(a, p) = 1，这个定理也可以写成更加常用的一种形式
a^(p - 1) ≡ 1 (mod p)
费马小定理是欧拉定理的一个特殊情况，如果 gcd(a, n) = 1，那么
a^φ(n) ≡ 1 (mod n)
费马小定理的逆叙述不成立，即假如 a^p - a 是 p 的倍数，p 不一定是一个质数。2^341 - 2 是 341 的倍数，但341 = 11 x 31，不是质数。
满足费马小定理的合数被称为费马伪素数，第一个伪素数 341 是萨鲁斯(Sarrus)在1819年发现的，有人已经证明了伪素数的个数是无穷的
RSA简介及证明 #
RSA(Rivest–Shamir–Adleman)是一种公钥密码系统，被广泛应用于安全数据传输。RSA名称来自其发明者的姓名首字母缩写：Ron Rivest，Adi Shamir和Leonard Adleman。该系统通过使用两个大质数生成公钥和私钥来工作。公钥可以自由分发，而私钥必须保密
当某人想要向公钥所有者发送消息时，他们使用公钥加密消息。只有私钥的所有者才能解密消息，确保通信保持机密性
RSA被认为是非常安全的加密方法，因为它依赖于目前认为分解两个大质数乘积的因子在常规时间是不可行的事实
算法步骤 #
RSA加密算法主要步骤如下：
- 选择2个大质数 p 和 q，计算出模数 N = p * q，N 作为公私密钥共同的模，N可以公开，p 和 q 不公开私密保留
- 计算欧拉函数 φ(N) = (p - 1) * (q - 1)，φ(N) 不公开私密保留
- 选择一个e(1 < e < φ(N))，且 e 和 φ(N) 互质，e 可以公开
- 取 e 的模逆元为 d，ed ≡ 1 (mod φ(n)) ，d 不公开私密保留
公钥（可以公开）：e和N
私钥（不可以公开）：d
加密：c = m^e (mod N)，得到的 c 即为密文
解密：m = c^d (mod N)，得到的 m 即为明文
算法证明 #
RSA算法可以抽象为两个映射：加密映射 E(x) 和 解密映射 D(x)，满足
D(E(x)) = x
解密性证明如下：
D(E(x)) ≡ (E(x))^d (mod N)
≡ x^ed
≡ x^(φ(N)k)x (根据ed的取值关系，ed = kφ(N) + 1)
≡ (1^k)x (根据欧拉定理，a^φ(N) ≡ 1 (mod N))
≡ x
因为 p 和 q都是大素数，x 和 n = pq 不互质的概率很低，所以直接忽略了不互质的情况
Q&A #
解密性证明方法主要用到了什么定理
e 的取值
算法是对数字进行加密，实际使用场景主要是文本，数字和文本怎么对应的
p、q 为 大质数，构造这2个大质数复杂吗
RSA算法中哪些部分是可以公开的，哪些部分是不可以公开的
RSA 算法的安全性体现在哪
常说的1024/2048长度的RSA密钥，这个长度指的是什么的长度