Part 7.4：数论算法——从质数到密码学的基石
引言：代码世界里的数学幽灵
当我们在讨论算法时，通常会想到排序、搜索、图论等直观的应用。然而，在这些具体问题的背后，存在一个更古老、更抽象的数学分支，它像一个幽灵一样，深刻地影响着计算机科学的每一个角落——这就是**数论 (Number Theory)**。
你可能会问，研究整数性质的数论，与编程有什么关系？关系重大！
- 你每次访问
https://网站，背后都有基于数论的 RSA 或 ECC 加密算法在保护你的数据安全。 - 你使用的哈希表，其哈希函数的设计往往需要数论知识来减少冲突。
- 分布式系统中的唯一 ID 生成、游戏中的随机数，甚至高性能计算中的某些优化，都离不开数论的智慧。
为什么数论算法如此重要？
- 面试价值：在顶级公司的面试中，数论问题是区分候选人数学思维和底层能力的重要工具。涉及质数、最大公约数、模运算、快速幂等问题屡见不鲜。
- 学术与工程价值：
- 密码学基石：没有数论，就没有现代公钥密码体系，整个互联网的安全大厦将不复存在。
- 算法竞赛：数论是 ACM/ICPC 等算法竞赛中的一个独立且重要的分支。
- 底层优化：理解数论可以帮助你设计出更高效、更巧妙的算法来解决特定问题。
本文将为你揭开数论在算法世界中的面纱，从最基础、最核心的三个问题入手：如何高效判断和筛选质数？如何快速计算两个数的最大公约数？以及如何处理天文数字级别的幂运算？
背景知识：模运算的钟表世界
在深入数论算法之前，我们必须掌握一个核心概念：**模运算 (Modular Arithmetic)**。
直觉：钟表算术
模运算就像一个钟表。假设现在是 10 点，4 个小时后是几点？10 + 4 = 14，但在 12 小时的钟表上，14 点就是 2 点。这个过程就是 14 mod 12 = 2。
严谨原理：同余关系
a ≡ b (mod m)，读作 “a 同余于 b 模 m”，意味着 a 和 b 除以 m 的余数相同。
核心性质：模运算的美妙之处在于，加、减、乘运算都可以在模的世界里“封闭”进行，这对于防止计算结果溢出至关重要。
(a + b) mod m = ((a mod m) + (b mod m)) mod m(a - b) mod m = ((a mod m) - (b mod m) + m) mod m(加上 m 是为了防止结果为负)(a * b) mod m = ((a mod m) * (b mod m)) mod m
Part A：质数 (Prime Number) - 构建数字世界的原子
质数是只能被 1 和自身整除的正整数。它们是数论的基石，就像化学中的元素一样。
1. 质数判定：试除法
原理：一个数 n 如果是合数，那么它必然有一个小于或等于 √n 的质因子。
步骤：要判断 n 是否为质数，只需检查从 2 到 √n 的所有整数是否能整除 n。
def is_prime(n):
if n <= 1: return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True时间复杂度：O(√n)。
2. 质数筛选：埃拉托斯特尼筛法 (Sieve of Eratosthenes)
场景：如果需要找出从 2 到 n 之间的所有质数，对每个数都进行一次试除法太慢了。我们需要一种更高效的“筛选”方法。
直觉：想象一个数字列表。我们从第一个质数 2 开始，把所有 2 的倍数（4, 6, 8…）都划掉。然后找到下一个没被划掉的数 3（它一定是质数），再把所有 3 的倍数（6, 9, 12…）划掉。不断重复这个过程。
步骤分解：
- 创建一个从 2 到
n的布尔数组is_prime，初始值全为True。 - 从
p = 2开始遍历。 - 如果
is_prime[p]为True，则p是一个质数。 - 将
p的所有倍数（2p,3p,4p… 直到n）在is_prime数组中标记为False。 - 继续寻找下一个
p，重复 3-4 步，直到p² > n。
Python 实现：
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, int(n**0.5) + 1):
if is_prime[p]:
for multiple in range(p*p, n + 1, p):
is_prime[multiple] = False
primes = [i for i, is_p in enumerate(is_prime) if is_p]
return primes时间复杂度：O(n log log n)，非常接近线性。
Part B：最大公约数 (GCD) - 欧几里得算法的永恒之美
最大公约数 (Greatest Common Divisor) 是指能同时整除两个或多个整数的最大正整数。
欧几里得算法 (Euclidean Algorithm)
这是人类历史上最古老的算法之一，至今仍在广泛使用，其优雅和高效令人惊叹。
核心原理：gcd(a, b) = gcd(b, a mod b)
直觉：两个数的最大公约数，也一定是它们中较大数与较小数之差的最大公约数。通过不断用余数代替较大数，可以迅速缩小问题规模。
动画式案例：计算 gcd(48, 18)
gcd(48, 18)->a=48, b=18。48 mod 18 = 12。问题转化为gcd(18, 12)。gcd(18, 12)->a=18, b=12。18 mod 12 = 6。问题转化为gcd(12, 6)。gcd(12, 6)->a=12, b=6。12 mod 6 = 0。问题转化为gcd(6, 0)。- 当
b=0时，a就是最大公约数。所以gcd(48, 18) = 6。
Python 实现：
def gcd(a, b):
while b:
a, b = b, a % b
return a时间复杂度：O(log(min(a, b)))。每次迭代，数字规模至少减半，因此复杂度是对数级的。
Part C：模幂运算 - 快速幂算法
场景：在密码学和组合数学中，我们经常需要计算 (a^b) mod m。如果 a 和 b 都很大，直接计算 a^b 会导致数据溢出，而且非常慢。
快速幂算法 (Exponentiation by Squaring)
核心思想：利用指数的二进制表示来加速计算。
直觉：任何一个数 b 都可以写成 2 的幂次之和。例如 13 = 8 + 4 + 1 = 2³ + 2² + 2⁰。
所以 a¹³ = a⁸ * a⁴ * a¹。
我们可以通过反复平方 a 来得到 a¹, a², a⁴, a⁸… 然后只把 b 的二进制表示中为 1 的那些项乘起来。
动画式案例：计算 3¹³ mod 7
b = 13的二进制是1101。3¹³ = 3⁸ * 3⁴ * 3¹
| b (二进制) | 操作 | base | result |
|---|---|---|---|
...1101 | b 为奇数, result *= base | 3 | 3 |
...110 | b >>= 1, base *= base | 9 ≡ 2 | 3 |
...11 | b 为奇数, result *= base | 2 | 6 |
...1 | b >>= 1, base *= base | 4 | 6 |
... | b 为奇数, result *= base | 4 | 24 ≡ 3 |
最终结果是 3。
Python 实现：
def fast_power(base, power, mod):
result = 1
base %= mod
while power > 0:
# 如果 power 是奇数，需要乘上当前的 base
if power % 2 == 1:
result = (result * base) % mod
# base 自我平方
base = (base * base) % mod
# power 整除 2
power //= 2
return result时间复杂度：O(log b)。循环次数取决于 b 的二进制位数。
总结
数论算法是计算机科学的“内功心法”，它虽然抽象，但应用极其广泛。掌握基础的数论算法，能让你在解决问题时拥有更广阔的思路和更深刻的洞察力。
本文核心要点
✅ 质数：
- 试除法：O(√n) 判定单个质数。
- 埃氏筛：O(n log log n) 筛选出一定范围内的所有质数。
✅ 最大公约数：
- 欧几里得算法：O(log(min(a, b))) 的高效解法，基于 gcd(a, b) = gcd(b, a mod b)。
✅ 模幂运算：
- 快速幂算法：O(log b) 计算 (a^b) mod m，避免溢出和超时。
扩展与进阶
- 扩展欧几里得算法：求解
ax + by = gcd(a, b)的整数解，用于计算模逆元。 - 费马小定理与欧拉定理：在密码学中有重要应用，是 RSA 算法的理论基础。
- 中国剩余定理：解决一组同余方程。
- Miller-Rabin 素性检验：一种高效的随机化算法，用于检验大数是否为质数。
在下一篇文章中，我们将探讨一个在信号处理和多项式计算中至关重要的分治算法——**快速傅里叶变换 (FFT)**，看看它是如何将某些计算的复杂度从 O(n²) 奇迹般地降到 O(n log n) 的。