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

admin 2018-09-16 阅读


摘要:本文讲解二维码纠错码字生成使用到的数学数论基础知识,伽罗瓦域(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 = 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 的负数,也称为加法逆元。

乘法模运算 (a mod 4) * (b mod 4) = (a*b) mod 4

* 0 1 2 3
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(a,b),还可以算出另外两个整数 x 和 y 满足方程 a*x + by = d = gcd(a,b)。对于给定的 (a,b) 如何计算(x,y,d),过程如下:(截图《自密码编码学与网络安全 原理与实践 第6版》 ,斯托林斯著)
计算步骤,关注公众号:ProgramLife042,公众号名称:风之程序人生

算法流程图如下:默认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 .

域,群,环

具体就不展开了,感兴趣可以参考相关专业书籍,截图一张说明他们满足公理的关系
域,群,环,关注公众号:ProgramLife042,公众号名称:风之程序人生


伽罗瓦域定义

在数学中,有限域(英语: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,公众号名称:风之程序人生。查看更多最新内容。
公众号

来源:未知

声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。