1) transformations over finite fields
有限域上的映射
2) Base over finite fields
有限域上的基
4) ergodic matrix over finite field
有限域上的遍历矩阵
1.
The bases selected by both parties are hidden by making use of ergodic matrix over finite field.
通过利用有限域上的遍历矩阵对当事双方各自所选择的基进行隐藏,实现了交换操作。
5) polynomial equations over finite field
有限域上的多项式方程
6) polynomial over finite field
有限域上的多项式
补充资料：有限域
仅含有限多个元素的域。它首先由E.伽罗瓦所发现，因而又称为伽罗瓦域。它和有理数域、实数域比较，有着许多不同的性质。最简单的有限域是整数环Z 模一个素数p得到的商环Z/(p),由p个元素0,1,...,p-1组成,按模p相加和相乘。这p个元素的域简记为Fp，有如下性质：pα=0;，αp=α其中α、b∈Fp。Fp称为特征为p的素域,它与素数成一一对应。
任一有限域的特征是一素数。一个特征为素数 p的有限域F仍满足上述的第一、第二两条性质，F包含一个最小的子域,由单位元素e的一切倍数0,e,2e...,(p-1)e组成，它与Z/(p)同构。因此一个特征为p的有限域总是以特征为p的素域Fp作为子域。
特征p的有限域F也是Fp上一个有限维线性空间。设维数为n，F对Fp的一基为ε1,ε2,...,εn,则F由下列pn个元素组成：所以｜F｜=pn。F的乘法群F*=F-{0}是一个pn-1阶循环群，恰好是多项式的全部根。因此,F恰好由在Fp的代数闭包内的全部根组成。反之,任给一个素数p和一个正整数n，恒存在一个含pn个元素的有限域,它就是多项式在Fp上的分裂域。元素个数相同的任何两个有限域是同构的。因此,在同构意义下,对每个素数p和一个正整数n，存在一个而且只有一个含pn个元素的有限域，这个有限域记作GF(pn)。
顺便指出，J.H.M.韦德伯恩于1905年证明了"有限除环必是乘法交换的"。因此，有限除环就是现在所说的有限域。
对n的每个因子d,GF(pn)有一个而且只有一个含pd个元素的子域。因此,GF(pn)的子域和n的因子成一一对应。
有限域F=GF(pn)有一个弗罗贝尼乌斯自同构,有,对所有x∈F，当且仅当n|k,因而σ生成一个n阶循环群G，|G|=[F:Fp]。F/Fp是一个伽罗瓦扩张，G是它的群，对n的每个因子d,在伽罗瓦对应下，子群〈〉和它的不动域GF()成一一对应。
对于α∈F=GF(pn),规定：
,称为α从F到Fp的迹，在不致引起混淆的情况下,简记作Tr。Tr(x)是线性空间F/Fp上的一个线性函数,是加法群F到加法群Fp的一个满同态。
对α∈F，规定：，称为α从F到Fp的范数,可简记作N(α)。N是乘法群F*到F壩的一个满同态。
设??(x)是元素α∈F＝GF(pn)在Fp上的极小多项式，??(x)的次数称为α的次数,α的次数d等于[Fp(α):Fp],因而d│n。假设α≠0,则α的次数d和α在乘法群F*中的阶e有如下的关系:d是最小正整数,使得pd呏1(тode), 即α的次数等于pтode的指数。
若α(≠0)的阶等于pn-1,则α称为F的一个本原元素。它的极小多项式??(x)称为（n次）本原多项式。
设g(x)是Fp[x]中一个不可约多项式, 且g(x)≠x,若存在一个最小正整数r使得 xr呏1(modg(x))，则r称为g(x)的周期。一个非零的 α∈F的极小多项式??(x)的周期，等于α的阶。特别，一个n次本原多项式的周期等于pn-1。设一个不可约多项式g(x)(≠x)的周期为r,则g(x)k的周期等于rps，其中ps-1≤ps。
Fp[x]的一个m 次不可约多项式g(x)在GF(pn)内有根；；这三者是等价的。因此,Fp[x]中n次不可约多项式全是的因式,n次不可约多项式的个数为,其中μ(d)是麦比乌斯函数。用表示Fp上全部n次不可约多项式(首项系数为1)的积，于是。n次本原多项式的个数为，其中φ(m)为欧拉函数。
Fp上一个多项式??(x)（次数n≥1）的分解对现代通信有很重要的关系。在理论上它和商环R=Fp[x]/(??(x))的代数结构又密切相关。令，则V有如下的性质。
① Fp嶅V嶅R，V为R的一个子环而且半单,因而V是一些与Fp同构的子域的直和,i=1,2,...,g;g等于V作为Fp上线性空间的维数，g也是??(x)在Fp上相异的不可约因式的个数。的单位元素ei(i=1,2,...,g),构成R的互相正交的本原幂等元而且。
② 令，则 Pi(x)为一个不可约多项式的方幂,,而且·。pj(x)称为??(x)的准素因式。
为了给出分解??(x)的实际的计算法，还有如下性质。
③ R有一个F自同构π：π(g(x))=g(x)p，g(x)∈R，则V就是属于π的特征值1的全部特征向量和0构成的特征子空间。于是有:a.设η∈V,g(x)为??(x)的一个因式,如果g(x)凲η-i,i=0,1,...,p-1,则为一个非平凡的分解，而且这个条件也是必要的。上面的乘积中出现的因式两两互素。b.设η1,η2,...,ηg为V对Fp的一基，则g(x)为一个不可约多项式的方幂，其充分必要条件是每个ηi与Fp中一个元素modg(x)同余。
分解??(x)的步骤大致如下:不妨设η1=1。用η2按a.分解??(x),得到的因式记为??1(x),??2(x),...,??r(x),r≤g-1，每个??i(x)按b.进行检验，如果??i(x)含有两个或两个以上不同素因式，则存在一个ηj,j>2，使得??i(x)和ηj满足a.中的条件，用ηj对??i(x)进行分解, 如此进行下去,经有限步后,即得到??(x)的全部准素因式pi(x)，i=1,2,...,g,而pi(x)的分解是容易的。至于V的求得,则是属于线性方程组的问题。
判定一个n次多项式??(x)是否是本原的,还没有一般的方法，只有用试算的办法去计算具体的??(x)的周期之后才能作出判断。F2上 168次以下的三项或五项的本原多项式（每个次数给出一个）已经有表可查。计算出全部F上n次不可约多项式大致有两种途径,一是直接分解第2n-1个分圆多项式，一是筛法,它正如求有理素数的筛法一样。F2上16次以下的全部不可约多项式和17～34次具有各种周期的不可约多项式有表可查。
令R表示由有限域 F上的形式幂级数组成的环。??可逆的充分必要条件是α0≠0。如果存在一个正整数l使得,那么??就称为循环的。若??是循环的,则最小的l就称为??的周期。全部循环幂级数构成R的一个子环,记作C。R中所有形如h(x)/g(x)的真分式构成R的一个子环，记作B,这里h(x)和g(x)是F[x]中的多项式, h(x)的次数小于g(x)的次数,且g(0)≠0。可以证明,C=B。因此,B与C的关系正如正的真分数（分母与10互素）与循环小数的关系一样。有限域在现代通信（例如编码）、组合数学（例如有限几何、区组设计、差集合、正交拉丁方）以及正交试验设计等各方面，有广泛的应用。
仅以线性反馈移位寄存器序列（以下简称线性移存器序列）为例，叙述如下。有限域F上一个非退化n位线性移存器序列,从一个非零初态x0，x1,...，xn-1出发产生一个输出序列, 称之为一个n位线性移存器序列，它在 t时刻的输出xt是它前 n个时刻的输出的线性函数 ，式中b)j∈F，是与时刻 t无关的常数。这个n位非退化线性移存器的功能由上述递推关系所刻画。将输出序列表成幂级数,此时x相当于移存器中的迟延算子。令,则α(x)·g(x)为一个次数不大于(n-1)的多项式，记为h(x)，于是α(x)=h(x)/g(x)，因而α(x)是一个循环级数，α(x)的周期等于g(x)/d(x)的周期，其中d(x)=(g(x),h(X))。若g(x)是可约的,则α(x) 的周期还依赖于所给的初态。若 g(x)是不可约的，从任一非零初态出发得到的α(x)有同一周期，即g(x)的周期。反之，任给一个n次多项式g(x)，且g(0)=1,则可以造出一个非退化 n位线性反馈移存器序列使得它的功能由g(x)所确定。
应用n次本原多项式可以造出周期最长的n位线性反馈移存器序列。
参考书目
L.Dickson,Linear Algebraic Groups, with an Exposition of the Galois Field Theory, Dover,NewYork, 1958.
A.Albert,Fundamental Concepts of Higher Algebra, Univ. of Chicago Press, Chicago, 1956.
任一有限域的特征是一素数。一个特征为素数 p的有限域F仍满足上述的第一、第二两条性质，F包含一个最小的子域,由单位元素e的一切倍数0,e,2e...,(p-1)e组成，它与Z/(p)同构。因此一个特征为p的有限域总是以特征为p的素域Fp作为子域。
特征p的有限域F也是Fp上一个有限维线性空间。设维数为n，F对Fp的一基为ε1,ε2,...,εn,则F由下列pn个元素组成：所以｜F｜=pn。F的乘法群F*=F-{0}是一个pn-1阶循环群，恰好是多项式的全部根。因此,F恰好由在Fp的代数闭包内的全部根组成。反之,任给一个素数p和一个正整数n，恒存在一个含pn个元素的有限域,它就是多项式在Fp上的分裂域。元素个数相同的任何两个有限域是同构的。因此,在同构意义下,对每个素数p和一个正整数n，存在一个而且只有一个含pn个元素的有限域，这个有限域记作GF(pn)。
顺便指出，J.H.M.韦德伯恩于1905年证明了"有限除环必是乘法交换的"。因此，有限除环就是现在所说的有限域。
对n的每个因子d,GF(pn)有一个而且只有一个含pd个元素的子域。因此,GF(pn)的子域和n的因子成一一对应。
有限域F=GF(pn)有一个弗罗贝尼乌斯自同构,有,对所有x∈F，当且仅当n|k,因而σ生成一个n阶循环群G，|G|=[F:Fp]。F/Fp是一个伽罗瓦扩张，G是它的群，对n的每个因子d,在伽罗瓦对应下，子群〈〉和它的不动域GF()成一一对应。
对于α∈F=GF(pn),规定：
,称为α从F到Fp的迹，在不致引起混淆的情况下,简记作Tr。Tr(x)是线性空间F/Fp上的一个线性函数,是加法群F到加法群Fp的一个满同态。
对α∈F，规定：，称为α从F到Fp的范数,可简记作N(α)。N是乘法群F*到F壩的一个满同态。
设??(x)是元素α∈F＝GF(pn)在Fp上的极小多项式，??(x)的次数称为α的次数,α的次数d等于[Fp(α):Fp],因而d│n。假设α≠0,则α的次数d和α在乘法群F*中的阶e有如下的关系:d是最小正整数,使得pd呏1(тode), 即α的次数等于pтode的指数。
若α(≠0)的阶等于pn-1,则α称为F的一个本原元素。它的极小多项式??(x)称为（n次）本原多项式。
设g(x)是Fp[x]中一个不可约多项式, 且g(x)≠x,若存在一个最小正整数r使得 xr呏1(modg(x))，则r称为g(x)的周期。一个非零的 α∈F的极小多项式??(x)的周期，等于α的阶。特别，一个n次本原多项式的周期等于pn-1。设一个不可约多项式g(x)(≠x)的周期为r,则g(x)k的周期等于rps，其中ps-1
Fp[x]的一个m 次不可约多项式g(x)在GF(pn)内有根；；这三者是等价的。因此,Fp[x]中n次不可约多项式全是的因式,n次不可约多项式的个数为,其中μ(d)是麦比乌斯函数。用表示Fp上全部n次不可约多项式(首项系数为1)的积，于是。n次本原多项式的个数为，其中φ(m)为欧拉函数。
Fp上一个多项式??(x)（次数n≥1）的分解对现代通信有很重要的关系。在理论上它和商环R=Fp[x]/(??(x))的代数结构又密切相关。令，则V有如下的性质。
① Fp嶅V嶅R，V为R的一个子环而且半单,因而V是一些与Fp同构的子域的直和,i=1,2,...,g;g等于V作为Fp上线性空间的维数，g也是??(x)在Fp上相异的不可约因式的个数。的单位元素ei(i=1,2,...,g),构成R的互相正交的本原幂等元而且。
② 令，则 Pi(x)为一个不可约多项式的方幂,,而且·。pj(x)称为??(x)的准素因式。
为了给出分解??(x)的实际的计算法，还有如下性质。
③ R有一个F自同构π：π(g(x))=g(x)p，g(x)∈R，则V就是属于π的特征值1的全部特征向量和0构成的特征子空间。于是有:a.设η∈V,g(x)为??(x)的一个因式,如果g(x)凲η-i,i=0,1,...,p-1,则为一个非平凡的分解，而且这个条件也是必要的。上面的乘积中出现的因式两两互素。b.设η1,η2,...,ηg为V对Fp的一基，则g(x)为一个不可约多项式的方幂，其充分必要条件是每个ηi与Fp中一个元素modg(x)同余。
分解??(x)的步骤大致如下:不妨设η1=1。用η2按a.分解??(x),得到的因式记为??1(x),??2(x),...,??r(x),r≤g-1，每个??i(x)按b.进行检验，如果??i(x)含有两个或两个以上不同素因式，则存在一个ηj,j>2，使得??i(x)和ηj满足a.中的条件，用ηj对??i(x)进行分解, 如此进行下去,经有限步后,即得到??(x)的全部准素因式pi(x)，i=1,2,...,g,而pi(x)的分解是容易的。至于V的求得,则是属于线性方程组的问题。
判定一个n次多项式??(x)是否是本原的,还没有一般的方法，只有用试算的办法去计算具体的??(x)的周期之后才能作出判断。F2上 168次以下的三项或五项的本原多项式（每个次数给出一个）已经有表可查。计算出全部F上n次不可约多项式大致有两种途径,一是直接分解第2n-1个分圆多项式，一是筛法,它正如求有理素数的筛法一样。F2上16次以下的全部不可约多项式和17～34次具有各种周期的不可约多项式有表可查。
令R表示由有限域 F上的形式幂级数组成的环。??可逆的充分必要条件是α0≠0。如果存在一个正整数l使得,那么??就称为循环的。若??是循环的,则最小的l就称为??的周期。全部循环幂级数构成R的一个子环,记作C。R中所有形如h(x)/g(x)的真分式构成R的一个子环，记作B,这里h(x)和g(x)是F[x]中的多项式, h(x)的次数小于g(x)的次数,且g(0)≠0。可以证明,C=B。因此,B与C的关系正如正的真分数（分母与10互素）与循环小数的关系一样。有限域在现代通信（例如编码）、组合数学（例如有限几何、区组设计、差集合、正交拉丁方）以及正交试验设计等各方面，有广泛的应用。
仅以线性反馈移位寄存器序列（以下简称线性移存器序列）为例，叙述如下。有限域F上一个非退化n位线性移存器序列,从一个非零初态x0，x1,...，xn-1出发产生一个输出序列, 称之为一个n位线性移存器序列，它在 t时刻的输出xt是它前 n个时刻的输出的线性函数 ，式中b)j∈F，是与时刻 t无关的常数。这个n位非退化线性移存器的功能由上述递推关系所刻画。将输出序列表成幂级数,此时x相当于移存器中的迟延算子。令,则α(x)·g(x)为一个次数不大于(n-1)的多项式，记为h(x)，于是α(x)=h(x)/g(x)，因而α(x)是一个循环级数，α(x)的周期等于g(x)/d(x)的周期，其中d(x)=(g(x),h(X))。若g(x)是可约的,则α(x) 的周期还依赖于所给的初态。若 g(x)是不可约的，从任一非零初态出发得到的α(x)有同一周期，即g(x)的周期。反之，任给一个n次多项式g(x)，且g(0)=1,则可以造出一个非退化 n位线性反馈移存器序列使得它的功能由g(x)所确定。
应用n次本原多项式可以造出周期最长的n位线性反馈移存器序列。
参考书目
L.Dickson,Linear Algebraic Groups, with an Exposition of the Galois Field Theory, Dover,NewYork, 1958.
A.Albert,Fundamental Concepts of Higher Algebra, Univ. of Chicago Press, Chicago, 1956.
说明：补充资料仅用于学习参考，请勿用于其它任何用途。
参考词条