Конечное поле $(\mathbb F,+,\cdot)$ это конечное множество $\mathbb F$ с двумя внутренними законами $+$ и $\cdot$, такой, что $(\mathbb F,+)$ является коммутативным группа с нейтральным отмеченным $0$, и $(\mathbb F-\{0\},\cdot)$ является коммутативной группой с нейтральными отмеченными $1$, а умножение является дистрибутивным относительно дополнение, которое $\forall A,B,C\in\mathbb F$ он держит $A\cdot(B+C)=(A\cdot B)+(A\cdot C)$.
Можно показать, что все конечные поля с одинаковым числом элементов являются изоморфный, то есть мы можем отображать одно в другое с помощью биекция $\mathcal F$ такой, что $\mathcal F(A+B)=\mathcal F(A)+\mathcal F(B)$ и $\mathcal F(A\cdot B)=\mathcal F(A)\cdot \mathcal F(B)$. Таким образом, мы можем говорить о в конечное поле $\mathbb F$ с $q$ элементы. Это часто отмечается $\mathbb F_q$.
Можно показать, что любое конечное поле имеет число $q$ элементов формы $q=p^k$ для некоторого простого $р$ и немного $k\in\mathbb N^*$.
Когда $к=1$, поле $(\mathbb F_p,+,\cdot)$ это просто кольцо целых чисел по модулю $р$, это $(\mathbb Z_p,+,\cdot)$.
Для произвольного $k\in\mathbb N^*$, мы можем думать о поле $(\mathbb F_{p^k},+,\cdot)$ как множество многочленов степени до $к-1$ и коэффициенты в $\mathbb Z_p$. То есть полиномы для абстрактной переменной $х$ с одним коэффициентом $\mathbb Z_p$ для каждого из $к$ термины $х^я$ с $i\in\{0,1\ldots,k-1\}$. Дополнение в $\mathbb F_{p^k}$ есть сложение многочленов. Умножение в $\mathbb F_{p^k}$ представляет собой умножение полиномов с последующей редукцией по модулю конкретного редукционного полинома. $ Р (х) $ степени точно $к$, и непреодолимый.
Эквивалентно, мы можем думать о $\mathbb F_{p^k}$ как набор $p^k$ кортежи $к$ элементы $\mathbb Z_p$, отмеченный $(а_0,а_1\ldots,а_{к-1})$. Дополнение определяется$$(a_0,a_1\ldots,a_{k-1})+(b_0,b_1\ldots,b_{k-1})=(a_0+b_0,a_1+b_1\ldots,a_{k-1}+ б_{к-1})$$с более поздними дополнениями, внесенными в $\mathbb Z_p$, то есть с редукцией по модулю $р$. Если кортеж $А$ имеет $a_i=1$ и все остальные термины $0$, и кортеж $В$ имеет $b_j=1$ и все остальные термины $0$, потом, когда $i+j<k$ кортеж $С$ за $А\cточка Б$ имеет $c_{i+j}=1$ и все остальные термины $0$. Когда $i+j=k$, кортеж $С$ за $А\cточка Б$ постоянный кортеж $(r_0,r_1,\ldots,r_{k-1})$ независим от $я$ и $j=k-i$. Этот кортеж таков, что многочлен $R(x)=x^k-r_{k-1}\,x^{k-1}\ldots-r_1\,x-r_0$ с коэффициентами в $\mathbb Z_p$ является непреодолимый, подразумевая $r_0\ne0$. Этот постоянный кортеж $(r_0,r_1\ldots,r_{k-1})$, или, что то же самое, многочлен $ Р (х) $, в сочетании с ранее изложенными правилами и свойствами $+$ и $\cdot$, полностью определяет умножение и является нейтральным $(1,0\ldots,0)$.
Мы можем вычислить кортеж $(c_0,c_1\ldots,c_{k-1})$ за $(a_0,a_1\ldots,a_{k-1})\cdot(b_0,b_1\ldots,b_{k-1})$ следующее:
$(c_0,c_1\ldots,c_{k-1}):=(0,0\ldots,0)$
за $я$ от $к-1$ вплоть до $0$
- $м:=с_{к-1}$
- за $j$ от $к-1$ вплоть до $1$
- $c_j:=m\cdot r_j+a_i\cdot b_j+c_{j-1}$
- $c_0:=m\cdot r_0+a_i\cdot b_0$
с вычислениями в последних двух строках, перенесенными в $\mathbb Z_p$, то есть по модулю $р$.
