你也可以手繪二維碼（二）糾錯碼字演算法：數論基礎及伽羅瓦域GF（2^8）

摘要： 摘要：本文講解二維碼糾錯碼字生成使用到的數學數論基礎知識，伽羅瓦域（Galois Field）GF（2^8），這是手繪二維碼填格子理論基礎，不想深究可以直接跳過。同時數論基礎也是Hash演算法，RSA演算法等密碼學的入門基礎。 二維碼生成演算法最為核心的就是編碼規則和糾錯碼字的生成。本篇專...

摘要：本文講解二維碼糾錯碼字生成使用到的數學數論基礎知識，伽羅瓦域（Galois Field）GF（2^8），這是手繪二維碼填格子理論基礎，不想深究可以直接跳過。同時數論基礎也是Hash演算法，RSA演算法等密碼學的入門基礎。

二維碼生成演算法最為核心的就是編碼規則和糾錯碼字的生成。本篇專門講解糾錯涉及到的伽羅瓦域（Galois Field）。本文內容大部分是閱讀《密碼編碼學與網路安全》後參考相關PPT編寫，如有遺漏或不嚴謹地方請參考專業書籍。

數論基礎

整除，因數，素數

設 a , b(b≠0) 是兩個整數，如果存在另外一個整數 c 使得 a=b·c ,則稱 b 整除 a,記為 b|a,且稱 b 為 a 的因子。如果 p (p>1) 的因子只有 ±1，±p，稱整數 p 是素數。

模

如果 a 和 n(n≠0) 是兩個整數，則定義 a mod n 是 a 除以 n 所得的餘數。正整數 n 稱為模數。因此對於任意整數 a 可以寫出:

a = qn + r (0<=r

a = ⌊a/n⌋ * n + ( a mod n)

例子： a = 49,n = 8,則 q = 49 mod 8 = floor(49/8) = 6 , r = 49 mod 8 = 1

,49 = 6 * 8 + 1 .

最大公因數

最大公因數，也稱最大公約數、最大公因子，指兩個或多個整數共有因子中最大的一個。記為 gcd(a,b)。如果 gcd(a,b) = 1 ,則說 a,b 互素，記為 a⊥b。

Euclid 定理： 對任意非負整數 a 和正整數 b，有 gcd(a, b)=gcd(b, a-b)=gcd(b, a mod b)=gcd(a, b mod a) ,這也是常見的輾轉相除法的理論基礎。

示例：

gcd(18,12)= gcd(12,18-12) = gcd(12,6) = gcd(6,0) = 6

= gcd(12，18 mod 12) = gcd(12,6) = gcd(6,0) = 6

同餘

如果 (a mod n)=(b mod n)，則稱兩整數 a 和 b 模 n 同餘，記為 a ≡ b mod n。模 n 的剩餘類集合定義比 n 小的非負整數集合 Z(n)={0,1,2...,(n-1)}，更準確來說集合中每一個整數都代表一個剩餘類。我們將模 n 的剩餘類表示為 [0],[1],...[n-1],其中 [r] = {a:a 是一個整數，a ≡ n mod r}.

mod 在此處的含義表示a和b對於給定的模數有等價關係，和說（a- b）是 n 的整數倍一樣。

例子：49 mod 8 = 17 mod 8 = 1 ,則 49 ≡ 17 mod 8,等價於 8 | (49 - 17 ) = 8 | 32 顯然是成立的。

模運算

模運算的結果都限制在模的剩餘類裡面，運算封閉這是非常重要的一個性質。

• 交換律
  • (w+x) mod n=(x+w) mod n
  • (w×x) mod n=(x×w) mod n
• 結合律
  • [(w+x)+y] mod n=[w+(x+y)] mod n
  • [(w×x)×y] mod n=[w×(x×y)] mod n
• 分配律
  • [w×(x+y)] mod n=[w×x+w×y] mod n
• 單位元
  • (0+w) mod n=w mod n
  • (1×w) mod n=w mod n
• 加法逆元
  • 對 w∈Zn 存在z∈Zn，使得w+z≡0 mod n，記z=-w。
• 加法可約律
  • 如果 (a+b) ≡ (a+c) mod n，則 b≡c mod n
• 乘法可約律
  • 如果 (a×b) ≡ (a×c) mod n 且 a 有乘法逆元，那麼對 (a×b) ≡ (a×c) mod n 兩邊同乘以 -a，即得 b ≡ c mod n

下面的示例是計算Z(4)=｛0，1，2，3｝的模加法和模乘法

加法模運算 (a mod 4) + (b mod 4) = (a+b) mod 4

+	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

加法：對每一 x，都有一 y，使得 x+y ≡ 0 mod 4。如對 3，有 1，使得 3+1 ≡ 0 mod 4，稱 y 為 x 的負數，也稱為加法逆元。

---|---|---|---|---

0|0 | 0 | 0 | 0

1|0 | 1 | 2 | 3

2|0 | 2 | 0 | 2

3|0 | 3 | 2 | 1

乘法：對 x，若有 y，使得 x*y ≡ 1 mod 4，如3×3 ≡ 1 mod 4，則稱y為x的倒數，也稱為乘法逆元。

並非每一x都有乘法逆元。

定理：設 a∈Zn，gcd(a, n) = 1，則 a 在 Zn 中有乘法逆元。

上表中只有 a = 1,a = 3 滿足 gcd(a,4) = 1,從高亮結果可以看到定理的正確性。嚴格證明略。

擴充套件的歐幾里德演算法

演算法流程圖如下：預設a > b，否則根據性質可以調整過來

最常用的方法就是使用一個表格計算：

gcd(1759,550)= gcd(550,1759 mod 550) =gcd(550,109) = gcd(109,5) = 1

Q(整數部分)	X1	X2	X3	Y1	Y2	Y3
---	1	0	1759	0	1	550
1759/550=3	0	1	550	1-3*0=1	0-3*1=-3	109
550/109=5	1	-3	109	0-5*1=-5	1-5*(-3)=16	5
109/5=21	-5	16	5	1-21*(-5)=106	-3-21*16=-339	4
5/4=1	106	-339	4	-5-1*106= -111	16-1*(-339)= 355	1

直到 Y3 = 1 ,此時 有 d = Y3 = 1，x = Y1 = -111，y = Y2 = 355. 驗算如下： 1759 * (-111) + 550 * (355) = -195249 + 195250 = 1 .

域，群，環

伽羅瓦域定義

在數學中，有限域（英語：Finite field）或伽羅瓦域（英語：Galois field，為紀念埃瓦里斯特·伽羅瓦命名）是包含有限個元素的域。與其他域一樣，有限域是進行加減乘除運算都有定義並且滿足特定規則的集合。有限域最常見的例子是當 p 為素數時，整數對 p 取模。有限域的元素個數稱為它的序。

ofollow,noindex" target="_blank">這是維基百科的定義，需要請點選檢視更多內容 。

每個有限域的階必為素數的冪，即有限域的階可表示為 pⁿ（p 是素數，n 是正整數），記為 GF(pⁿ)。當 n = 1，GF(p) 就是 mod p，因為一個數 模p後，結果在 [0, p-1] 之間,有限域包含 p個元素。

下期將會討論具體的 GF(pⁿ) 編碼實現過程，敬請期待！

感興趣交流可以留言或關注我的公眾號。