数论（Number Theory）是数学中最古老且最迷人的分支之一，研究整数及其性质。从古希腊的欧几里得到近代的高斯、欧拉、拉马努金，数论一直是纯数学的核心领域。随着计算机科学的发展，数论在密码学、编码理论、算法设计、量子计算等领域展现出巨大的应用价值。
整除性理论是数论的基石，研究整数的加法与乘法结构。无论是最简单的算术还是最复杂的密码系统，都建立在这些基本概念之上。
对于整数 a a b b b ≠ 0 b = 0 q q a = b q a = b q b b a a b ∣ a b ∣ a b ∤ a b ∤ a
基本性质：
传递性： 若 a ∣ b a ∣ b b ∣ c b ∣ c a ∣ c a ∣ c 线性组合： 若 a ∣ b a ∣ b a ∣ c a ∣ c a ∣ ( b ± c ) a ∣ ( b ± c ) 数乘： 若 a ∣ b a ∣ b c c a ∣ b c a ∣ b c 对称性： 若 a ∣ b a ∣ b b ∣ a b ∣ a a = ± b a = ± b
定理（带余除法）： 对任意整数 a a b b q q r r a = b q + r a = b q + r 0 ≤ r < b 0 ≤ r < b
带余除法是所有数论算法的基础——从最大公约数的计算到素性测试，从模算术到多项式算法。
在计算机中，带余除法对应 / 和 % 运算符。需要注意的是，不同编程语言对负数的整除定义不同：Python 的 % 保证余数非负（0 ≤ r < b 0 ≤ r < b
整数 a a b b gcd ( a , b ) g cd( a , b ) a a b b
欧几里得算法（辗转相除法） 是已知最古老的算法之一（出现在欧几里得《几何原本》中，约公元前 300 年），至今仍是计算最大公约数的最高效方法：
gcd(a, b):
while b != 0:
a, b = b, a mod b
return |a|
时间复杂度： 最坏情况下 O ( log min ( a , b ) ) O ( log min ( a , b ) ) n n 5 n 5 n
扩展欧几里得算法 不仅能计算 gcd ( a , b ) g cd( a , b ) x , y x , y
a x + b y = gcd ( a , b ) a x + b y = g cd( a , b )
这在计算模逆元、求解线性丢番图方程中至关重要。实现时需要注意系数 x , y x , y O ( max ( a , b ) ) O ( max ( a , b ) )
lcm ( a , b ) lcm ( a , b ) a a b b
gcd ( a , b ) ⋅ lcm ( a , b ) = ∣ a b ∣ g cd( a , b ) ⋅ lcm ( a , b ) = ∣ a b ∣
定理（算术基本定理/唯一分解定理）： 每个大于 1 的整数都可以唯一分解为素数的乘积（不计顺序），即：
n = p 1 α 1 p 2 α 2 ⋯ p k α k n = p 1 α 1 p 2 α 2 ⋯ p k α k
其中 p i p i α i α i
这一定理是整个数论的根基。它的证明需要用到欧几里得引理（若素数 p ∣ a b p ∣ a b p ∣ a p ∣ a p ∣ b p ∣ b
同余是高斯在 1801 年出版的《算术研究》（Disquisitiones Arithmeticae）中系统引入的概念，是数论中最强大也最优雅的工具之一。
设 m m m ∣ ( a − b ) m ∣ ( a − b ) a a b b m m
a ≡ b ( m o d m ) a ≡ b ( m o d m )
同余关系是等价关系（满足自反性、对称性、传递性），它将整数划分为 m m
代数性质：
加法： 若 a ≡ b ( m o d m ) a ≡ b ( m o d m ) c ≡ d ( m o d m ) c ≡ d ( m o d m ) a ± c ≡ b ± d ( m o d m ) a ± c ≡ b ± d ( m o d m ) 乘法： 若 a ≡ b ( m o d m ) a ≡ b ( m o d m ) c ≡ d ( m o d m ) c ≡ d ( m o d m ) a c ≡ b d ( m o d m ) a c ≡ b d ( m o d m ) 指数： 若 a ≡ b ( m o d m ) a ≡ b ( m o d m ) a k ≡ b k ( m o d m ) a k ≡ b k ( m o d m )
注意：除法没有直接的模运算性质 ——模 m m
模 m m 完全剩余系 是 { 0 , 1 , 2 , … , m − 1 } { 0 , 1 , 2 , … , m − 1 }
简化剩余系 （既约剩余系）由与 m m φ ( m ) φ ( m )
费马小定理（1640）： 若 p p p ∤ a p ∤ a
a p − 1 ≡ 1 ( m o d p ) a p − 1 ≡ 1 ( m o d p )
费马最初以信件形式提出该定理，未给出证明。莱布尼茨留下了未发表的证明手稿，欧拉在 1736 年首次公开发表证明。
欧拉定理（1763）： 若 gcd ( a , m ) = 1 g cd( a , m ) = 1
a φ ( m ) ≡ 1 ( m o d m ) a φ ( m ) ≡ 1 ( m o d m )
这两个定理是 RSA 密码算法的数学基础。例如，RSA 解密能正确恢复原文正是依赖于 m e d ≡ m ( m o d n ) m e d ≡ m ( m o d n )
若 gcd ( a , m ) = 1 g cd( a , m ) = 1 x x
a x ≡ 1 ( m o d m ) a x ≡ 1 ( m o d m )
称 x x a a m m a − 1 ( m o d m ) a − 1 ( m o d m )
模逆元可通过扩展欧几里得算法或利用欧拉定理 (a φ ( m ) − 1 a φ ( m ) − 1
定理（CRT）： 设 m 1 , m 2 , … , m k m 1 , m 2 , … , m k a 1 , a 2 , … , a k a 1 , a 2 , … , a k
{ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) x ≡ a k ( m o d m k ) ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) ⋮ x ≡ a k ( m o d m k )
在模 M = m 1 m 2 ⋯ m k M = m 1 m 2 ⋯ m k
历史： 中国剩余定理的名称来源于公元 3 至 5 世纪的《孙子算经》中的"物不知数"问题："今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？"
应用价值：
RSA 解密加速： 利用 CRT，RSA 解密速度可提升约 4 倍（将 n n n / 2 n / 2 秘密共享： Shamir 的秘密共享方案基于多项式插值，与 CRT 思想相通大整数表示： 将大整数表示为剩余系下的分量，实现并行算术
定理： p p ( p − 1 ) ! ≡ − 1 ( m o d p ) ( p − 1 ) ! ≡ − 1 ( m o d p )
该定理虽给出了素数的充要条件，但因阶乘的计算开销极大，实践中不用于素性测试。
素数是数论的"原子"，如同化学中的元素周期表——所有整数都由素数"构成"。
欧几里得定理（约公元前 300 年）： 素数有无穷多个。
证明（经典反证）： 假设素数有限，为 p 1 , p 2 , … , p n p 1 , p 2 , … , p n N = p 1 p 2 ⋯ p n + 1 N = p 1 p 2 ⋯ p n + 1 N N p p p p p ∣ 1 p ∣ 1 p p
这一简洁的证明被誉为数学中最优美的证明之一。
素数定理（PNT，1896，Hadamard/de la Vallée-Poussin 独立证明）： 不超过 x x π ( x ) π ( x )
π ( x ) ∼ x ln x π ( x ) ∼ ln x x
这意味着在 1 到 n n 1 / ln n 1 / ln n
更精确的估计： π ( x ) ≈ Li ( x ) = ∫ 2 x d t ln t π ( x ) ≈ Li ( x ) = ∫ 2 x l n t d t
判断一个数是否为素数，对密码学至关重要。以下是主要算法的对比：
确定性算法：
算法
时间复杂度
说明
试除法
O ( n ) O ( n ) 适合 < 1 0 12 < 1 0 1 2
AKS（2002）
O ( 6 + ϵ n ) O ( log 6 + ϵ n ) 首个无条件确定多项式时间算法，理论意义远大于实践
ECPP
亚指数时间
实践中最快的确定性方法之一
概率性算法（实践中首选）：
算法
说明
误判率
Miller-Rabin
最常用
< 4 − k < 4 − k k k
Baillie-PSW
无已知反例
实践中可视为确定
费马检验
不推荐
存在卡迈克尔数
Miller-Rabin 素性测试实践指南：
32 位整数：测试基 { 2 , 7 , 61 } { 2 , 7 , 6 1 }
64 位整数：测试基 { 2 , 325 , 9375 , 28178 , 450775 , 9780504 , 1795265022 } { 2 , 3 2 5 , 9 3 7 5 , 2 8 1 7 8 , 4 5 0 7 7 5 , 9 7 8 0 5 0 4 , 1 7 9 5 2 6 5 0 2 2 }
通用：12 轮随机基即可达到 < 1 0 − 7 < 1 0 − 7
注意： 卡迈克尔数是费马小定理的反例——对一切与 n n a a a n − 1 ≡ 1 ( m o d n ) a n − 1 ≡ 1 ( m o d n )
密码学应用中常需要生成大素数，流程如下：
随机生成一个 k k
用小素数表（前几百个素数）快速筛除合数
使用 Miller-Rabin 测试（多轮）精确检验
通过检验的可信概率极高
实践要点：
使用密码学安全的随机数生成器（如 /dev/urandom），而非 rand()
RSA 的 p p q q
避免 p − 1 p − 1 p = 2 q + 1 p = 2 q + 1 q q
整数分解被认为是计算困难的（NP 但不知是否为 NP-完全），这正是 RSA 的安全性基础。
主要分解算法：
算法
发明时间
复杂度
适用范围
试除法
古代
O ( n ) O ( n ) 极小因子
Pollard's ρ ρ
1975
O ( n 1 / 4 ) O ( n 1 / 4 ) 中等因子 (< 1 0 20 < 1 0 2 0
Pollard's p − 1 p − 1
1974
O ( B log n ) O ( B log n ) 平滑因子
二次筛法 (QS)
1981
亚指数
~100 位十进制数
数域筛法 (NFS)
1990
亚指数
≥100 位（最快渐进）
当前记录（2025+）： RSA-250（829 位二进制/250 位十进制）已于 2020 年被分解，耗时约 2700 核心年。
数论中研究了许多特殊类型的素数：
梅森素数： 形如 M p = 2 p − 1 M p = 2 p − 1 M 3 = 7 , M 5 = 31 , M 7 = 127 M 3 = 7 , M 5 = 3 1 , M 7 = 1 2 7 孪生素数： 相差 2 的素数对，如 ( 3 , 5 ) , ( 5 , 7 ) , ( 11 , 13 ) ( 3 , 5 ) , ( 5 , 7 ) , ( 1 1 , 1 3 ) 索菲·日尔曼素数： 若 p p 2 p + 1 2 p + 1 p p 高斯素数： 在复整数环 Z [ i ] Z [ i ]
数论函数是定义在正整数上的函数，在数论中扮演重要角色。许多数论函数是积性函数（f ( m n ) = f ( m ) f ( n ) f ( m n ) = f ( m ) f ( n ) gcd ( m , n ) = 1 g cd( m , n ) = 1
φ ( n ) φ ( n ) n n n n
φ ( n ) = n ∏ p ∣ n ( 1 − 1 p ) φ ( n ) = n p ∣ n ∏ ( 1 − p 1 )
重要性质：
若 p p φ ( p ) = p − 1 φ ( p ) = p − 1
积性：若 gcd ( m , n ) = 1 g cd( m , n ) = 1 φ ( m n ) = φ ( m ) φ ( n ) φ ( m n ) = φ ( m ) φ ( n )
和式：∑ d ∣ n φ ( d ) = n ∑ d ∣ n φ ( d ) = n
对于 n > 2 n > 2 φ ( n ) φ ( n )
μ ( n ) = { 1 n = 1 ( − 1 ) k n 为 k 个不同素数之积 0 n 有平方因子 μ ( n ) = ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ 1 ( − 1 ) k 0 n = 1 n 为 k 个不同素数之积 n 有平方因子
莫比乌斯反演公式： 若 F ( n ) = ∑ d ∣ n f ( d ) F ( n ) = ∑ d ∣ n f ( d )
f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) f ( n ) = d ∣ n ∑ μ ( d ) F ( d n )
这一定理在组合数论和解析数论中极其重要，允许我们在求和函数和原函数之间转换。
σ k ( n ) = ∑ d ∣ n d k σ k ( n ) = d ∣ n ∑ d k
σ 0 ( n ) σ 0 ( n ) d ( n ) d ( n ) τ ( n ) τ ( n ) n n σ 1 ( n ) σ 1 ( n ) σ ( n ) σ ( n ) n n
完美数 是满足 σ ( n ) = 2 n σ ( n ) = 2 n
6 = 1 + 2 + 3 , 28 = 1 + 2 + 4 + 7 + 14 , 496 , 8128 6 = 1 + 2 + 3 , 2 8 = 1 + 2 + 4 + 7 + 1 4 , 4 9 6 , 8 1 2 8
每个偶完美数都对应于一个梅森素数：若 2 p − 1 2 p − 1 2 p − 1 ( 2 p − 1 ) 2 p − 1 ( 2 p − 1 )
曼戈尔特函数 Λ ( n ) Λ ( n ) Λ ( n ) = ln p Λ ( n ) = ln p n n p p 刘维尔函数 λ ( n ) λ ( n ) 若 n n λ ( n ) = − 1 λ ( n ) = − 1
丢番图方程是整数系数的多项式方程，只求整数解。以 3 世纪古希腊数学家丢番图的著作《算术》命名。
形如 a x + b y = c a x + b y = c gcd ( a , b ) ∣ c g cd( a , b ) ∣ c
x = x 0 + b gcd ( a , b ) t , y = y 0 − a gcd ( a , b ) t , t ∈ Z x = x 0 + g cd( a , b ) b t , y = y 0 − g cd( a , b ) a t , t ∈ Z
x 2 + y 2 = z 2 x 2 + y 2 = z 2 gcd ( x , y , z ) = 1 g cd( x , y , z ) = 1
x = m 2 − n 2 , y = 2 m n , z = m 2 + n 2 x = m 2 − n 2 , y = 2 m n , z = m 2 + n 2
其中 m > n m > n gcd ( m , n ) = 1 g cd( m , n ) = 1 m , n m , n
定理（Wiles，1994）： 方程 x n + y n = z n x n + y n = z n n ≥ 3 n ≥ 3
费马在 1637 年阅读丢番图《算术》时，在页边写下此猜想并注"我发现了一个真正美妙的证明，但页边太小写不下"。历经 358 年、几代数学家的努力，最终由安德鲁·怀尔斯用椭圆曲线和模形式理论证明。这是现代数学史上最辉煌的成就之一。
形如 x 2 − D y 2 = 1 x 2 − D y 2 = 1 D D D = 61 D = 6 1 x = 1766319049 , y = 226153980 x = 1 7 6 6 3 1 9 0 4 9 , y = 2 2 6 1 5 3 9 8 0
设 p p x x x 2 ≡ a ( m o d p ) x 2 ≡ a ( m o d p ) a a p p 二次剩余 ，否则为二次非剩余 。在模 p p
勒让德符号 ( a p ) ( p a )
( a p ) = { 1 a 是模 p 的二次剩余且 p ∤ a − 1 a 是模 p 的二次非剩余 0 p ∣ a ( p a ) = ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ 1 − 1 0 a 是模 p 的二次剩余且 p ∤ a a 是模 p 的二次非剩余 p ∣ a
定理（高斯，1796）： 设 p , q p , q
( p q ) ( q p ) = ( − 1 ) p − 1 2 ⋅ q − 1 2 ( q p ) ( p q ) = ( − 1 ) 2 p − 1 ⋅ 2 q − 1
高斯称此为"黄金定理"，它给出了 8 种不同的证明。二次互反律允许我们高效计算勒让德符号，无需实际计算平方根。
平方根模素数： Tonelli-Shanks 算法可在 O ( 2 p ) O ( log 2 p ) Rabin 密码系统： 安全性基于模合数平方根的困难性Goldwasser-Micali 加密： 基于二次剩余判定的概率加密数域筛法： NFS 算法内部大量使用二次互反律
设 gcd ( a , m ) = 1 g cd( a , m ) = 1 a k ≡ 1 ( m o d m ) a k ≡ 1 ( m o d m ) k k a a m m 阶 ，记作 ord m ( a ) ord m ( a )
若 ord m ( a ) = φ ( m ) ord m ( a ) = φ ( m ) a a m m 原根 。模 m m m = 2 , 4 , p k , 2 p k m = 2 , 4 , p k , 2 p k p p φ ( φ ( m ) ) φ ( φ ( m ) )
给定素数 p p g g y = g x ( m o d p ) y = g x ( m o d p ) x x
Diffie-Hellman 密钥交换（1976） ElGamal 加密（1985） 数字签名算法（DSA）
求解 DLP 的算法：
算法
时间复杂度
说明
大步小步法 (BSGS)
O ( p ) O ( p ) 确定性，空间 O ( p ) O ( p )
Pollard's ρ ρ
O ( p ) O ( p ) 概率性，空间 O ( 1 ) O ( 1 )
Pohlig-Hellman
取决于因子分解
若 p − 1 p − 1
指数积分法
亚指数
对有限域有效
量子算法 (Shor)
O ( 3 p ) O ( log 3 p ) 需量子计算机
安全性要求： 当前安全级别要求 p p
连分数是将实数表示为以下形式的表达式：
a 0 + 1 a 1 + 1 a 2 + 1 a 3 + ⋱ a 0 + a 1 + a 2 + a 3 + ⋱ 1 1 1
基本性质：
有理数的连分数展开有限
无理数的连分数展开无限
二次无理数（有理系数二次方程的根）的连分数循环
著名连分数的例子：
黄金比例 ϕ = [ 1 ; 1 , 1 , 1 , … ] = 1 + 5 2 ϕ = [ 1 ; 1 , 1 , 1 , … ] = 2 1 + 5
圆周率 π = [ 3 ; 7 , 15 , 1 , 292 , 1 , 1 , 1 , 2 , … ] π = [ 3 ; 7 , 1 5 , 1 , 2 9 2 , 1 , 1 , 1 , 2 , … ]
自然底数 e = [ 2 ; 1 , 2 , 1 , 1 , 4 , 1 , 1 , 6 , 1 , 1 , 8 , … ] e = [ 2 ; 1 , 2 , 1 , 1 , 4 , 1 , 1 , 6 , 1 , 1 , 8 , … ]
应用：
求解佩尔方程
最佳有理逼近（如 π ≈ 355 / 113 π ≈ 3 5 5 / 1 1 3 3 × 1 0 − 7 3 × 1 0 − 7
连分数分解算法（CFRAC）
解析数论使用复分析和实分析的工具有研究数论问题。
黎曼 ζ 函数定义为（ℜ ( s ) > 1 ℜ ( s ) > 1
ζ ( s ) = ∑ n = 1 ∞ 1 n s = ∏ p 素数 1 1 − p − s ζ ( s ) = n = 1 ∑ ∞ n s 1 = p 素数 ∏ 1 − p − s 1
欧拉乘积公式建立了 ζ 函数与素数的联系。
黎曼在 1859 年的论文《论不超过某值的素数个数》中提出：ζ 函数的所有非平凡零点都在 ℜ ( s ) = 1 / 2 ℜ ( s ) = 1 / 2
黎曼猜想的成立将极大改善素数定理的误差项，并深刻影响数论的许多领域。
定理（Dirichlet，1837）： 对于任意互素的正整数 a , d a , d a , a + d , a + 2 d , … a , a + d , a + 2 d , …
这一定理使用 Dirichlet L-函数证明，标志着解析数论的诞生。
基于大素数分解的困难性：
选取两个大素数 p , q p , q n = p q n = p q
选取加密指数 e e gcd ( e , φ ( n ) ) = 1 g cd( e , φ ( n ) ) = 1
计算解密指数 d ≡ e − 1 ( m o d φ ( n ) ) d ≡ e − 1 ( m o d φ ( n ) )
加密：c ≡ m e ( m o d n ) c ≡ m e ( m o d n ) m ≡ c d ( m o d n ) m ≡ c d ( m o d n )
安全参数建议（NIST SP 800-57）：
年份
RSA 密钥长度
等效对称密钥
当前
2048 位
112 位
近期
3072 位
128 位
远期
15360 位
256 位
基于离散对数问题的困难性，允许双方在不安全的信道上协商共享密钥。这是公钥密码学的奠基性贡献。
在椭圆曲线的点群上实现离散对数密码系统。ECC 使用更短的密钥提供同等安全性：
ECC 密钥长度
RSA 等效长度
对称等效
256 位
3072 位
128 位
384 位
7680 位
192 位
521 位
15360 位
256 位
随着量子计算的发展，基于数论的经典密码系统面临威胁。Shor 算法可在多项式时间内分解大整数和计算离散对数。
正在标准化的后量子方案：
格密码（CRYSTALS-Kyber/Dilithium）： 基于格上的困难问题哈希签名（SPHINCS+）： 基于哈希函数的签名编码密码（Classic McEliece）： 基于纠错码的解码困难性
数论中有大量表面简单但极其深刻的问题：
问题
提出时间
当前状态
简述
黎曼猜想
1859
未解（千年大奖）
ζ 函数零点均在 Re(s)=1/2
哥德巴赫猜想
1742
未解
偶数 = 两素数之和
孪生素数猜想
约 1849
未解
无穷多对相差 2 的素数
abc 猜想
1985
争议中
望月新一声称证明
BSD 猜想
1960s
未解（千年大奖）
椭圆曲线秩与 L 函数
奇完美数
古代
未解
是否存在奇完美数？
华林问题
1770
基本解决
整数的幂和表示
考拉兹猜想
1937
未解
3n+1 问题
工具/库
语言
说明
SymPy
Python
符号数学，数论功能全面
gmpy2
Python
基于 GMP 的高精度运算
GMP / MPIR
C/C++
高精度整数运算库
NTL
C++
数论与多项式库
PARI/GP
专用
数论计算机代数系统
SageMath
Python
统一的数学系统，数论极强
BigInteger
Java
内置大整数与素性测试
# 最大公约数与扩展欧几里得算法
def egcd(a, b):
if b == 0:
return (a, 1, 0)
g, x1, y1 = egcd(b, a % b)
return (g, y1, x1 - (a // b) * y1)
# Miller-Rabin 素性测试
def is_probable_prime(n, rounds=12):
if n < 2: return False
if n in (2, 3): return True
if n % 2 == 0: return False
d, s = n - 1, 0
while d % 2 == 0:
d //= 2
s += 1
import random
for _ in range(rounds):
a = random.randrange(2, n - 1)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(s - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
针对不同目标读者的建议学习路径：
入门路径（无高等数学背景）：
整除性与带余除法
最大公约数与欧几里得算法
算术基本定理
同余基础
中国剩余定理
数学专业路径：
同余理论深究与剩余系
二次剩余与二次互反律
原根与离散对数
数论函数与 Dirichlet 卷积
二次型理论
解析数论入门
代数数论基础
计算机科学/密码学路径：
模算术与快速幂算法
扩展欧几里得算法与模逆元
Miller-Rabin 素性测试
RSA 与 DH 协议的数论基础
椭圆曲线密码学
格密码学基础
推荐阅读：
《初等数论及其应用》（Rosen）——经典教材，理论与实践并重
《具体数学》（Graham, Knuth, Patashnik）——数论与计算机科学交叉
《数论导引》（Hardy & Wright）——经典理论著作
《A Computational Introduction to Number Theory and Algebra》（Shoup）——计算数论权威参考
《An Introduction to the Theory of Numbers》（Niven, Zuckerman, Montgomery）——经典教材
本文是数学知识库的一部分，涵盖数论的核心概念、理论基础、算法实现与现代应用。文章从整除性出发，延伸到同余理论、素数分布、数论函数、丢番图方程等经典分支，并详细讨论了数论在密码学中的核心应用。