Os elementos de F2m são polinômios de grau menor que m com
coeficientes binários.
{am-1xm-1 + am-2xm-2 + ... + a2x2
+ a1x + a0 | ai = 0 ou 1}.
O polinômio pode ser representado em um vetor como (am-1 ... a1
a0). F2m possui 2m elementos.
As principais operações em F2m são adição e multiplicação. Algumas
operações envolvem um polinômio f(x) = xm + fm-1xm-1 + fm-2xm-2 + ... +
f2x2 + f1x + f0, onde fi é um coeficiente binário. O polinômio f(x) (de grau
m) precisa ser irredutível, isto é, não pode ser fatorado em outros dois
polinômios. Este polinômio garante estas operações retornem polinômios
pertencentes ao F2m.
A adição de dois polinômios é definida como a operação de OU-
Exclusivo bit a bit. A multiplicação é módulo f(x), ou seja, (am-1 ... a1 a0) (bm-
1 ... b1 b0) = (rm-1 ... r1 r0), onde rm- 1xm-1 + ... + r1x + r0 é o resto da
divisão de (am-1xm-1 + ... + a1x + a0) (bm-1xm-1 + ... + b1x + b0) pelo
polinômio f(x). Todos os coeficientes são calculados módulo 2. A operação
de subtração é equivalente à adição e a operação de exponenciação é
derivada de forma direta da multiplicação, ou seja, (am-1 ... a1 a0)k é
realizada multiplicando k vezes (am-1 ... a1 a0).
Existe pelo menos um elemento g em F2m, tal que todos elementos
em F2m, à exceção do polinômio identicamente nulo, podem ser
expressados como uma potência de g. Este elemento é denominado o
gerador de F2m.
A seguir, segue um exemplo, considerando o campo F24, utilizando a
representação polinomial. O polinômio irredutível é f(x) = x4 + x + 1. O
elemento g = (0010) é um gerador deste campo. As potencies de g são:
g0 = (0001) g1 = (0010) g2 = (0100) g3 = (1000) g4 = (0011)
g5 = (0110) g6 = (1100) g7 = (1011) g8 = (0101) g9 = (1010)
g10 = (0111) g11 = (1110) g12 = (1111) g13 = (1101) g14 = (1001)
g15 = (0001)
Em uma aplicação de criptografia, o parâmetro m deve ser grande o
suficiente para permitir a criação de uma tabela imune a quebras.
Atualmente, o uso de m = 160 é uma escolha confiável.
A tabela permite a utilização da notação que utiliza potência do
gerador (gk), ao em vez de utilizar a notação de vetor de bits.
Continuando utilizando o campo F24 com o polinômio irredutível f(x)
= x4 + x + 1, considere a curva elíptica y2 + xy = x3 + g4x2 + 1, onde a =
g4 e b = g0 =1.
Os quinze pontos que satisfazem esta equação são:
(1, g13) (g3, g13) (g5, g11) (g6, g14) (g9, g13)
(g10, g8) (g12, g12) (1, g6) (g3, g8) (g5, g3)
(g6, g8) (g9, g10) (g10, g) (g12, 0) (0, 1)
