從整數(shù)到模運(yùn)算MoonMath Manual 算術(shù)篇——零知識證明數(shù)學(xué)基礎(chǔ)第一課【免費(fèi)下載鏈接】moonmath-manualA resource for anyone interested in understanding and unlocking the potential of zk-SNARKs, from beginners to experts.項(xiàng)目地址: https://gitcode.com/gh_mirrors/mo/moonmath-manual想要真正看懂 zk-SNARK繞不開的第一道坎就是模運(yùn)算。零知識證明的數(shù)學(xué)基礎(chǔ)本質(zhì)上建立在一套從整數(shù)出發(fā)、在有限世界里重新定義加減乘除的算術(shù)系統(tǒng)之上。作為開源手冊MoonMath Manual的算術(shù)篇導(dǎo)讀本文將從最熟悉的整數(shù)算術(shù)講起帶你一步步走進(jìn)同余、剩余類、素域與費(fèi)馬小定理用通俗的比喻和紙筆可算的例子完成零知識證明數(shù)學(xué)基礎(chǔ)的第一課。完整內(nèi)容可查看 arithmetics-moonmath.tex。為什么零知識證明需要重新學(xué)算術(shù)zk-SNARK零知識簡潔非交互式知識論證的核心思想是在不泄露秘密輸入的情況下證明我確實(shí)完成了一次計(jì)算。但現(xiàn)實(shí)世界的計(jì)算規(guī)模太大、太連續(xù)而密碼學(xué)需要的是離散、可逆、難以猜測的運(yùn)算空間。于是數(shù)學(xué)家把目光投向了一個(gè)看似奇怪的問題如果數(shù)字繞一圈就回到原點(diǎn)會發(fā)生什么這就是模運(yùn)算。MoonMath Manual 的獨(dú)特之處在于它讓讀者用紙和筆就能構(gòu)造一個(gè)小型但完整可用的 zk-SNARK。而這一切的起點(diǎn)正是這本手冊第一章Arithmetics里的整數(shù)算術(shù)與模運(yùn)算。書中每個(gè)概念都配有手算例題、SageMath 校驗(yàn)代碼和配套習(xí)題非常適合零基礎(chǔ)入門。第一站整數(shù)算術(shù)里的三個(gè)老朋友在進(jìn)入模運(yùn)算之前先把三個(gè)基礎(chǔ)概念復(fù)習(xí)一遍它們是后續(xù)所有內(nèi)容的墊腳石。歐幾里得除法帶余除法對任意整數(shù) a 和除數(shù) b≠0總能唯一寫成a m × b r 其中 0 ≤ r |b|例如 7 ÷ 3 2 余 1。這個(gè)商 余數(shù)的分解看似簡單卻是模運(yùn)算定義的根基——同余的本質(zhì)就是余數(shù)相等。素?cái)?shù)只被 1 和自身整除的自然數(shù)2、3、5、7、11……。算術(shù)基本定理告訴我們每個(gè)自然數(shù)都可以唯一分解成素?cái)?shù)的乘積。而乘法容易、分解極難這一不對稱性正是眾多密碼系統(tǒng)的安全基石整數(shù)分解問題。擴(kuò)展歐幾里得算法不僅能算出最大公約數(shù) gcd(a,b)還能同時(shí)找到整數(shù) s、t 使 gcd(a,b) s·a t·b。它是后面計(jì)算模逆元的核心工具強(qiáng)烈建議動(dòng)手跟著手冊里的表格算一遍比如 gcd(12,5) 的例子。模運(yùn)算入門像時(shí)鐘一樣繞圈的數(shù)字模運(yùn)算最經(jīng)典的比喻就是時(shí)鐘。假設(shè)現(xiàn)在是 11 點(diǎn)20 小時(shí)后是幾點(diǎn)不是 31 點(diǎn)而是 7 點(diǎn)——因?yàn)閿?shù)字超過 12 就繞回去了。這個(gè)繞圈點(diǎn)就叫做模數(shù)modulus。把這種直覺形式化就得到**同余congruence**的定義兩個(gè)整數(shù)除以模數(shù) n 后余數(shù)相同就稱它們關(guān)于 n 同余記作a ≡ b (mod n)比如以 12 為模-7、5、17、29 全部同余因?yàn)樗鼈兂?12 的余數(shù)都是 5。同余最妙的地方在于它幾乎可以像普通等式一樣操作兩邊同加、同乘都成立但有一個(gè)關(guān)鍵區(qū)別——只有當(dāng) k 與模數(shù)互質(zhì)時(shí)才能在同余式兩邊除以 k。這個(gè)細(xì)節(jié)在解同余方程時(shí)至關(guān)重要手冊中專門用一個(gè)完整的例子模 6 下解7·(2x21)11 ≡ x-102 (mod 6)演示了全過程。模運(yùn)算的計(jì)算規(guī)則從同余到費(fèi)馬小定理掌握了同余的基本操作后手冊給出了幾條計(jì)算規(guī)則compatibility with addition / multiplication / scaling 等并引出一個(gè)在密碼學(xué)中無處不在的定理——費(fèi)馬小定理若 p 為素?cái)?shù)則對任意整數(shù) kk^p ≡ k (mod p) 若 k 與 p 互質(zhì)還可寫成k^(p-1) ≡ 1 (mod p)別看它只有一行費(fèi)馬小定理直接給出了素域中求模逆元的捷徑r 的逆元就是 r^(p-2)模 p 下。例如在模 5 下3 的逆元是 3^3 27 ≡ 2而 3×2 6 ≡ 1驗(yàn)證成立。中國剩余定理多個(gè)同余方程的合體術(shù)有時(shí)候我們面對的不是單個(gè)同余式而是一組模數(shù)互質(zhì)的同余方程組x ≡ 4 (mod 7) x ≡ 1 (mod 3) x ≡ 3 (mod 5) x ≡ 0 (mod 11)**中國剩余定理CRT**保證這樣的方程組一定有解且所有解關(guān)于模數(shù)乘積 N 7×3×5×11 1155 同余。手冊給出了完整的求解算法和手算步驟最終 x ≡ 88 mod 1155并配有 SageMath 的CRT_list校驗(yàn)。CRT 在現(xiàn)代密碼學(xué)如 RSA 加速、秘密共享中被廣泛使用值得反復(fù)練習(xí)。剩余類與模逆把無窮多壓縮成有限個(gè)同余式的解往往有無窮多個(gè)例如 x ≡ 4 (mod 6) 的解是 {…, -8, -2, 4, 10, 16, …}計(jì)算起來很不方便。手冊給出的優(yōu)雅方案是剩余類余數(shù)類表示把余數(shù)相同的所有整數(shù)合并成一個(gè)代表元于是模 n 算術(shù)只剩下恰好 n 個(gè)數(shù)字0, 1, 2, …, n-1并定義出屬于自己的加法和乘法表。這套系統(tǒng)記作 Z?。有了剩余類模逆元的概念就水到渠成a 的乘法逆元 a?1 滿足 a × a?1 ≡ 1 (mod n)。關(guān)鍵結(jié)論是a 存在模逆元 ? gcd(a, n) 1a 與 n 互質(zhì)逆元可用擴(kuò)展歐幾里得算法高效求出例如模 6 下5 與 6 互質(zhì)其逆元是 5 本身而 2、3、4 都與 6 不互質(zhì)沒有逆元。素域?yàn)槭裁此財(cái)?shù)模數(shù)如此特殊如果把模數(shù)換成素?cái)?shù) p會發(fā)生奇妙的質(zhì)變每個(gè)非零元素都有逆元任何方程 a·x b 0 都能像在有理數(shù)里一樣求解且解唯一。這樣的 Z? 稱為素域prime field是橢圓曲線、配對、Groth16 等一切 zk-SNARK 底層結(jié)構(gòu)的地基。舉個(gè)例子方程 3x 3 0 在 Z? 中有唯一解 x 4但在 Z? 中卻因?yàn)?3 沒有逆元而無法直接求解實(shí)際存在 3 個(gè)解。這一差異正是素?cái)?shù)模數(shù)在密碼學(xué)中被偏愛的原因。模運(yùn)算的威力也可以直觀地看到——下面這張圖展示了在模 43 的素域上滿足橢圓曲線方程 y2 x3 6 (mod 43) 的全部 39 個(gè)點(diǎn)把坐標(biāo)系換成更小的模數(shù)還能看到點(diǎn)集的另一種分布這些散點(diǎn)圖來自手冊后續(xù)的橢圓曲線章節(jié)正好印證了整數(shù)世界在模運(yùn)算下如何演變成密碼學(xué)需要的有限世界。從模運(yùn)算到多項(xiàng)式通往 zk-SNARK 的最后一塊拼圖算術(shù)篇的最后一部分把整數(shù)算術(shù)平移到多項(xiàng)式世界多項(xiàng)式同樣可以做帶余除法、有素因子不可約多項(xiàng)式分解而最亮眼的工具是拉格朗日插值——給定 m1 個(gè)點(diǎn)就能唯一恢復(fù)一個(gè) m 次多項(xiàng)式。手冊還特別演示了同一組點(diǎn) (0,4)、(-2,1)、(2,3) 在有理數(shù)域和 Z? 中分別插值出不同多項(xiàng)式直觀展示了系數(shù)所在的世界如何影響結(jié)果。這一性質(zhì)是 zk-SNARK 的核心機(jī)制把計(jì)算正確性轉(zhuǎn)化為多項(xiàng)式在某點(diǎn)處為零的整除性問題再用配對與同態(tài)隱藏來驗(yàn)證。詳細(xì)推導(dǎo)見后續(xù)章節(jié)與 intro-moonmath.tex。新手學(xué)習(xí)路線建議動(dòng)手算手冊每個(gè)小節(jié)都配有手算例題和習(xí)題先按歐幾里得除法 → 擴(kuò)展歐幾里得 → 同余 → 模逆 → 素域的順序逐個(gè)攻破。用 SageMath 校驗(yàn)文中大量sage:命令塊如ZZ(12).xgcd(ZZ(5))、Integers(6)、CRT_list(...)可用來即時(shí)驗(yàn)證你的手算結(jié)果。對照練習(xí)配合 algebra-moonmath.tex 學(xué)習(xí)群、環(huán)、域等代數(shù)結(jié)構(gòu)把算術(shù)篇的概念放到更大的框架里理解。獲取源碼可通過git clone https://gitcode.com/gh_mirrors/mo/moonmath-manual獲取手冊 LaTeX 源碼跟隨 Readme.adoc 中的構(gòu)建步驟自行編譯 PDF。零知識證明看起來高深莫測但正如 MoonMath Manual 反復(fù)強(qiáng)調(diào)的一旦適應(yīng)了繞圈的數(shù)字這種新玩法模運(yùn)算其實(shí)比想象中簡單得多。從整數(shù)到模運(yùn)算你已經(jīng)邁出了 zk-SNARK 數(shù)學(xué)基礎(chǔ)最關(guān)鍵的第一步。接下來就拿起筆跟著手冊把第一個(gè)同余方程算出來吧【免費(fèi)下載鏈接】moonmath-manualA resource for anyone interested in understanding and unlocking the potential of zk-SNARKs, from beginners to experts.項(xiàng)目地址: https://gitcode.com/gh_mirrors/mo/moonmath-manual創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考