从整数到模运算MoonMath Manual 算术篇——零知识证明数学基础第一课【免费下载链接】moonmath-manualA resource for anyone interested in understanding and unlocking the potential of zk-SNARKs, from beginners to experts.项目地址: https://gitcode.com/gh_mirrors/mo/moonmath-manual想要真正看懂 zk-SNARK绕不开的第一道坎就是模运算。零知识证明的数学基础本质上建立在一套从整数出发、在有限世界里重新定义加减乘除的算术系统之上。作为开源手册MoonMath Manual的算术篇导读本文将从最熟悉的整数算术讲起带你一步步走进同余、剩余类、素域与费马小定理用通俗的比喻和纸笔可算的例子完成零知识证明数学基础的第一课。完整内容可查看 arithmetics-moonmath.tex。为什么零知识证明需要重新学算术zk-SNARK零知识简洁非交互式知识论证的核心思想是在不泄露秘密输入的情况下证明我确实完成了一次计算。但现实世界的计算规模太大、太连续而密码学需要的是离散、可逆、难以猜测的运算空间。于是数学家把目光投向了一个看似奇怪的问题如果数字绕一圈就回到原点会发生什么这就是模运算。MoonMath Manual 的独特之处在于它让读者用纸和笔就能构造一个小型但完整可用的 zk-SNARK。而这一切的起点正是这本手册第一章Arithmetics里的整数算术与模运算。书中每个概念都配有手算例题、SageMath 校验代码和配套习题非常适合零基础入门。第一站整数算术里的三个老朋友在进入模运算之前先把三个基础概念复习一遍它们是后续所有内容的垫脚石。欧几里得除法带余除法对任意整数 a 和除数 b≠0总能唯一写成a m × b r 其中 0 ≤ r |b|例如 7 ÷ 3 2 余 1。这个商 余数的分解看似简单却是模运算定义的根基——同余的本质就是余数相等。素数只被 1 和自身整除的自然数2、3、5、7、11……。算术基本定理告诉我们每个自然数都可以唯一分解成素数的乘积。而乘法容易、分解极难这一不对称性正是众多密码系统的安全基石整数分解问题。扩展欧几里得算法不仅能算出最大公约数 gcd(a,b)还能同时找到整数 s、t 使 gcd(a,b) s·a t·b。它是后面计算模逆元的核心工具强烈建议动手跟着手册里的表格算一遍比如 gcd(12,5) 的例子。模运算入门像时钟一样绕圈的数字模运算最经典的比喻就是时钟。假设现在是 11 点20 小时后是几点不是 31 点而是 7 点——因为数字超过 12 就绕回去了。这个绕圈点就叫做模数modulus。把这种直觉形式化就得到**同余congruence**的定义两个整数除以模数 n 后余数相同就称它们关于 n 同余记作a ≡ b (mod n)比如以 12 为模-7、5、17、29 全部同余因为它们除以 12 的余数都是 5。同余最妙的地方在于它几乎可以像普通等式一样操作两边同加、同乘都成立但有一个关键区别——只有当 k 与模数互质时才能在同余式两边除以 k。这个细节在解同余方程时至关重要手册中专门用一个完整的例子模 6 下解7·(2x21)11 ≡ x-102 (mod 6)演示了全过程。模运算的计算规则从同余到费马小定理掌握了同余的基本操作后手册给出了几条计算规则compatibility with addition / multiplication / scaling 等并引出一个在密码学中无处不在的定理——费马小定理若 p 为素数则对任意整数 kk^p ≡ k (mod p) 若 k 与 p 互质还可写成k^(p-1) ≡ 1 (mod p)别看它只有一行费马小定理直接给出了素域中求模逆元的捷径r 的逆元就是 r^(p-2)模 p 下。例如在模 5 下3 的逆元是 3^3 27 ≡ 2而 3×2 6 ≡ 1验证成立。中国剩余定理多个同余方程的合体术有时候我们面对的不是单个同余式而是一组模数互质的同余方程组x ≡ 4 (mod 7) x ≡ 1 (mod 3) x ≡ 3 (mod 5) x ≡ 0 (mod 11)**中国剩余定理CRT**保证这样的方程组一定有解且所有解关于模数乘积 N 7×3×5×11 1155 同余。手册给出了完整的求解算法和手算步骤最终 x ≡ 88 mod 1155并配有 SageMath 的CRT_list校验。CRT 在现代密码学如 RSA 加速、秘密共享中被广泛使用值得反复练习。剩余类与模逆把无穷多压缩成有限个同余式的解往往有无穷多个例如 x ≡ 4 (mod 6) 的解是 {…, -8, -2, 4, 10, 16, …}计算起来很不方便。手册给出的优雅方案是剩余类余数类表示把余数相同的所有整数合并成一个代表元于是模 n 算术只剩下恰好 n 个数字0, 1, 2, …, n-1并定义出属于自己的加法和乘法表。这套系统记作 Zₙ。有了剩余类模逆元的概念就水到渠成a 的乘法逆元 a⁻¹ 满足 a × a⁻¹ ≡ 1 (mod n)。关键结论是a 存在模逆元 ⟺ gcd(a, n) 1a 与 n 互质逆元可用扩展欧几里得算法高效求出例如模 6 下5 与 6 互质其逆元是 5 本身而 2、3、4 都与 6 不互质没有逆元。素域为什么素数模数如此特殊如果把模数换成素数 p会发生奇妙的质变每个非零元素都有逆元任何方程 a·x b 0 都能像在有理数里一样求解且解唯一。这样的 Zₚ 称为素域prime field是椭圆曲线、配对、Groth16 等一切 zk-SNARK 底层结构的地基。举个例子方程 3x 3 0 在 Z₅ 中有唯一解 x 4但在 Z₆ 中却因为 3 没有逆元而无法直接求解实际存在 3 个解。这一差异正是素数模数在密码学中被偏爱的原因。模运算的威力也可以直观地看到——下面这张图展示了在模 43 的素域上满足椭圆曲线方程 y² x³ 6 (mod 43) 的全部 39 个点把坐标系换成更小的模数还能看到点集的另一种分布这些散点图来自手册后续的椭圆曲线章节正好印证了整数世界在模运算下如何演变成密码学需要的有限世界。从模运算到多项式通往 zk-SNARK 的最后一块拼图算术篇的最后一部分把整数算术平移到多项式世界多项式同样可以做带余除法、有素因子不可约多项式分解而最亮眼的工具是拉格朗日插值——给定 m1 个点就能唯一恢复一个 m 次多项式。手册还特别演示了同一组点 (0,4)、(-2,1)、(2,3) 在有理数域和 Z₅ 中分别插值出不同多项式直观展示了系数所在的世界如何影响结果。这一性质是 zk-SNARK 的核心机制把计算正确性转化为多项式在某点处为零的整除性问题再用配对与同态隐藏来验证。详细推导见后续章节与 intro-moonmath.tex。新手学习路线建议动手算手册每个小节都配有手算例题和习题先按欧几里得除法 → 扩展欧几里得 → 同余 → 模逆 → 素域的顺序逐个攻破。用 SageMath 校验文中大量sage:命令块如ZZ(12).xgcd(ZZ(5))、Integers(6)、CRT_list(...)可用来即时验证你的手算结果。对照练习配合 algebra-moonmath.tex 学习群、环、域等代数结构把算术篇的概念放到更大的框架里理解。获取源码可通过git clone https://gitcode.com/gh_mirrors/mo/moonmath-manual获取手册 LaTeX 源码跟随 Readme.adoc 中的构建步骤自行编译 PDF。零知识证明看起来高深莫测但正如 MoonMath Manual 反复强调的一旦适应了绕圈的数字这种新玩法模运算其实比想象中简单得多。从整数到模运算你已经迈出了 zk-SNARK 数学基础最关键的第一步。接下来就拿起笔跟着手册把第一个同余方程算出来吧【免费下载链接】moonmath-manualA resource for anyone interested in understanding and unlocking the potential of zk-SNARKs, from beginners to experts.项目地址: https://gitcode.com/gh_mirrors/mo/moonmath-manual创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考