有限域上模运算为何难逆
有限域上的模乘法本身是双射、结构完全确定，可一旦把多次乘法叠成幂，求逆就退化为遍历整个乘法群，规模随域大小指数膨胀。
A complete interactive classroom, not just a preview.
Start when you are ready to enter this Stage's 4 scenes and explore, respond, and learn as you go.
为什么有限域上的模乘法和幂运算在域足够大时几乎无法求逆？
在普通整数里，把 7 乘以某个数再取模，你总能反推出原来的数；但在密码学常用的有限域 GF(p) 里，同样的乘法却几乎没人能反推。
既然模运算只是一次除法取余，听上去完全可逆，为什么乘法在有限域上就成了现代公钥密码的算力基石？
先展示整数模 n 下乘法可逆的简短例子，再用同一手法对比 GF(p) 上离散对数在小域与大域中求解时间的跳跃，让'域越大、逆运算越像暴力'变得肉眼可见。
有限域模运算的难逆性来自域内结构没有给逆运算提供捷径：唯一的通用方法是把整个乘法表重新遍历一遍；域越大，这个遍历代价按指数增长。
- 不展开具体椭圆曲线或 RSA 的工程实现
- 不讲解欧拉定理、费马小定理的形式化证明
- 不介绍 Pollard rho、指数微积分等子指数算法细节
- 01一个反直觉的对比slideSlot 1Hook
在普通整数模 11 下，已知 7·x ≡ 3 (mod 11)，可以秒算 x；同样形式的等式放到密码学使用的巨大有限域中，求 x 却需要全球算力。
- 整数小模数下乘法可逆
- 密码学使用几百位的大素数域
- 问题形式相同，求解难度天差地别
Phenomenon同一个等式 7·x ≡ 3 (mod n) 在不同 n 下求解难度悬殊
Question是什么把'取一次余'变成了一道几乎无解的题？
- 02亲手感受乘法群的大小interactiveSlot 2Tension
在 GF(p) 中输入一个素数 p，对比 p 较小时整个乘法表的规模与 p 增大后乘法表规模的爆炸式增长。
- 选定素数 p
- 观察 |GF(p)*| = p−1 的乘法群大小
- 体会 p 翻倍时元素数量线性增长而遍历代价指数级
Prediction把 p 从 11 改到 23 之类的大小，乘法表元素只会多一倍，应该很快就能暴力穷举。
Tempting intuition线性变大的群，对计算机来说应该毫无压力。
- 03一次乘法可逆，多次幂运算无捷径slideSlot 3Reveal
在 GF(p) 中，单步乘法 a·b 永远保持双射，乘以 a 的逆元 a^(p−2) 即可解出 b；但若把乘法反复堆叠成 g^x，这就是离散对数问题，唯一通用解法是逐一尝试 1, 2, …, p−2，代价为 O(p)。
- 单次模乘法是双射，存在显式逆元
- 幂运算 g^x 把 x 折叠成群中的一个点
- 求逆等价于对 p−1 个候选值逐一尝试
- p 每增加一位比特，工作量翻倍
Evidence从 g=3, p=11 出发，画出 3^0..3^9 的值表，再用同样手法画到 g=3, p=2^20 附近时表项数量已经达到百万级。
Conclusion有限域上的难逆性不是来自模运算本身，而是来自幂运算把指数折叠后，唯一的通用求逆方法就是遍历 p−1 个候选。
Mechanism- 1第一步：单次模乘 a·b 在有限域内是双射，逆元就是 a^(p−2) mod p
- 2第二步：把乘法重复 x 次得到 g^x，多个不同的 x 会折叠到群中同一个点上
- 3第三步：折叠之后，结构信息被压缩，反推只能暴力遍历整个群
- 04迁移到任意公开指数难题slideSlot 4Takeaway
把'幂运算折叠指数、只能用遍历求逆'这一机制搬到 Diffie-Hellman 密钥交换或 ElGamal 签名中：公开 g 和 g^x 不暴露 x，正是因为 GF(p) 上的离散对数没有代数捷径。
- Diffie-Hellman 安全 = 离散对数难
- 任何公开 g^x 的协议都依赖同一折叠效应
- 域大小决定安全等级，与具体协议无关
Transfer面对一个未知公开值 g^x mod p，应预期其安全性来自群大小而非协议设计。
Expected inference只要底层群足够大，攻击者拿到的只有折叠后的点，无论协议多精巧都无法反推指数。
Discussion threads for a Stage aren't available yet.
