Uma transformação afim é uma transformação entre dois
espaços afins A e
B. Essa transformação, ou mapeamento, consiste numa transformação lineal em
A somado de um vetor
b \in B. Ou seja:
S(x)=Tx + b.
No campo da criptografia post-quântica as transformações afins são usadas para ocultar a chave pública dos sistemas de cifração baseados em multivariados.
Para os envolvidos na área é de importância saber lidar com as diferentes representações de uma transformação afim. Neste post apresentarei essas representações e mostrarei como converter uma para a outra.
Seja
\mathbb{F} um corpo finito com
q elementos e
\mathbb{E} uma extensão de grau
n do corpo
\mathbb{F}. Seja
S:\mathbb{F}^n\rightarrow \mathbb{F}^n uma transformação afim.
Definição 1: Seja
0\leq i < n e
A,B_i \in \mathbb{E}. Então nós chamamos o polinômio
S(X)=\sum_{i=0}^{n-1}B_i X^{{q}^i}+A a representação de uma só variável da transformação afim
S.
Definição 2: Seja
M_S \in \mathbb{F}^{n\times n} uma matriz e
v_s \in \mathbb{F}^n um vetor. Então nos chamamos
S(x):=M_Sx+v_s, a representação matricial da transformação afim
S .
Definição 3: Seja o espaço vetorial
\mathbb{F}^n. Então nós chamamos
\phi:\mathbb{E}\rightarrow \mathbb{F}^n com
\phi(a):=b e
b_i=a_{i-1} de bijeção canônica.
Teorema: Uma transformação afim, com
v=0 na representação de uma só variável pode ser transformada eficientemente na sua representação matricial.
Prova: Definamos
e_i \in \mathbb{F}^n com
1\leq i \leq n, com um
1 no seu i-th coeficiente e zero no restante. Vamos a mostrar que a coluna
k dessa matriz é dada pela seguinte fórmula:
M_k=\phi(S(\phi^{-1}(e_k))). Vamos a definir
P(X):=\sum_{i=0}^{n-1}B_i X^{{q}^i}. Da álgebra conhecemos que o corpo
\mathbb{F}^n é também um espaço vetorial sobre o corpo
\mathbb{F}. Esse espaço vetorial tem a base
V=\{t^0, t^1, t^2,\ldots,t^{{n-1}}\}. Vamos a representar os coeficiente de
P(X) como
B_i =\sum_{j=0}^{n-1}b_{ij} t^j e a variável
X=\sum_{k=0}^{n-1}X_{k}t^k. Substituindo esses valores em
P(X) temos
P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} t^j(\sum_{k=0}^{n-1}X_{k}t^k)^{{q}^i},
Usando o
teorema binomial e reduzindo temos
P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}t^{j+k{{q}^i}},
Escrevendo
t^{j+k{{q}^i}} usando a base
V temos
t^{j+k{{q}^i}} = \sum_{m=0}^{n-1}c_{ijkm}t^m. Por tanto:
P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k} \sum_{m=0}^{n-1}c_{ijkm}t^m
P(X) = \sum_{m=0}^{n-1}\underline{\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}c_{ijkm}}_{E}t^m
Por outro lado, escrevendo
\phi(S(\phi^{-1}(e_k))) usando a base
V temos que esta é igual a:
\phi(S(\phi^{-1}(e_k)))=(\sum_{i,j}^{n-1}b_{i,j}c_{ijk0}, \cdots, \sum_{i,j}^{n-1}b_{i,j}c_{ijk(n-1)}). Por fim, veja que
E_m = (\phi(S(\phi^{-1}(e_1)))[m],\cdots,\phi(S(\phi^{-1}(e_{n-1})))[m])^{T}*(X_1,\cdots, X_{n-1}).
No caso de transformação afim com
v \neq 0 então se tem que v:=
M_k=\phi(S(\phi^{-1}(0))) e as colunas de
M são
M_k=\phi(S(\phi^{-1}(e_k)))-v.
First the DFA solution is presented in the next table and his diagram in JFLAP in the next file.
