素数、最大公约数与欧几里得算法

素数的定义

素数（Prime Number）是大于 1 的自然数，除了 1 和它本身外没有其他正因数。前几个素数是：2, 3, 5, 7, 11, 13, 17, 19, 23, ...

大于 1 的非素数自然数称为合数（Composite Number）。

素数的基本性质

  • 算术基本定理：任何大于 1 的整数都可以唯一地分解为素数的乘积。如 60 = 2² × 3 × 5。
  • 素数无穷多：欧几里得证明了素数有无穷多个。
  • 素数定理：不超过 n 的素数个数 π(n) ≈ n / ln(n)。这意味着随机选一个 n 位数，它是素数的概率约为 1/ln(n)。

素数在密码学中的作用

素数是公钥密码学的基石：

  • RSA：安全性基于大素数 p、q 的乘积 n = p × q 难以分解。实际使用中 p、q 通常为 1024 位或更大。
  • Diffie-Hellman：使用大素数 p 和原根 g。
  • 椭圆曲线：曲线定义在素数域 GF(p) 上。

素性测试

判断一个大数是否为素数是密码学的关键操作：

  • 试除法：逐一试除到 √n，仅适用于小数。
  • Fermat 测试：若 n 为素数，则对所有 1 < a < n，有 an-1 ≡ 1 (mod n)。不满足则必为合数，但满足不一定为素数（Carmichael 数）。
  • Miller-Rabin 测试：Fermat 测试的改进，是目前最常用的概率性素性测试。重复 k 次可将错误概率降到 4-k。
  • AKS 算法：2002 年提出的确定性多项式时间素性测试，但实际效率不如 Miller-Rabin。

最大公约数（GCD）

最大公约数 gcd(a, b) 是同时整除 a 和 b 的最大正整数。

若 gcd(a, b) = 1，则称 a 和 b 互素（Coprime）。

欧几里得算法

基于性质 gcd(a, b) = gcd(b, a mod b)，递归计算直到 b = 0。

function gcd(a, b):
    while b ≠ 0:
        (a, b) = (b, a mod b)
    return a

例如：gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6。

扩展欧几里得算法

在计算 gcd(a, b) 的同时，求出整数 x, y 使得：

a × x + b × y = gcd(a, b)

密码学应用：当 gcd(a, b) = 1 时，求出的 x 就是 a 在模 b 下的模逆元。这是 RSA 中计算私钥 d = e-1 mod φ(n) 的关键算法。

function extended_gcd(a, b):
    if b == 0: return (a, 1, 0)
    (g, x1, y1) = extended_gcd(b, a mod b)
    return (g, y1, x1 - (a // b) * y1)

Bézout 定理

对任意整数 a 和 b，存在整数 x 和 y 使得 ax + by = gcd(a, b)。扩展欧几里得算法就是构造性地证明并求出这组 (x, y)。