你也可以手绘二维码(二)纠错码字算法:数论基础及伽罗瓦域GF(2^8)

发布日期:2019-04-02

摘要:本文讲解二维码纠错码字生成使用到的数学数论基础知识,伽罗瓦域(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<n)q= ⌊a/n⌋

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

例子: a = 49n = 8则 q = 49 mod 8 = floor(49/8) = 6 r = 49 mod 8 = 149 = 6 * 8 + 1 .

最大公因数

最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有因子中最大的一个。记为 gcd(ab)。如果 gcd(ab) = 1 则说 ab 互素,记为 a⊥b。

Euclid 定理:对任意非负整数 a 和正整数 b,有 gcd(a b)=gcd(b a-b)=gcd(b a mod b)=gcd(a b mod a)这也是常见的辗转相除法的理论基础。

示例:

gcd(1812)= gcd(1218-12) = gcd(126) = gcd(60) = 6

= gcd(12,18 mod 12) = gcd(126) = gcd(60) = 6

同余

如果 (a mod n)=(b mod n),则称两整数 a 和 b 模 n 同余,记为 a ≡ b mod n。模 n 的剩余类集合定义比 n 小的非负整数集合 Z(n)={012...(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 | 31|1 | 2 | 3 | 02|2 | 3 | 0 | 13|3 | 0 | 1 | 2

加法:对每一 x,都有一 y,使得 x+y ≡ 0 mod 4。如对 3,有 1,使得 3+1 ≡ 0 mod 4,称 y 为 x 的负数,也称为加法逆元。

乘法模运算

(a mod 4) * (b mod 4) = (a*b) mod 4

*0123
00000
10123
20202
30321

乘法:对 x,若有 y,使得 x*y ≡ 1 mod 4,如3×3 ≡ 1 mod 4,则称y为x的倒数,也称为乘法逆元。并非每一x都有乘法逆元

定理:设 a∈Zn,gcd(a n) = 1,则 a 在 Zn 中有乘法逆元。

上表中只有 a = 1a = 3 满足 gcd(a4) = 1从高亮结果可以看到定理的正确性。严格证明略。

扩展的欧几里德算法

对于给定的整数 a 和 b ,扩展的欧几里德算法不仅能计算出最大公约数gcd(ab),还可以算出另外两个整数 x 和 y 满足方程 a*x + by = d = gcd(ab)。对于给定的 (ab) 如何计算(xyd)过程如下:(截图《自密码编码学与网络安全 原理与实践 第6版》 斯托林斯著)

算法流程图如下:默认a > b,否则根据性质可以调整过来

最常用的方法就是使用一个表格计算:gcd(1759550)= gcd(5501759 mod 550) =gcd(550109) = gcd(1095) = 1

Q(整数部分)X1X2X3Y1Y2Y3
---10175901550
1759/550=3015501-3*0=10-3*1=-3109
550/109=51-31090-5*1=-51-5*(-3)=165
109/5=21-51651-21*(-5)=106-3-21*16=-3394
5/4=1106-3394-5-1*106= -11116-1*(-339)=3551

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

域,群,环

具体就不展开了,感兴趣可以参考相关专业书籍,截图一张说明他们满足公理的关系


伽罗瓦域定义

在数学中,有限域(英语:Finite field)或伽罗瓦域(英语:Galois field,为纪念埃瓦里斯特·伽罗瓦命名)是包含有限个元素的域。与其他域一样,有限域是进行加减乘除运算都有定义并且满足特定规则的集合。有限域最常见的例子是当 p 为素数时,整数对 p 取模。有限域的元素个数称为它的序。

这是维基百科的定义,需要请点击查看更多内容。

每个有限域的阶必为素数的幂,即有限域的阶可表示为 pⁿ(p 是素数,n 是正整数),记为 GF(pⁿ)。当 n = 1,GF(p) 就是 mod p,因为一个数 模 p 后,结果在 [0 p-1] 之间有限域包含 p个元素。


下期将会讨论具体的 GF(pⁿ) 编码实现过程,敬请期待!

感兴趣交流可以留言,共同探讨学习,期望得到你的指正。你也可以关注公众号:ProgramLife042,公众号名称:风之程序人生。查看更多最新内容。