3.1　有限域

3.1.1　概述

本條給出有限域Fq的描述及其元素的表示，q是一個奇素數或者是2的方冪。當q是奇素數p時，要求p>2^191；當q是2的方冪2^m時，要求m>192且為素數。

3.1.2　素域Fp

當q是奇素數p時，素域Fp中的元素用整數0,1,2,…,p-1表示。素域特性如下：

a) 加法單位元是整數0；

b) 乘法單位元是整數1；

c) 域元素的加法是整數的模p加法，即若a,b∈Fp，則a+b = (a+b) mod p；

d) 域元素的乘法是整數的模p乘法，即若a,b∈Fp，則ab = (ab) mod p。

3.1.3　二元擴域F2^m

當q是2的方冪2^m時，二元擴域F2m可以看成F2上的m維向量空間，其元素可用長度為m的比特串表示。

F2m中的元素有多種表示方法，其中最常用的兩種方法是多項式基(PB)表示(參見附錄A.2.1.1)和正規基(NB)表示(參見附錄A.2.1.3)。基的選擇原則是使得F2^m中的運算效率盡可能高。本標準并不規定基的選擇。下面以多項式基表示為例說明二元擴域F2^m。

設F2^m次不可約多項式f (x)=x^m+f(m-1)*x^(m-1)+…+ f2x^2+ f1x+ f0 (其中f i∈F2, i = 0,1, …,m-1)是二元擴域F2m的約化多項式。F2m由F2上所有次數低于m的多項式構成。多項式集合{xm-1,xm-2,…, x,1}是F2m在F2上的一組基，稱為多項式基。F2m中的任意一個元素a(x) = am-1xm-1+ am-2xm-2+…+ a1x+ a0在F2上的系數恰好構成了長度為m的比特串，用a =(am-1, am-2,…, a1, a0)表示。多項式域特性如下：

a)零元0用全0比特串表示；

b)乘法單位元1用比特串00…001表示；

c)兩個域元素的加法為比特串的按比特異或運算；

d)域元素a和b的乘法定義如下：設a和b對應的F2上多項式為a(x)和b(x)，則a?b定義為多項式(a(x)b(x)) modf(x)對應的比特串。