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 对于每个元素 ,存在一个加法逆元 ,满足
注意到,如果我们只关注 的 运算,那么这就是一个以 0 为(加法)单位元的交换群。
Identity Law 存在一个乘法单位元 ,满足
注意到,如果我们只关注 的 运算,那么这几乎是一个以元素 为(乘法)单位元的交换群,除了 的元素不一定具有运算逆元。
注 2.37:更一般地说,人们有时处理不包含乘法单位元的环,也处理 不可交换的环,即 可能不等于 。因此,形式上,我们这里描述的环实际上是具有(乘法)单位元的交换环。然而,我们这里使用的所有环都是这种类型的,所以我们就叫它们环。环的每个元素都有一个加法逆元,但可能有许多非零元素没有乘法逆元。例如,在整数 的环中,唯一具有乘法逆的元素是1和−1.
定义: 每一个非零元素都具有乘法逆元的(交换)环,我们称之为 域
例 2.38 下面给出一些我们都已经熟悉的环和域的例子
, 是乘法运算, 是加法运算,乘法单位元是 ,每一个非零元素都有乘法逆元,所以 是一个域
, 是乘法运算, 是加法运算,只有 具有乘法逆元,所以 是环,而不是域
, 为正整数, 是乘法运算, 是加法运算,乘法单位元是 ,这里 总是一个环,当且仅当 是一个素数,它是域。
? , 为任意素数, 是乘法运算, 是加法运算,乘法单位元是 ,根据性质 ,每一个非零元素都有乘法逆元,因此 ? 是一个域。
所有系数取自 的多项式的集合在通常的多项式加法和乘法运算下形成一个环,记作 ,
比如, 就是 环中的多项式, 也是如此,(虽然不是多。。。)
更一般地,如果 是一个环,我们可以从 中取系数构造一个多项式环。比如, 可能是 ? 或者 ? 。我们将在 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.42 我们对同余的定义涵盖了本书所需的所有性质。然而,我们必须注意到,以理想(ideals)作为模数的同余有更一般的概念。就我们的目的而言,使用模主理想(principal ideals)的同余就足够了,主理想是由单个元素生成的理想。
命题2.41的一个重要作用是提供了一个是从旧环中创建新环的方法,就像我们通过模 的同余从 中创建 一样。
定义 设有环 ,选取非零元素 ,对于任意元素 ,我们所以满足 的 集合记作 ,集合 称为 的同余类,我们将所有同余类的集合表示为 或者 ,因此
我们称 为 关于 的商环(the quotient ring of R by m),这个名字由下面的命题得来。
命题 2.43 上面关于同余类的式子给出了同余类 集合上加法和乘法运算规则的定义,使得 成为了一个环。
2.10.3 Polynomial Rings and the Euclidean Algorithm
在例2.38的6中,我们注意到,如果 是一个环,那么我们可以从 中获取系数来构成另一个环,记作
非零多项式的度(degree)为 的最高幂次,因此,如果
那么 的度为 ,记为 ,并且我们称 为 的首项系数(leading coefficient)。若非零对象是的首项系数为 1,则称为首一多项式,比如 是首一多项式,但是 就不是。
尤其注意当 是域的情况,比如 是 ? (对于密码学来说,最后一种情况是比较常见且重要的)。其中之所以当 是 比较有用且重要,是因为在 1.2 一节中我们证明的 中的性质,同样适用于多项式环 ,在这一节中,我们将讨论 的一些性质。
回顾一下高中学的,如何用一个多项式除以两一个多项式。下面给出一个例子, 除以 。
只要有域 ,那么对于任意的多项式 都可以这么操作。这种具有“余数除法”的环也称为欧几里德环。
命题 2.44 (环 是欧几里德环),设有域 , 和 为 中的多项式,那么对 进行如下的表示
证明:首先我们设存在某个任意值 满足 (比如,我们可以设 )如果 ,那么算法结束。否则我们记
注意到我们已经消去了 中幂次最高的那一项,所以 。如果 ,那么算法结束,否则继续这个步骤。每一次操作我们都能够减小 ,因此最终我们可以使得
定义 中的两个元素 的公因式是可以同时整除 的 ,当 的每一个因式都整除 时,我们称 为 的最大公因式。
接下来我们将看到每一对 中的元素都拥有最大公因式,且是唯一的(除非乘以 中的另一个元素)。我们将最大首一公因式写作
所以 是一个公因式,至于是不是最大的,留给读者去检查了。
目前尚不清楚,是否每一对元素都有一个最大公因式。但实际上,有许多环中不存在最大公因式,例如在环 中。但当 是一个域时,多项式环 中确实存在最大公因式。
命题 2.46 ( 下的欧几里德拓展算法)设域 , 为 下的多项式 ,那么存在 的最大公因式 ,且存在公因式 满足
证明:同定理1.7的证明,多项式 可以通过反复应用命题 2.44,如下图。同样的,多项式 也可以由下图中的式子进行消元后计算得到,就如定理1.11的证明一般。
例 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.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.38中
例 2.58 在 中,什么时候多项式 是不可约的呢?如果它可约,那么就可以表示为
换句话说,当域 中存在元素,其平方是 时。反过来说,如果 满足 ,那么 。
这证明了:当前仅当 在 中不是二次剩余, 在 不可约。
在 3.9 一节中我们将学到的二次互反定理给出:当前仅当 , 在 不可约。
设素数 满足 ,那么商域 是一个包含 元素的域。其包含元素 为 的二次根,所以我们可以把 看作是复数的类比。其中元素的形式也可以写作
其中 是表示具有性质 的符号。其中的加减乘除也是可以类比复数的运算。不过系数不再是实数,而是模 下的整数。所以,除法通常是通过“分母有理化”来完成的,例如
倒是不用担心说分母会是 0,因为 ,所以只要 有一个不是零元素,那么 。这样一个有阶 的域将会在 6.9.3 一节中用到。
为了构建一个具有 元素的域,我们需要找到一个 中的度为 的不可约多项式,在更高级的书籍中已经证明,总是有这样一个多项式,实际上通常有很多这样的多项式。此外,在某种抽象意义上,我们选择哪个不可约多项式并不重要:我们总是得到相同的域(会同构)。然而,在实际意义上,还是有点区别,因为如果 没有很多非零系数,那么在 下的实际计算效率更高。我们在下面的定理中总结了有限域的一些主要性质。
(a) 对于每个 ,存在一个度为 de 不可约多项式
(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 环、多项式环与有限域