同余
定义
$a, b \in Z, m \in Z^+$，若有 $m | a - b$，则称 $a, b$ 模 $m$ 同余，记作 $a \equiv b \quad (mod \; m)$
判断
$a \equiv b \quad (mod \; m) \iff \exists q \in Z, a = b + q \cdot m$
模同余是一种等价关系，即有自反性、对称性、和传递性
$a \equiv b \quad (mod \; m) \iff$ $a, b$ 被 $m$ 除的余数相同
同余做加法和乘法之后仍然同余
性质
- 设 $d \cdot a \equiv d \cdot b \quad (mod \; m)$，若 $(d,m) = 1$，则 $a \equiv b \quad (mod \; m)$
- $m \in Z^+$，设 $a \equiv b \quad (mod \; m)$，$d > 0$，则 $a \cdot d \equiv b \cdot d \quad (mod \; d \cdot m)$
- 设 $a \equiv b \quad (mod \; m)$，若 $d | (a, b, m)$，则 $\frac{a}{d} \equiv \frac{b}{d} \quad (mod \; \frac{m}{d})$
- 设 $a \equiv b \quad (mod \; m)$，若 $d | m$，则 $a \equiv b \quad (mod \; d)$
- 设 $a \equiv b \quad (mod \; m_i)$，则 $a \equiv b \quad mod([m_1, … m_k])$
- 设 $a \equiv b \quad (mod \; m)$，则 $(a, m) = (b, m)$
剩余类和完全剩余系
剩余类与剩余
$m \in Z^+$，$\forall a \in Z$，令 $C_a = \lbrace c | c \in Z, c \equiv a (mod \; m) \rbrace$，则 $C_a$ 称为模 $m$ 的 $a$ 的剩余类，一个剩余类中的任一数称为该类的剩余或代表元，若 $r_0, r_1, \dots, r_n \in Z$ 且任意两个数都不在同一个剩余类中，则称其为模 $m$ 的一个完全剩余系
通常将模 $m$ 的所有剩余类记作 $Z/mZ$，模 $m$ 的所有简化剩余类记作 $(Z/mZ)^*$
完全剩余系
$r_0, r_1, \dots ,r_n$ 为模 $m$ 的一个完全剩余系 $\iff$ 模 $m$ 两两不同余
一些特殊的完全剩余系：最小非负完全剩余系、最小正完全剩余系、最大非正完全剩余系、最大负完全剩余系、绝对值最小完全剩余系
性质
- $m \in Z^+, (a, m) = 1$，$\forall b \in Z$，若 $k$ 遍历模 $m$ 的一个完全剩余系，则 $a \cdot k + b$ 也遍历模 $m$ 的一个完全剩余系
- $(m_1, m_2) = 1$，若 $k_1, k_2$ 分别遍历模 $m_1, m_2$ 的完全剩余系，则 $m_2 \cdot k_1 + m_1 \cdot k_2$ 遍历模 $m_1 \cdot m_2$ 的完全剩余系
简化剩余系与欧拉函数
欧拉函数
欧拉函数 $\psi(m)$，指 $0, 1, \dots, m-1$ 中与 $m$ 互素的整数个数
简化剩余类
若剩余类 $C_a$ 中的一个剩余 $a$ 满足 $(a, m)=1$，则称该类为简化剩余类，简化剩余类中的剩余称为简化剩余，从每个简化剩余类中任取一个整数组成的集合称为简化剩余系
注：由定义可知 $|(Z/mZ)^*|=\psi(m)$
同剩余系，简化剩余也可分为一些特殊的简化剩余系
性质
$(a, m) = 1$，如果 $x$ 遍历模 $m$ 的一个简化剩余系，则 $a \cdot x$ 也遍历模 $m$ 的一个简化剩余系
$(a, m) = 1$，存在 $a^{-1} \in Z$，且 $1 \le a^{-1} < m$，使得 $a \cdot a^{-1} \equiv 1 \quad (mod \; m)$
- 由 Bezout 等式立即得到结论成立
$(m_1, m_2) = 1$，如果 $k_1, k_2$ 分别遍历模 $m_1,m_2$ 的简化剩余系，则 $m_2 \cdot k_1 + m_1 \cdot k_2$ 遍历模 $m_1 \cdot m_2$ 的简化剩余系
$(m, n) = 1$，则 $\psi(mn)=\psi(m) \cdot \psi(n)$
- 考虑 $xm + yn$ 由上一条定理立证
设 $n = \Pi p_i^{\alpha_i}$，则 $\psi(n) = n \cdot \Pi(1-\frac{1}{p_i})$
$$
\sum_{d|m} \psi(d) = m
$$- 该定理将用于原根的构造
- $1, \dots , m$ 中的每一个整数按照与 $m$ 的最大公因数进行分类
欧拉定理和费马小定理
欧拉定理
若 $(a, m) = 1$，则有 $a^{\psi(m)} \equiv 1 \quad (mod \; m)$
RSA
设 $p, q$ 是两个不同的奇素数，$n = p \cdot q$，$a \in Z$ 且 $(a, n) = 1$，如果 $e$ 满足：
$$
1 < e < \psi(n), \quad (e, \psi(n)) = 1
$$
那么存在整数 $d$，使得 $e \cdot d \equiv 1 \quad (mod \; \psi(n))$，而且，对于整数
$$
a^e \equiv c \quad (mod \; n), \quad 1 < c < n
$$
有
$$
c^d \equiv a \quad (mod \; n)
$$
上述公钥为 $n,e$，私钥为 $p,q,d$，明文为 $a$，密文为 $c$
class GeneratePrime:
"""generate prime by miller robin algorithm"""
def __init__(self, judge_numbers: Iterable[int] = None):
# judge_numbers are numbers to test in miller robin algorithm
if not judge_numbers:
self.judge_numbers = {2, 3, 5, 7, 11, 13}
else:
self.judge_numbers = judge_numbers
def gen_nbit_prime(self, n, threshold=1000):
"""generate nbit length prime"""
# support n <= 1024
assert n <= 1024
lower_bound = 2 ** n
upper_bound = 2 ** (n+1)
num = 0
while num < threshold:
# keep odd
p = randint(lower_bound, upper_bound) | 1
if self.is_prime(p):
return p
num += 1
print("fail to find prime")
def is_prime(self, p) -> bool:
if p & 1 == 0:
return False
if p in {2, 3, 5, 7, 11}:
return True
for judge_num in self.judge_numbers:
if not self.miller_robin_test(p, judge_num):
return False
return True
@staticmethod
def miller_robin_test(p: int, a: int) -> bool:
"""miller robin algorithm to test if p is prime
More details can be found in wikipedia "https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test"
"""
# fermat theorem: a^p = a (mod p) if p is prime
# here we use builtin function for efficiency
if pow(a, p, p) != a:
return False
n = p - 1
# if x^2 = 1 (mod p) then, x = 1/p-1 (mod p)
while n & 1:
remainder = pow(a, n, p)
if remainder not in (1, p-1):
return False
n //= 2
return True
class RSA:
"""RSA example
Description:
this implement 2.4.5 in chapter2
"""
def __init__(self, nbit, e=65537):
prime_gen = GeneratePrime()
p = prime_gen.gen_nbit_prime(nbit)
q = prime_gen.gen_nbit_prime(nbit)
n = p * q
phi_n = (p-1) * (q-1)
d, *_ = self.extended_euclidean(e, phi_n)
d %= phi_n
self.private_key = {
"p": p,
"q": q,
"phi_n": phi_n,
"d": d
}
self.public_key = {
"n": n,
"e": e
}
def encrypt(self, a):
"""encrypt plaintext a with public key e"""
e = self.public_key.get("e")
n = self.public_key.get("n")
return pow(a, e, n)
def decrypt(self, c):
d = self.private_key.get("d")
n = self.public_key.get("n")
return pow(c, d, n)
@staticmethod
def extended_euclidean(a, b):
"""use extended euclidean algorithm to calculate s, t, k, s.t. sa + tb = k = (a, b)"""
quotients = []
q, r1 = divmod(a, b)
r2 = b
quotients.append(q)
while r1 > 0:
q, r = divmod(r2, r1)
r2 = r1
r1 = r
quotients.append(q)
s: list = [1, 0]
t: list = [0, 1]
for i in range(len(quotients) - 1):
s.append(quotients[i] * -s[i+1] + s[i])
t.append(quotients[i] * -t[i+1] + t[i])
return s[-1], t[-1], r2费马小定理
$p$ 是一个素数，$\forall a,t,k \in Z$，有 $a^{t + k \cdot (p-1)} \equiv a^t \quad (mod \; p)$
Wilson 定理
$p$ 是一个素数，则有
$$
(p-1)! \equiv -1 \quad (mod \; p)
$$
模重复平方计算法
计算 $b^n \; (mod \; m)$ 的步骤：
- 将 $n$ 表示成二进制 $n=(n_{k-1}n_{k-2} \cdots n_0)_2$
- 在模 $m$ 下计算 $b_0=b,b_1=b_0^2, \dots, b_{k-1}=b_{k-2}^2$
- 在模 $m$ 下计算 $a_0 = b_0^{n_0}, a_t=a_{t-1} \cdot b_t^{n_t}, \; \; t \in [1, k-1]$
- $a_{k-1}$ 即为结果
例子：计算 $312^{13} \; (mod \; 667)$
$$
\begin{align}& 13 = (1101)_2 \\& b_0 = b = 312； b_1 = b_0^2 = 629； b_2 = b_1^2 = 110；b_3 = b_2^2 = 94 \\& a_0 = b_0^{n_0} = 312；a_1 = a_0 \cdot b_1^{n_1} = 312；a_2 = a_1 \cdot b_2^{n_2} = 303；a_3 = a_2 \cdot b_3^{n_3} = 468 \end{align}
$$
故结果为 $468$
def exponentiation_by_squaring(b: int, e: int, m: int) -> int:
"""calculate non-negative integer k that satisfies b^e = k (mod m)
Description:
This function implement exponentiation mod in chapter2
Args:
b: the base integer
e: the exponent integer
m: the modulus
Returns:
the non-negative integer k that satisfies b^e = k (mod m) and 0 <= k < m
"""
def integer_to_binary(s) -> List[int]:
"""change non-negative integer s to binary"""
bin_array = []
while s > 0:
bin_array.append(s % 2)
s //= 2
# the binary is expressed as a_0 + a_1*2 + ... + a_n*2^n
return bin_array
bin_list = integer_to_binary(e)
# previously calculate b, b^2, b^4, ... in the case of module m
previous_b_list: list = [b % m]
for i in range(len(bin_list) - 1):
previous_b_list.append(previous_b_list[i] ** 2 % m)
# calculate k
k = b ** bin_list[0] % m
for i in range(1, len(bin_list)):
if bin_list[i] == 1:
k = k * previous_b_list[i] % m
return k
