数论基础（五）数论算法¶
章节概述¶
本章将介绍数论中的重要算法，包括质因数分解、勒让德符号的计算以及离散对数问题的求解。这些算法在密码学、计算机科学和算法竞赛中都有广泛应用。
学习目标¶
- 掌握质因数分解的各种算法
- 理解勒让德符号的概念和计算方法
- 了解离散对数问题
- 掌握婴儿-巨步算法求解离散对数
- 了解 Pollard's Rho 算法（大数分解）
- 掌握数论算法的优化技巧
（一）质因数分解¶
质因数分解的定义¶
将一个正整数表示为质数的乘积：
其中 p₁ < p₂ < ... < pₖ 是质数，aᵢ 是正整数。
算法一：试除法¶
原理：依次尝试用质数去除 n
def prime_factorization_trial(n):
"""
质因数分解（试除法）
参数:
n: 正整数
返回:
dict: 质因数及其指数的字典
时间复杂度: O(√n)
示例:
>>> prime_factorization_trial(12)
{2: 2, 3: 1}
>>> prime_factorization_trial(100)
{2: 2, 5: 2}
>>> prime_factorization_trial(17)
{17: 1}
"""
factors = {}
# 处理 2 的因子
count = 0
while n % 2 == 0:
count += 1
n = n // 2
if count > 0:
factors[2] = count
# 处理奇数因子
for i in range(3, int(n**0.5) + 1, 2):
count = 0
while n % i == 0:
count += 1
n = n // i
if count > 0:
factors[i] = count
# 如果剩下的 n 是质数
if n > 1:
factors[n] = 1
return factors
算法二：优化试除法¶
优化点： - 先筛出 √n 以内的质数 - 只用质数试除
def prime_factorization_optimized(n):
"""
质因数分解（优化试除法）
参数:
n: 正整数
返回:
dict: 质因数及其指数的字典
时间复杂度: O(√n / log n)
"""
factors = {}
# 筛出 √n 以内的质数
limit = int(n**0.5) + 1
primes = sieve_of_eratosthenes(limit)
# 用质数试除
for p in primes:
if p * p > n:
break
count = 0
while n % p == 0:
count += 1
n = n // p
if count > 0:
factors[p] = count
# 如果剩下的 n 是质数
if n > 1:
factors[n] = 1
return factors
算法三：Pollard's Rho 算法（大数分解）¶
应用场景：分解非常大的数（试除法太慢）
原理：利用随机化和费马小定理
import random
def pollard_rho(n):
"""
Pollard's Rho 算法：分解大数
参数:
n: 待分解的合数
返回:
int: n 的一个非平凡因子
时间复杂度: O(n^(1/4))
"""
if n % 2 == 0:
return 2
if n % 3 == 0:
return 3
while True:
c = random.randint(2, n - 1)
f = lambda x: (pow(x, 2, n) + c) % n
x, y, d = 2, 2, 1
while d == 1:
x = f(x)
y = f(f(y))
d = gcd(abs(x - y), n)
if d != n:
return d
def prime_factorization_pollard(n):
"""
使用 Pollard's Rho 算法进行质因数分解
参数:
n: 正整数
返回:
dict: 质因数及其指数的字典
时间复杂度: 优于试除法，特别是对大数
"""
factors = {}
def factorize(n):
if n == 1:
return
if is_prime(n):
factors[n] = factors.get(n, 0) + 1
return
d = pollard_rho(n)
factorize(d)
factorize(n // d)
factorize(n)
return factors
质因数分解的应用¶
应用1：计算约数个数¶
def count_divisors_from_factors(factors):
"""
根据质因数分解计算约数个数
参数:
factors: 质因数分解结果
返回:
int: 约数的个数
"""
count = 1
for exp in factors.values():
count *= (exp + 1)
return count
应用2：计算约数之和¶
def sum_divisors_from_factors(factors):
"""
根据质因数分解计算所有约数的和
参数:
factors: 质因数分解结果
返回:
int: 所有约数的和
"""
total = 1
for p, exp in factors.items():
total *= (p**(exp + 1) - 1) // (p - 1)
return total
（二）勒让德符号¶
勒让德符号的定义¶
对于奇质数 p 和整数 a，勒让德符号 (a/p) 定义为： - (a/p) = 0，如果 a ≡ 0 (mod p) - (a/p) = 1，如果 a 是模 p 的二次剩余 - (a/p) = -1，如果 a 是模 p 的二次非剩余
欧拉判别法¶
定理：对于奇质数 p 和不被 p 整除的整数 a：
def legendre_symbol_euler(a, p):
"""
使用欧拉判别法计算勒让德符号 (a/p)
参数:
a: 整数
p: 奇质数
返回:
int: 0, 1, 或 -1
时间复杂度: O(log p)
示例:
>>> legendre_symbol_euler(2, 7)
1
>>> legendre_symbol_euler(3, 7)
-1
>>> legendre_symbol_euler(7, 7)
0
"""
a = a % p
if a == 0:
return 0
result = mod_pow(a, (p - 1) // 2, p)
if result == p - 1:
return -1
return result
勒让德符号的性质¶
性质1：周期性¶
性质2：乘法性¶
性质3：二次互反律¶
如果 p 和 q 都是奇质数，则：
性质4：特殊值¶
勒让德符号的应用¶
应用1：判断二次剩余¶
def is_quadratic_residue(a, p):
"""
判断 a 是否是模 p 的二次剩余
参数:
a: 整数
p: 奇质数
返回:
bool: 如果是二次剩余返回 True
"""
return legendre_symbol_euler(a, p) == 1
应用2：求解二次同余方程¶
参见第三章的 Tonelli-Shanks 算法。
（三）离散对数¶
离散对数问题的定义¶
给定质数 p、原根 g 和整数 y，求 x 使得：
称 x 为 y 以 g 为底的离散对数，记作 x = log_g(y) mod p。
离散对数问题的困难性¶
离散对数问题被认为是计算上困难的，这是许多密码学算法（如 Diffie-Hellman 密钥交换、ElGamal 加密）安全性的基础。
婴儿-巨步算法（Baby-Step Giant-Step）¶
原理：将指数 x 分解为 x = im + j，其中 m = ⌈√p⌉
步骤： 1. 选择 m = ⌈√p⌉ 2. 婴儿步：计算并存储 g^j (mod p)，j = 0, 1, ..., m-1 3. 巨步：计算 y × (g^(-m))^i (mod p)，i = 0, 1, ..., m-1 4. 如果找到匹配，则 x = im + j
import math
def baby_step_giant_step(g, y, p):
"""
婴儿-巨步算法求解离散对数
求 x 使得 g^x ≡ y (mod p)
参数:
g: 原根
y: 整数
p: 质数
返回:
int: 离散对数 x
如果无解返回 None
时间复杂度: O(√p)
空间复杂度: O(√p)
示例:
# 2^x ≡ 3 (mod 13)
>>> baby_step_giant_step(2, 3, 13)
4 # 因为 2^4 = 16 ≡ 3 (mod 13)
"""
m = int(math.ceil(math.sqrt(p - 1)))
# 婴儿步：计算 g^j (mod p)，j ∈ [0, m-1]
table = {}
current = 1
for j in range(m):
if current not in table:
table[current] = j
current = (current * g) % p
# 巨步：计算 y * g^(-im) (mod p)，i ∈ [0, m-1]
inv_g_m = mod_inverse(mod_pow(g, m, p), p)
current = y
for i in range(m):
if current in table:
x = i * m + table[current]
if mod_pow(g, x, p) == y:
return x
current = (current * inv_g_m) % p
return None # 无解
Pohlig-Hellman 算法¶
适用场景：当 p-1 的质因数分解已知时
原理：利用中国剩余定理将离散对数问题分解为多个小规模的子问题
def pohlig_hellman(g, y, p):
"""
Pohlig-Hellman 算法求解离散对数
参数:
g: 原根
y: 整数
p: 质数
返回:
int: 离散对数 x
时间复杂度: O(Σ(eᵢ × log pᵢ))，其中 p-1 = Π(pᵢ^eᵢ)
"""
# 分解 p-1
factors = prime_factorization(p - 1)
# 对每个质因数求解
equations = []
for q, e in factors.items():
x_mod_qe = 0
g_power = mod_pow(g, (p - 1) // q, p)
y_power = y
for i in range(e):
# 求解 g^((p-1)/q) * x_i ≡ y^(something) (mod p)
temp = mod_pow(y_power, (p - 1) // (q ** (i + 1)), p)
x_i = baby_step_giant_step(g_power, temp, p)
x_mod_qe += x_i * (q ** i)
y_power = (y_power * mod_inverse(mod_pow(g, x_i * (q ** i), p), p)) % p
equations.append((x_mod_qe % (q ** e), q ** e))
# 使用中国剩余定理合并
solution, _ = crt(equations)
return solution
（四）其他重要算法¶
算法一：米勒-拉宾素性测试¶
应用场景：快速判断大数是否为质数（概率性算法）
def miller_rabin(n, k=5):
"""
米勒-拉宾素性测试
参数:
n: 待测试的数
k: 测试次数（影响准确性）
返回:
bool: 如果 n 可能是质数返回 True
如果 n 肯定是合数返回 False
时间复杂度: O(k × log³ n)
准确性：错误概率 ≤ 4^(-k)
"""
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0:
return False
# 将 n-1 分解为 d × 2^s
d = n - 1
s = 0
while d % 2 == 0:
d //= 2
s += 1
# 进行 k 次测试
for _ in range(k):
a = random.randint(2, n - 2)
x = mod_pow(a, d, n)
if x == 1 or x == n - 1:
continue
for __ in range(s - 1):
x = mod_pow(x, 2, n)
if x == n - 1:
break
else:
return False # 肯定是合数
return True # 可能是质数
算法二：扩展欧几里得算法（回顾）¶
已经在第二章详细介绍，这里不再赘述。
（五）实战应用¶
应用1：RSA 密钥生成¶
def generate_rsa_keypair(p, q):
"""
生成 RSA 密钥对
参数:
p, q: 两个大质数
返回:
tuple: (公钥, 私钥)
"""
n = p * q
phi = (p - 1) * (q - 1)
# 选择 e
e = 65537 # 常用值
while gcd(e, phi) != 1:
e = random.randrange(2, phi)
# 计算 d
d = mod_inverse(e, phi)
# 公钥 (e, n)，私钥 (d, n)
return ((e, n), (d, n))
应用2：Diffie-Hellman 密钥交换¶
def diffie_hellman_key_exchange(p, g):
"""
Diffie-Hellman 密钥交换协议
参数:
p: 大质数
g: 原根
返回:
tuple: (Alice的密钥, Bob的密钥, 共享密钥)
"""
# Alice 选择私钥
a = random.randint(2, p - 2)
A = mod_pow(g, a, p) # Alice 的公钥
# Bob 选择私钥
b = random.randint(2, p - 2)
B = mod_pow(g, b, p) # Bob 的公钥
# 计算共享密钥
alice_shared = mod_pow(B, a, p)
bob_shared = mod_pow(A, b, p)
# 验证密钥相同
assert alice_shared == bob_shared
return (a, b, alice_shared)
实战练习¶
练习1：分解大数¶
任务：使用 Pollard's Rho 算法分解一个大数
def exercise_1():
"""
分解大数 1234567890123456789012345678901234567890
"""
n = 1234567890123456789012345678901234567890
factors = prime_factorization_pollard(n)
print(f"{n} 的质因数分解：")
for p, exp in sorted(factors.items()):
print(f" {p}^{exp}")
练习2：求解离散对数¶
任务：求解 2^x ≡ 5 (mod 101)
def exercise_2():
"""
求解 2^x ≡ 5 (mod 101)
"""
g, y, p = 2, 5, 101
x = baby_step_giant_step(g, y, p)
print(f"离散对数：{x}")
print(f"验证：{g}^{x} mod {p} = {mod_pow(g, x, p)}")
练习3：判断质数¶
任务：使用米勒-拉宾测试判断大数是否为质数
def exercise_3():
"""
判断大数是否为质数
"""
numbers = [
2**61 - 1, # 梅森质数
2**67 - 1, # 非质数
10**100 + 267, # 未知
]
for n in numbers:
is_prime_prob = miller_rabin(n, k=10)
print(f"{n} 可能是质数：{is_prime_prob}")
章节小结¶
本章介绍了重要的数论算法：
- 质因数分解：掌握试除法、优化试除法和 Pollard's Rho 算法
- 勒让德符号：理解定义、性质和计算方法
- 离散对数：理解离散对数问题，掌握婴儿-巨步算法
- 米勒-拉宾测试：掌握概率性素性测试方法
- 密码学应用：了解 RSA 和 Diffie-Hellman 的数学基础
这些算法是现代密码学和计算机安全的基础。
下一步¶
继续学习第六章：应用实例，了解数论在实际问题中的应用。
重点提醒： - Pollard's Rho 算法适合分解大数 - 婴儿-巨步算法的时间复杂度是 O(√p) - 米勒-拉宾测试是概率性算法，需要进行多次测试 - 离散对数问题是密码学的基础