從整數到模運算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?1 滿足 a × a?1 ≡ 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 的素域上滿足橢圓曲線方程 y2 x3 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），僅供參考 從整數到模運算：MoonMath Manual 算術篇——零知識證明數學基礎第一課
從整數到模運算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?1 滿足 a × a?1 ≡ 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 的素域上滿足橢圓曲線方程 y2 x3 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），僅供參考