CTF导航 CTF导航

密码学系列｜2.10 环、多项式环与有限域

密码学 2年前 (2022) admin
1,134 0 0

‍‍

2.10 Rings, Quotient Rings, Polynomial Rings, and Finite Fields

‍‍在本节中，我们将介绍抽象代数入门课程中通常会涉及的一些点。这些概念比我们之前讨论过的概念要复杂一些。对于密码学应用，本节最重要的点是具有素数幂阶的有限域理论，主要用于 6.7 和 6.8 小节中对椭圆曲线密码的学习；以及多项式环的商理论，主要用于 7.10一节中介绍的基于格的NTRU公钥密码系统。

  众所周知，群是数学许多领域中的基本结构。群  的本质就是一个集合和一个运算，它允许我们将两个元素以一定的规则获得第三个元素。而在数学中的另一个基本结构，称为环，是一个有两个运算的集合。这两种运算类似于普通的加法和乘法，它们由分配律联系在一起。在这一节中，我们首先简要讨论了环的一般理论，然后讨论了如何通过取商去根据一个环构造另一个环，最后我们详细研究了多项式环。

2.10.1 An Overview of the Theory of Rings

  其实我们已经熟悉了许多环，例如带有加法和乘法运算的整数环。接下来我们抽象出这些运算的基本性质，并用它们来表述以下基本定义。
定义: 环是具有两个运算的集合 ，我们分别设为 ，他们具有以下性质
的性质：
Identity Law 存在加法单位元为  满足对于任意的 ，有 
Inverse Law 对于每个元素 ，存在一个加法逆元 ，满足 
Associative Law 
Commutative Law 
  注意到，如果我们只关注  的  运算，那么这就是一个以 0 为（加法）单位元的交换群。
 的性质：
Identity Law 存在一个乘法单位元 ，满足 
Associative Law 
Commutative Law 
  注意到，如果我们只关注  的  运算，那么这几乎是一个以元素  为（乘法）单位元的交换群，除了 的元素不一定具有运算逆元。
 和  的联合性质
Distributive Law 
注 2.37：更一般地说，人们有时处理不包含乘法单位元的环，也处理  不可交换的环，即  可能不等于 。因此，形式上，我们这里描述的环实际上是具有（乘法）单位元的交换环。然而，我们这里使用的所有环都是这种类型的，所以我们就叫它们环。环的每个元素都有一个加法逆元，但可能有许多非零元素没有乘法逆元。例如，在整数 的环中，唯一具有乘法逆的元素是1和−1.
定义: 每一个非零元素都具有乘法逆元的（交换）环，我们称之为 域
例 2.38 下面给出一些我们都已经熟悉的环和域的例子
  1. ，  是乘法运算， 是加法运算，乘法单位元是 ，每一个非零元素都有乘法逆元，所以  是一个域
  2. ， 是乘法运算， 是加法运算，只有 具有乘法逆元，所以  是环，而不是域
  3. ， 为正整数， 是乘法运算， 是加法运算，乘法单位元是 ，这里  总是一个环，当且仅当  是一个素数，它是域。
  4. ， 为任意素数， 是乘法运算， 是加法运算，乘法单位元是 ，根据性质 ，每一个非零元素都有乘法逆元，因此  是一个域。
  5. 所有系数取自  的多项式的集合在通常的多项式加法和乘法运算下形成一个环，记作 ,

比如， 就是  环中的多项式， 也是如此，（虽然不是多。。。）
  1. 更一般地，如果  是一个环，我们可以从  中取系数构造一个多项式环。比如， 可能是  或者 。我们将在 7.9 一节讨论这些一般多项式环，记作 。

2.10.2 Divisibility and Quotient Rings

  在1.2一节中我们介绍了整除的概念，它也可以被推广到环。
定义 设  为环中的两个元素且 ，如果环中存在  满足

  我们  整除 ，或者称  被  整除，于之前一样，  整除  记作 ，否则记作 。
注 2.39 性质1.4中的关于整除性的基本性质都可以推广到环上， 上的证明都是用于环。类似的，对于任意不等于 0 的环 ，都有 ，见练习题2.30。然而，并不是所有的环都像 那么nice，比如，在有的环中，存在两个非零元素  满足 。如在  中，有 
  回顾一下，不存在非平凡因子的整数我们称之为素数。那么什么是平凡因式呢？我们可以“分解”任何一个整数  为 ，这就是平凡分解，之所以称之为“平凡”，是因为 1 和 -1 都有乘法逆元。一般来说，对于环 ，如果  是一个有乘法逆元  的元素那么我们可以把任意元素 分解为  。有乘法逆元的元素和只有平凡因子分解的元素是环内的特殊元素，所以我们给它们起了特殊的名字。
定义 设有环 ，若元素  有乘法逆元，即称之为 unit。即环内存在元素  满足 
注 2.40 整数的性质是，排列因子的顺序后每个整数都能够唯一地分解为素数的乘积。然而并非每个环都具有这种重要的唯一因式分解性质，但在下一节中，我们将证明具有域中系数的多项式环是具有唯一的因式分解。
  我们知道同余是处理整数的一个非常重要和强大的数学工具。利用整除的定义，我们可以将同余的概念推广到任意环
定义 设环 ，选取一个非零元素 ，若两个元素  的差被  整除，则我们称  同余，写作

  环的同余满足与整数相同的类等式性质
命题 2.41 设有环 ，随机选取非零元素 ，如果满足

那么有

证明留作练习题了，见练习 2.32。
注 2.42 我们对同余的定义涵盖了本书所需的所有性质。然而，我们必须注意到，以理想（ideals）作为模数的同余有更一般的概念。就我们的目的而言，使用模主理想（principal ideals）的同余就足够了，主理想是由单个元素生成的理想。
  命题2.41的一个重要作用是提供了一个是从旧环中创建新环的方法，就像我们通过模  的同余从  中创建一样。
定义 设有环 ，选取非零元素 ，对于任意元素 ，我们所以满足  的  集合记作 ，集合  称为  的同余类，我们将所有同余类的集合表示为  或者 ，因此

  对于同余类我们也可以进行加、乘

  我们称  为  关于  的商环(the quotient ring of R by m)，这个名字由下面的命题得来。
命题 2.43 上面关于同余类的式子给出了同余类  集合上加法和乘法运算规则的定义，使得  成为了一个环。
证明留作练习题了，见练习 2. 43。

2.10.3 Polynomial Rings and the Euclidean Algorithm

  在例2.38的6中，我们注意到，如果  是一个环，那么我们可以从  中获取系数来构成另一个环，记作

  非零多项式的度（degree）为  的最高幂次，因此，如果

  那么  的度为 ，记为 ，并且我们称  为  的首项系数（leading coefficient）。若非零对象是的首项系数为 1，则称为首一多项式，比如  是首一多项式，但是  就不是。
  尤其注意当  是域的情况，比如  是 （对于密码学来说，最后一种情况是比较常见且重要的）。其中之所以当  是  比较有用且重要，是因为在 1.2 一节中我们证明的  中的性质，同样适用于多项式环 ，在这一节中，我们将讨论  的一些性质。
  回顾一下高中学的，如何用一个多项式除以两一个多项式。下面给出一个例子， 除以 。

密码学系列｜2.10 环、多项式环与有限域


即， 除以  得到商  余 ，也可以写作

  注意到剩余多项式 的度是严格小于除式  的度的。
  只要有域 ，那么对于任意的多项式  都可以这么操作。这种具有“余数除法”的环也称为欧几里德环。
命题 2.44（环  是欧几里德环），设有域  ， 和  为  中的多项式，那么对  进行如下的表示

  其中，  为多项式，并且
  称： 除以  有商  和剩余 
证明：首先我们设存在某个任意值  满足  （比如，我们可以设 ）如果 ，那么算法结束。否则我们记

，其中 。我们重新表示等式  为

  注意到我们已经消去了  中幂次最高的那一项，所以 。如果 ，那么算法结束，否则继续这个步骤。每一次操作我们都能够减小 ，因此最终我们可以使得 
证毕。
  现在我们可以定义  下的公因式和最大公因式了。
定义  中的两个元素  的公因式是可以同时整除  的 ，当  的每一个因式都整除  时，我们称  为  的最大公因式。
  接下来我们将看到每一对  中的元素都拥有最大公因式，且是唯一的（除非乘以  中的另一个元素）。我们将最大首一公因式写作 
例子 2.45  的最大公因式是 ，因为

  所以  是一个公因式，至于是不是最大的，留给读者去检查了。
  目前尚不清楚，是否每一对元素都有一个最大公因式。但实际上，有许多环中不存在最大公因式，例如在环中。但当  是一个域时，多项式环  中确实存在最大公因式。
命题 2.46 （  下的欧几里德拓展算法）设域 ,  为   下的多项式 ，那么存在  的最大公因式 ，且存在公因式  满足

证明：同定理1.7的证明，多项式  可以通过反复应用命题 2.44，如下图。同样的，多项式  也可以由下图中的式子进行消元后计算得到，就如定理1.11的证明一般。

密码学系列｜2.10 环、多项式环与有限域

例 2.47 我们使用欧几里德算法计算在环  下的 

  所以  是最大公因式，为了得到一个首一多项式，我们给多项式乘以 ，得到

  回顾一下 2.10.2一节，我们称环中的元素  为 unit，如果其具有乘法逆元  的话。并且元素  是不可约的，当其不是一个 unit的时候，并且唯一分解  的方式 ，其中  有一个是 unit 。不难看出，多项式环  的 units 都是非零常数多项式，如  中的非零元素。见练习 2.34。
不可约性的问题则更为微妙，如下例所示。
例 2.48 多项式  在  下是不可约的，但是放在 ，其可以写为

  同样在  下也可以被分解，不过这次是分解为了一个二次多项式和一个三次多项式

  但是，在  下就是不可约的。
  作为素数的乘积，每个整数都有一个唯一的因式分解。域中有系数的多项式也是如此。和整数一样，证明唯一因式分解的关键是扩展欧几里德算法。
命题 2.49 如果有域 ，对于每一个非零多项式  都可以唯一的分解为首一不可约多项式的乘积。即如果  可以被分解为

  其中  是常数， 是首一不可约多项式。接下来我们打乱  的顺序。那么会满足

证明：如果   ，那么  （见练习2.34）,所以多项式都可以被分解为不可约多项式。至于唯一因式分解的证明可以参考整数相对应的那块，即定理 1.20。证明步骤的关键在于事实：如果  是不可约多项式且整除 ，那么 （或者两者都）。该事实其实是命题 1.19 的多项式类比，并且同样的，也是使用多项式版本的拓展欧几里得算法（命题 2.46）去证明。

2.10.4 Quotients of Polynomial Rings and Finite Fields of Prime Power Order

  在 2.10.3 中我们学习了多项式环，在2.10.2我们学习了商环，那么在这一节，我们将它们结合，考虑多项式环的商。
  回顾一下在我们处理模  的整数时，通常可以方便地用  到  之间的整数来表示模  的每个同余类。带余数除法算法（命题2.44）允许我们对多项式环的商做类似的事情。
命题 2.50 设有域 ，非零多项式  ，那么每个非零的同余类  都可以唯一的表示为 ，满足

证明：我们使用命题 2.44 去寻找多项式  满足

  其中，，或者 ，如果 ，那么 ，所以 。否则，模 后有 。因此  存在。现在证明  的唯一性，假设有  满足同样的性质，那么

  所以  整除 ，但是  的度时严格小于  的，所以 
证毕
例 2.51 考虑环 ，命题 2.50 表明这个商环中的每一个元素都可以被唯一的表示为

  有加法运算

  乘法运算也是比较简单，就是最后我们需要除以  然后取其剩余

  注意到，除以  取剩余，其实也可以简单的讲  替换成  就好。因此，在商环 中， 和  等价。注意到如果我们替换一下， ，那么  就是复数  的域。
  当  是域时，我们可以利用命题 2.50 计算多项式商环内元素的数量
推论 2.52 设有域 ，非零多项式  有度 ，那么商环  则有  个元素。
证明：根据命题2.50 我们知道， 中的每一个元素都可以唯一的表示为

  对于每个 ，都有  种可能，所以总共有  种可能。
证毕
  接下来我们给出一个多项式商环中 units 的重要性质，这允许我们构造出一个新的有限域。
命题 2.53 设有域 ，有多项式 。那么  为商环 中的一个unit，当前仅当

证明：首先假设  是  的一个 unit，根据定义，这意味着我们可以找到一个  满足 。用同余式的表示形式，即 。所以存在一个 ，满足

  这意味着，任何  的公因式也同时整除 ，因此 。
  接下来我们假设 ，那么根据命题 2.46，我们知道存在多项式  满足

  取模  后我们有

  所以  就是  在  下的逆元。
证毕
  当模为不可约多项式时就是命题 2.53 的一个重要实例。
推论 2.54 设有域 ，不可约多项式 ，那么商环  也是一个域，其中的每一个非零元素都有逆元。
证明：我们不妨设  是一个首一多项式，设 ，那么我们考虑两种情况。首先，假设 ，那么根据命题 2.53， 是一个 unit，得证。如果 ，那么我们有 ，但是  是首一且不可约，且 ，那么定有 。我们也知道 ，所以 ，因此在  下，  。因此  中的每一个元素都有乘法逆元。
例 2.55 多项式  在  不可约，所以商环  为一个域。事实上，这是复数域  ，  即为 ，因为在环  中，。
  作为对比，多项式  则显然不是  下的一个不可约多项式，所以商环  不是域，事实上，在 下，

  两个非零元素的乘积是 ，这意味着至少它们肯定不是 units。（环中乘积为 0 的非零元素也称为”零因子“（zero divisors））
  如果在推论 2.54 中我们应用 ，那么我们可以构造一个具有素数幂次个元素的域。
推论 2.56 设有限域 ， 为度  的不可约多项式，那么  是一个有   个元素的域。
例 2.57 不难验证多项式  是  中的不可约多项式（见练习2.37），所以  是一个有 8 个元素的域。由命题 2.50 可知，我们有以下8个元素

  加法简单，只需要记得系数模 2 就可以了

  乘法也是，正常将多项式相乘，然后除以 ，取剩余，比如

  所以  和  互为乘法逆元。 中完整的乘法表在练习 2.38中
例 2.58 在  中，什么时候多项式  是不可约的呢？如果它可约，那么就可以表示为

  根据系数，我们能够得出 ，所以

  换句话说，当域  中存在元素，其平方是 时。反过来说，如果  满足 ，那么 。
  这证明了：当前仅当  在  中不是二次剩余， 在  不可约。
  在 3.9 一节中我们将学到的二次互反定理给出：当前仅当 ， 在  不可约。
  设素数  满足 ，那么商域  是一个包含  元素的域。其包含元素  为 的二次根，所以我们可以把  看作是复数的类比。其中元素的形式也可以写作

  其中  是表示具有性质  的符号。其中的加减乘除也是可以类比复数的运算。不过系数不再是实数，而是模  下的整数。所以，除法通常是通过“分母有理化”来完成的，例如

  倒是不用担心说分母会是 0，因为 ，所以只要  有一个不是零元素，那么 。这样一个有阶  的域将会在 6.9.3 一节中用到。
  为了构建一个具有  元素的域，我们需要找到一个  中的度为  的不可约多项式，在更高级的书籍中已经证明，总是有这样一个多项式，实际上通常有很多这样的多项式。此外，在某种抽象意义上，我们选择哪个不可约多项式并不重要：我们总是得到相同的域（会同构）。然而，在实际意义上，还是有点区别，因为如果  没有很多非零系数，那么在  下的实际计算效率更高。我们在下面的定理中总结了有限域的一些主要性质。
定理 2.59 设有限域 
(a) 对于每个 ，存在一个度为  de 不可约多项式 
(b) 对于每个 ，存在包含有  个元素的有限域
(c) 如果  和  是拥有相同个数元素的有限域，那么存在一个方法将这两个域中的元素相联系，因此这两个域的加法和乘法表是一样的。（数学术语称  和  同构）
定义 我们记拥有  个元素的有限域为 。定理 2.59 说明至少会存在这样一个域，并且任意两个具有  个元素的域本质上是相同的，只不过具体到元素上是不一样的罢了。这样的域为了纪念十九世纪研究它们的法国数学家 Evariste Galois，也称为伽罗华域，记作 ，
注 2.60 不难证明，如果  是有限域，那么  则拥有   个元素（  为某个素数， ）证明需要用到线性代数，见练习 2.41。所以定理 2.59描述了所有有限域。
注 2.61 在密码学中，在  中运算，相比于选一个大素数  在  中运算要来的更高效些。这是因为计算机的二进制特性通常使它们在  中的计算更高效。第二个原因是，有时有限域包含较小的域是有利的。在的情况下，可以证明  是  （）的一个子域。当然，如果要使用  进行Diffie–Hellman密钥交换或Elgamal加密，则选择的  也需要与通常选择的  的大小大致相同。
  设有限域  有  个元素，其中的每一个非零元素都有逆元，那么 ( units 的集合) 有阶 ，根据拉格朗日定理（定理 2.13）有： 中的每一个元素的阶都整除 ，所以

  这是费马小定理（定理1.24）在任意有限域的推广。原根理论（定理 1.30）对于所有的有限域也都适用。
定理 2.62 设有限域  有  个元素，那么  有原根，即存在一个元素 ，满足

‍

‍‍‍


密码学系列｜2.10 环、多项式环与有限域

原文始发于微信公众号（山石网科安全技术研究院）：密码学系列｜2.10 环、多项式环与有限域

版权声明：admin 发表于 2022年5月24日 上午10:44。
转载请注明：密码学系列｜2.10 环、多项式环与有限域 | CTF导航

相关文章

密码学 ｜ 5.4 碰撞算法与中间相遇攻击
admin
409
5.2.2 针对维吉尼亚密码的密码分析：实践部分
admin
618
论文分享｜基于预言机的条件支付（NDSS 2023)
admin
27
G.O.S.S.I.P 阅读推荐 2024-02-19 密码学误用检测工具的误用？
admin
14
密码学基础之线性代数 Ⅰ
admin
139
一文探讨 Crypto 游戏的演变轨迹
admin
412

暂无评论

您必须登录才能参与评论！
立即登录
暂无评论...

相关文章

A quick post on Chen’s algorithm
0
RSA相关的趣味数学题(7)
0
DKG 协议的门限提升漏洞分析
0
G.O.S.S.I.P 阅读推荐 2024-02-19 密码学误用检测工具的误用？
0
再探格密码
0
成果分享|RRL：推荐系统逆向学习算法
0
密码学攻击之RSA：惊艳
0
椭圆曲线加密算法之Sony惨案模拟题的答案
0
椭圆曲线加密算法之Sony惨案模拟题
0
论文分享｜基于预言机的条件支付（NDSS 2023)
0