Proprietà su $GF(2^n)$

[_luca.barletta]

In $GF(2^n)$ si consideri un qualsiasi elemento $alphane0$.
Mostrare che la funzione $f(alpha)=alpha+alpha^2+alpha^4+alpha^8+...+alpha^(2^(n-1))$ può valere 0 oppure 1.

[TomSawyer1]

Mi è venuta in mente solo questa dimostrazione per induzione su $n$. Sarebbe interessante vederne una più costruttiva.

Denoto con $f_k(alpha)=alpha+alpha^2+\cdots+alpha^{2^{k-1}}$. Per $n=1$, abbiamo $f_1(1)=1$ e l'ipotesi è soddisfatta.
Supponiamo che sia soddsifatta per qualche $n\ge2$. Allora si ha $f_{n}(\alpha)\equiv 0,1 (mod 2^n)$, per ogni $\alpha \in GF(2^n)$. Ora ci serve solo il seguente teorema: se $a\equiv b (modp^l)$ allora $a^p\equiv b^p (mod p^{l+1})$. Dunque si avrà $[f_{n}(\alpha)]^2\equiv0^2,1^2 (mod 2^{n+1})$. Sviluppando $[f_{n}(\alpha)]^2=(\alpha+\alpha^2+\cdots+\alpha^{2^{n-1}})^2$, si ha che $f_{n}(\alpha)^2\equiv \alpha+\alpha^2+\cdots+\alpha^{2^{n}}=f_{n+1}(\alpha)$ in $GF(2^n)$, perche' $\alpha$ puo' essere visto come un polinomio con $\deg\alpha\le n$ e coefficienti in $ZZ_2$.

EDIT: ho un dubbio sulla dimostrazione, quindi aspetto conferme o smentite

[_luca.barletta]

L'ultimo periodo non mi convince molto.
Comunque si può provare anche senza induzione.

[TomSawyer1]

Non convince neanche me... Cerchero' una strada alternativa.

[fields1]

Naturalmente $GF(2^n)$ e' un anello di caratteristica $2$. Ma sappiamo che, in un anello di caratteristica $p$, vale che $(a+b)^p=a^p+b^p$. Inoltre sappiamo che per ogni $x\in GF(2^n)$, vale che $x^(2^n)=x$. Da queste osservazioni segue che:

$f(a)=a+a^2+a^4+...+a^(2^(n-1))=a^2+a^4+...+a^(2^n)=(a+a^2+a^4+...+a^(2^(n-1)))^2=f(a)^2$

Dunque, se $f(a)!=0$, moltiplicando ambo i membri per $f(a)^(-1)$, otteniamo che $f(a)=1$.

[_luca.barletta]

Ok fields.