扩域上(Galois域)的计算及其实现

有限域 FFF 的特征为素数 ppp; 它可以视作素域 Zp\mathbb{Z}_pZp​ 上的 n(n<∞)n(n<\infty)n(n<∞) 维线性空间, 从而 ∣F∣=pn|F|=p^n∣F∣=pn; FFF 的加法群可视作 nnn 个 ppp 阶循环群的直和; 其乘法群是 pn−1p^n-1pn−1 阶循环群, 从而 FFF 是 Zp\mathbb{Z}_pZp​ 的单扩域 Zp(u)\mathbb{Z}_p(u)Zp​(u), 其中 uuu 是 Zp\mathbb{Z}_pZp​ 上的 nnn 次代数元; FFF 恰是多项式 xpn−x∈Zp[x]x^{p^n}-x \in \mathbb{Z}_p[x]xpn−x∈Zp​[x] 的 pnp^npn 个根作成的集合, 又恰为 xpn−x∈Zp[x]x^{p^n}-x \in \mathbb{Z}_p[x]xpn−x∈Zp​[x] 在 Zp\mathbb{Z}_pZp​ 上的分裂域; 从而 pnp^npn 元域总存在, 且在同构意义下唯一. pnp^npn 元域 FFF 的自同构群恰为 Galois 群 Gal⁡(F/Zp)\operatorname{Gal}\left(F / \mathbb{Z}_p\right)Gal(F/Zp​) : 它是由 Frobenius 自同构 a↦apa \mapsto a^pa↦ap 生成的 nnn 阶循环群.虽然这样的域在近世代数的学习中已然是老生常谈,但是今天我们会给出它的c++计算实现.

扩域上的计算

密码学中通常会考虑F2\mathbb{F}_{2}F2​上及对应多项式环上的计算,这是由计算机的二进制基础决定的,但是随着加密解密方法的进展,很多加密协议及分析中会考虑很多扩域的计算,在本文中我们希望能实现Fpn\mathbb{F}_{p^n}Fpn​上的计算.

例:假设计算F24\mathbb{F}_{2^4}F24​上的元素,根据F24≅F2/f(x)\mathbb{F}_{2^4} \cong \mathbb{F}_{2}/f(x)F24​≅F2​/f(x),这里设f(x)=x4+x3+1f(x) = x^4+x^3+1f(x)=x4+x3+1为不可约多项式;F24\mathbb{F}_{2^4}F24​中洽有161616个元素吗,F2/f(x)\mathbb{F}_{2}/f(x)F2​/f(x)中的元素可以表示为小于444次的多项式,根据每一项出现与否({x3,x2,x,1}\{x^3,x^2,x,1\}{x3,x2,x,1})也恰有16个多项式,那么和F24\mathbb{F}_{2^4}F24​中的元素一一对应,因此F24\mathbb{F}_{2^4}F24​亦可表示为:

F24={0000,0001,...,1111}\mathbb{F}_{2^4} = \{0000,0001,...,1111\}F24​={0000,0001,...,1111}

我们的程序设计要用到我之前博客提到的GiNaC库,一个C++符号计算库,首先我们设计扩域和扩域元素的数据结构:

struct extension_field
{int PRIME_NUM;int EXTEN_NUM;GiNaC::ex IRRED_POLY;
};class extension_field_element
{
public:extension_field* pt_EXT_FIELD;int ELEMENT_INDEX;string SYMBOL;GiNaC::ex POLYNOMIAL;extension_field_element(extension_field* pt_EXT_FIELD,const GiNaC::ex& POLYNOMIAL);extension_field_element operator+(const extension_field_element& EXT_FIELD_ELE_OPS) const;extension_field_element operator*(const extension_field_element& EXT_FIELD_ELE_OPS) const;
};

扩域中元素的加法和乘法简单说就是取模的加法乘法,下面看算例:仍考虑计算F24\mathbb{F}_{2^4}F24​上的元素,根据F24≅F2/f(x)\mathbb{F}_{2^4} \cong \mathbb{F}_{2}/f(x)F24​≅F2​/f(x),这里设f(x)=x4+x3+1f(x) = x^4+x^3+1f(x)=x4+x3+1为我们选取的不可约多项式(要求选取的不可约多项式是本原多项式,至于怎么找本原多项式这里不赘述,请参考[2]);那么取:

(x3+x2+1)=f1(x),(x3+x+1)=f2(x)(x^3+x^2+1)=f_1(x),(x^3+x+1)=f_2(x)(x3+x2+1)=f1​(x),(x3+x+1)=f2​(x)

那么加法的实现(2=0mod2)(2=0 \bmod 2)(2=0mod2):

f1(x)+f2(x)=(x3+x2+1)+(x3+x+1)=2x3+x2+x+2=x2+x\begin{aligned} & f_1(x)+f_2(x) \\ = &(x^3+x^2+1)+(x^3+x+1) \\ = & 2 x^3+x^2+x+2=x^2+x \end{aligned} ==​f1​(x)+f2​(x)(x3+x2+1)+(x3+x+1)2x3+x2+x+2=x2+x​

乘法的实现:
f1(x)⋅f2(x)=(x3+x2+1)(x3+x+1)=x6+x5+x4+x3+x3+x3+x2+x+1=x6+x5+x4+x3+x2+x+1\begin{aligned} f_1(x) \cdot f_2(x) & =(x^3+x^2+1)(x^3+x+1) \\ & =x^6+x^5+x^4+x^3+x^3+x^3+x^2+x+1 \\ & =x^6+x^5+x^4+x^3+x^2+x+1 \end{aligned} f1​(x)⋅f2​(x)​=(x3+x2+1)(x3+x+1)=x6+x5+x4+x3+x3+x3+x2+x+1=x6+x5+x4+x3+x2+x+1​

又由f(x)=x4+x3+1f(x)=x^4+x^3+1f(x)=x4+x3+1,那么消去x6x^6x6也就是x6=x2⋅f(x)−x5−x2x^6=x^2 \cdot f(x)-x^5-x^2x6=x2⋅f(x)−x5−x2得:

f1(x)⋅f2(x)=x2⋅f(x)+f(x)+x≡xmodf(x)f_1(x) \cdot f_2(x) = x^2 \cdot f(x)+f(x)+x \equiv x \bmod f(x)f1​(x)⋅f2​(x)=x2⋅f(x)+f(x)+x≡xmodf(x)

因而得到F24\mathbb{F}_{2^4}F24​上f1(x)⋅f2(x)=xf_1(x) \cdot f_2(x) = xf1​(x)⋅f2​(x)=x;在计算过程中我们会用到模不可约多项式f(x)f(x)f(x)也就是拟除f(x)f(x)f(x)的过程,以下是拟除的实现方法,其中包含了多项式系数模ppp的函数(略):

GiNaC::ex pseudo_divide(const GiNaC::ex& POLYNOMIAL, const GiNaC::ex& POLYNOMIAL_DIV, const int& PRIME_NUM)
{GiNaC::ex POLYNOMIAL_RES = POLYNOMIAL;int DIS_DEG;GiNaC::ex COEFF_LEAD;while(POLYNOMIAL_RES.degree(a)>=POLYNOMIAL_DIV.degree(a)){DIS_DEG = POLYNOMIAL_RES.degree(a) - POLYNOMIAL_DIV.degree(a);COEFF_LEAD = POLYNOMIAL_RES.coeff(a,POLYNOMIAL_RES.degree(a));POLYNOMIAL_RES = coeff_mod(POLYNOMIAL_RES - (COEFF_LEAD*POLYNOMIAL_DIV*GiNaC::pow(a, DIS_DEG)).expand(), PRIME_NUM);}return POLYNOMIAL_RES;
}

扩域上的加法很简单,在此亦不赘述,下面是乘法的实现:

extension_field_element extension_field_element::operator*(const extension_field_element& EXT_FIELD_ELE_OPS) const
{GiNaC::ex POLYNOMIAL_RES=0;extension_field_element EXT_FIELD_ELE_RES(this->pt_EXT_FIELD,POLYNOMIAL_RES);if(this->pt_EXT_FIELD != EXT_FIELD_ELE_OPS.pt_EXT_FIELD){return EXT_FIELD_ELE_RES;}EXT_FIELD_ELE_RES.POLYNOMIAL = pseudo_divide((this->POLYNOMIAL*EXT_FIELD_ELE_OPS.POLYNOMIAL).expand(),this->pt_EXT_FIELD->IRRED_POLY,this->pt_EXT_FIELD->PRIME_NUM);return EXT_FIELD_ELE_RES;
}

扩域上的多项式环

假设考虑Fpn\mathbb{F}_{p^n}Fpn​上的元素,根据Fpn≅Fp/f(x)\mathbb{F}_{p^n} \cong \mathbb{F}_{p}/f(x)Fpn​≅Fp​/f(x),这里设f(x)f(x)f(x)是一模ppp的nnn阶不可约多项式;现在考虑多项式环Fpn[x1,⋯,xm]\mathbb{F}_{p^n}[x_1,\cdots,x_m]Fpn​[x1​,⋯,xm​]的计算,其中的多项式g(x)g(x)g(x)形如:

g(x)∈{∑ifiMi∣fi∈Fp/f(x),Mi=x1αi...xnαn}g(x) \in \{\sum_i f_{i}M_i |f_i \in \mathbb{F}_{p}/f(x),M_i = x^{\alpha_i}_1...x^{\alpha_n}_n\}g(x)∈{i∑​fi​Mi​∣fi​∈Fp​/f(x),Mi​=x1αi​​...xnαn​​}

事实上若限定xjx_jxj​的取值也在Fp/f(x)\mathbb{F}_{p}/f(x)Fp​/f(x)上面,是小于nnn阶的含xxx的模ppp多项式;我们现在考虑有没有什么规则可以利用来化简MiM_iMi​来防止阶数爆炸;

事实上,xjx_jxj​作为Fpn\mathbb{F}_{p^n}Fpn​上的元素,Fpn∖0\mathbb{F}_{p^n}\setminus 0Fpn​∖0构成一个pn−1p^n-1pn−1阶循环群,其阶只可能是pn−1p^n-1pn−1的因数(例:F32\mathbb{F}_{3^2}F32​上的元素的阶只可能是1,2,4,81,2,4,81,2,4,8),综上所述,只能断言xjpn=xjx^{p^n}_j=x_jxjpn​=xj​.下面我们用程序F34\mathbb{F}_{3^4}F34​中某元素ggg的阶=8=8=8,是34−1=803^4-1=8034−1=80的因数:

g^1 = 1+a+2*a^2
g^2 = 2*a+a^2
g^3 = 1+2*a+a^2
g^4 = 2
g^5 = 2+2*a+4*a^2
g^6 = a+2*a^2
g^7 = 2+a+2*a^2
g^8 = 1
g^9 = 1+a+2*a^2

一个额外的思考(😉):若我们需要求解多项式环Fpn[x1,⋯,xm]\mathbb{F}_{p^n}[x_1,\cdots,x_m]Fpn​[x1​,⋯,xm​]上的方程组,那么带着系数算来算去复杂度太高,不由得想到了动态规划,也就是先计算Fpn\mathbb{F}_{p^n}Fpn​上的加法乘法表T\mathcal{T}T,则我们可以查表得到T(gi,gj,+)=gk\mathcal{T}(g_i,g_j,+)=g_kT(gi​,gj​,+)=gk​和T(gi,gj,×)=gl\mathcal{T}(g_i,g_j,\times)=g_lT(gi​,gj​,×)=gl​来获得加法乘法结果,那多项式环Fpn[x1,⋯,xm]\mathbb{F}_{p^n}[x_1,\cdots,x_m]Fpn​[x1​,⋯,xm​]的多项式g(x)g(x)g(x)形如:

g(x)∈{∑igiMi∣gi∈Fpn,Mi=x1αi...xnαn}g(x) \in \{\sum_i g_{i}M_i |g_i \in \mathbb{F}_{p^n},M_i = x^{\alpha_i}_1...x^{\alpha_n}_n\}g(x)∈{i∑​gi​Mi​∣gi​∈Fpn​,Mi​=x1αi​​...xnαn​​}

计算一下子从多项式计算简化为纯符号计算,此时系数是纯符号的,我们只需要专心处理变元的计算结果即可,这也是下一步程序设计的工作.

参考资料

[1] Modern abstract algebra, Anderson, M. and Feil, T.,2014.
[2] 应用近世代数(第三版),胡冠章,清华大学出版社.