橢圓曲線系統常采用算數運算操作執行一系列加解密操作，掌握有限域的算數運算方法，對設計高效執行的密碼學算法至關重要。本文介紹了有限域的基本概念，進一步闡述了橢圓曲線系統的三種經典有限域（質數域，二元域和擴展域）以及其相應的算數運算方法(加法，減法，乘法和求逆運算)。

有限域介紹

數據域是相似數據系統（如有理數，實數和復雜數）及其屬性的抽象概念。數據域可構成數據集合$F$，并執行兩類基本運算：加法和乘法，一般滿足如下性質：
（1）$(F,+)$是一個阿貝爾群，具有（加法）單位元0；
（2）$(F\backslash \{0\},?)$是一個阿貝爾群，具有（乘法）單位元1；
（3）分配律：對所有 $a,b,c\in F$，滿足：
$(a+b)?c=a?c+b?c$。
如果集合$F$是有限的， 數據域也是有限的，稱$F$為有限域。

數據域操作

如上節所述，數據域$F$具有兩種類型操作，加法和乘法。依此類推，域元素的減法可按照加法定義，即對于$a,b\in F$, $a?b=a+(?b)$，其中$?b$在有限域$F$中唯一，且滿足$b+(?b)=0$，則$?b$稱為b的負數。相應的，數據域的除法可按照乘法定義，即對于$a,b\in F$,且$b=0$，滿足$a/b=a?b^{?1}$，其中$b^{?1}$在有限域$F$中唯一， 且滿足$b?b^{?1}=1$，則稱$b^{?1}是b的逆元$。

存在性和唯一性

在有限域中，階指有限域的元素數量。稱有限域F具有階q，當且僅當q可以表示為質數的指數形式，也就是 $q=p^m$，其中質數p稱為F的特征，m是正整數。如果$m=1$,稱$F$為質數域。如果$m\ge 2$，稱$F$為擴展域。對具有任意質數冪的階q，僅僅存在一個有限域。 也就是說，任意兩個具有相同階q的有限域，盡管形式上其標識有可能不同，但卻具有相同在形態。基于該性質，稱任2個具有相同階（假設階為q）的有限域具有同態性，其同態域表示為$F_q$。

質數域

設p為質數，對整數取模p，就生成一個由元素$0,1,2,...,p?1$構成的整數集合，這個集合構成階為p的有限域，表示為$F_p$，其中p為$F_p$的模數。對任意整數a，$a\mathrm{m}\mathrm{o}\mathrm{d}p$ 應表示余數r，且取值唯一，滿足$0\le r\le p?1$。這個運算與$a/p$等價，也稱為約化模$p$。

舉個栗子，有限域$F_{29}$的元素集合為{0，1，2，…，28}。以下為一些算數運算的例子：
1 加法： $17+20=8$ ，因為 $37\mathrm{m}\mathrm{o}\mathrm{d}29=8$
2 減法： $17?20=26$，因為 $?3\mathrm{m}\mathrm{o}\mathrm{d}29=26$
3 乘法： $17?20=21$，因為 $340\mathrm{m}\mathrm{o}\mathrm{d}29=21$
4 求逆： $17^{?1}=12$，因為 $17?12\mathrm{m}\mathrm{o}\mathrm{d}29=1$

二元域

階為$2^m$的有限域稱為二元域或特征為2的有限域。一種構造$F_{2^m}$的方式是采用多項式的基本表示方法。以下是有域$F_{2^m}$表示為二元多項式的例子（多項式的系數在數據域$F_2=0,1$中），其度不超過為m-1。

我們選取一個具有項數m的不可約的二元多項式$f(z)$（對任意m，這個多項式都是存在的）。$f(z)$具有的不可約性意味著$f(z)$不能被分解為（小于m）次冪的二元多項式的乘積。多項式系數值通常表示為的多項式加法后，對結果用2取模；多項式系數的乘法表示為執行約化多項式（reduction polynomial）$f(z)$的模。對任意二元多項式$a(z)$，$a(z)\mathrm{m}\mathrm{o}\mathrm{d}f(z)$表示執行$a(z)$除以$f(z)$的冪小于m的余數多項式$r(z)$，這個操作稱為約化模$f(z)$。

例1（二元域$F_{2^4}$） 二元域$F_{2^4}$的元素表示為如下16個二元多項式，它的冪不超過3:

例2： 通過一個栗子說明在二元域$F_{2^4}$中如何用多項式$f(z)=x^4+z+1$進行一系列約化模運算。
1 加法：$(z^3+z^2+1)+(z^2+z+1)=z^3+z$
2 減法：$(z^3+z^2+1)?(z^2+z+1)=z^3+z$。
注意 $?1=1\mathrm{m}\mathrm{o}\mathrm{d}2$，一般的，對于任意$a\in F_{a^m}$，$?a=a\mathrm{m}\mathrm{o}\mathrm{d}2$
3 乘法：$(z^3+z^2+1)\dot{(}{z}^2+z+1)=z^2+1$，因為：$(z^3+z^2+1)\dot{(}{z}^2+z+1)=z^5+z+1$ 且$(z^5+z+1)\mathrm{m}\mathrm{o}\mathrm{d}(z^4+z+1)=z^2+1$.
4 求逆：$(z^3+z^2+1{)}^{?1}=z^2$，因為$(z^3+z^2+1)?z^2\mathrm{m}\mathrm{o}\mathrm{d}(z^4+z+1)=1$

例3（同態域）：假設有3個冪為4的不可約二元多項式，分別為：$f_1(z)=z^4+z+1$，$f_2(z)=z^4+z^3+1$和$f_3(z)=z^4+z^3+z+1$。每個約化多項式能被用于構造域$F_2^4$；假設目標域分別為$k_1$,$k_2$,$k_3$。因此$k_1$,$k_2$,$k_3$的域元素同為16個二元多項式，其冪不超過3。換句話說，雖然這些域看起來明顯不同，例如：在$k_1$中，$z^3.z=z+1$;在$k_2$中，$z^3.z=z^3+1$;在$k_3$中，$z^3.z=z^3+z^2+z+1$，但是它們具有相同的階數，因此是同態的，只是元素具有不同的標記。K1和k2之間的同構性可以通過找到$c\in k_2$，c滿足$f_1(c)\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}{f}_2$，然后擴展$z?c$到同態$\phi :k_1\to k_2$來構造。 對c的選擇可以為$z^2+z$,$z^2+z+1$,$z^3+z^2$和$z^3+z^2+1$。

擴展域

在二元域中，多項式可以泛化為如下擴展域形式。

設p為質數，$m\ge 2$，$F_p[z]$表示以z為自變量，系數屬于$F_p$的一元多次方程。設$f(z)$為一個冪為m（$m\in F_p[z]$）的不可約多項式，可以證明，該多項式對任意p和m是存在的。$f(z)$的不可約性意味著$f(z)$不能分解為$f(z)$中的多項式的乘積。在$F_{p^m}$中，元素是$F_p[z]$的多項式，且冪不大于m-1。
域元素的加法通常表示為多項式的和，其系數運算在$F_p$中執行。域元素的乘法表示為多項式$f(z)$的模。

例4（擴展域） 設p=251，m=5，$f(z)=z^5+z^4+12z^3+9^2+7$是$F_{251}[z]$中的不可約多項式，將$F_{251^5}$設為約化多項式，可知$F_{251}[z]$的階為$251^5$，且$F_{251^5}$的元素為$F_{251}[z]$中的多項式，冪不大于4。
以下是有限域$F_{251^5}$中的算數運算，其中，$a=123z^4+76z^2+7z+4$，$b=196z^4+12z^3+225z^2+76$。
1 加法: $a+b=68z^4+12z^3+50z^2+7z+179$
2 減法： $a?b=178z^4+239z^3+102z^2+z^z+179$
3 乘法： $a?b=117z^4+151z^3+117z^2+182z+217$
4 除法： $a^{?1}=109z^4+111z^3+250z^2+98z+85$

有限子域

當$k$是一個關于有限域$K$操作的數據域時，$K$的子集$k$即為$K$的子域，$K$稱為$k$的一個擴展域。有限子域較為容易地特征化。設$F_{p^m}$是一個有限域，對于m的每個正除數$l$，都具有一個階為$p^l$的子域，其元素滿足$a^{p^l}=a$，且$a\in F_{p^m}$。反過來，對于一些m的正除數$l$，每個$F_{p^m}$的有限子域的階為$p^l$。

有限域的基

$F_{q^n}$是一個建立在有限子域$F_q$基礎上的向量空間。其中，空間中的向量是$F_{q^n}$的元素，其標量是$F_q$的元素，向量的和是$F_{q^n}$的加法運算，標量的乘積是$F_{q^n}$中$F_q$元素的乘法運算，向量空間是由不同基數構造的n維空間。
如果$B=b_1,b_2,...,b_n$表示一個基數，$a\in F_{q^n}$唯一表示為$F_q$元素的n元組$(a_1,a_2,...,a_n)$，其中$a=a_1{b}_1+a_2{b}_2+...+a_n{b}_n$。在以上有限域$F_{p^m}$的多項式基中，$F_{p^m}$是在$F_p$上的m維向量空間，$（z^{m?1},z^{m?2},...,z^2,z,1）$是建立在$F_p$上的$F_{p^m}$的基數。

有限域乘法群

有限域$F_q$的非0元素${F_q}^{?}$構成一個乘法循環群。此時元素$b(b\in {F_q}^{?})$存在，稱為生成元。生成元滿足以下關系式：${F_q}^{?}=\{b^i:0\le i\le q?2\}$。$a\in {F_q}^{?}$的階是$a^t=1$的最小的正整數$t$。${F_q}^{?}$是一個循環群，且$t$為$q?1$的除數。

總結

以上是生活随笔為你收集整理的有限域算数运算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。