摘要：本文讲解二维码纠错码字生成使用到的数学数论基础知识，伽罗瓦域（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 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，公众号名称：风之程序人生。查看更多最新内容。 公众号 作者：云是风的梦 出处：http://lijinfeng042.cnblogs.com/ 本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。https://www.cnblogs.com/lijinfeng042/p/9653088.html