\documentclass[a4paper]{article}

\usepackage[italian]{babel}
\usepackage{amssymb}

\newtheorem{teor}{Teorema}

\begin{document}
\begin{center}
\large
\textbf{L'algoritmo di fattorizzazione di Berlekamp}
\end{center}

\normalsize

\noindent
\textbf{Primi ingredienti:}
\begin{enumerate}
\item Siano $f, a, b$ polinomi di $\mathbb{Z}_p[x]$ tali che $a$ e $b$ 
sono primi tra loro. Allora vale: 
\[
\gcd(f, ab) = \gcd(f, a)\cdot  \gcd(f, b)
\]
\item Il polinomio $x^p-x  \in \mathbb{Z}_p[x]$ si spezza nel prodotto
\[
(x-0)\cdot(x-1)\cdots(x-(p-1))\]
\item Se $g \in  \mathbb{Z}_p[x]$, allora vale:
\[
g^p-g = (g-0)\cdot(g-1)\cdots (g-(p-1))
\]
\end{enumerate}
Per vedere il primo punto, basta scrivere ciascuno dei 
tre polinomi come prodotto di potenze di polinomi irriducibili; il 
secondo punto segue dal piccolo teorema di Fermat. Il terzo punto segue
dal secondo e dal fatto che l'applicazione $\phi :  \mathbb{Z}_p[x]
\longrightarrow \mathbb{Z}_p[x]$ definita da $\phi(a_0+a_1x+\cdots+a_nx^n)
= a_0+a_1g+\cdots+a_ng^n$ \`e un omomorfismo di anelli.

\begin{teor} \label{teor1}
Sia $f$ un polinomio di $\mathbb{Z}_p[x]$ e sia $g  \in
\mathbb{Z}_p[x]$ un polinomio
tale che:
\begin{enumerate}
\item $1 \leq \deg(g) < \deg(f)$; 
\item $f$ divide $g^p-g$;
\end{enumerate}
allora vale: 
\[
f = \gcd(f, g-0) \cdot \gcd(f, g-1) \cdots 
  \gcd(f, g-(p-1))
\]
e la fattorizzazione di $f$ scritta sopra \`e effettiva, cio\`e ci sono 
fattori propri di~$f$. 
\end{teor}
\textsc{Dim.:} Se $f$ divide $g^p-g$ allora abbiamo: 
\begin{eqnarray*}
f & = & \gcd(f, g^p-g) \\
  & = & \gcd(f, (g-0)\cdot (g-1)\cdots (g-(p-1)) \\
  & = & \gcd(f, g-0) \cdot \gcd(f,g-1) \cdots 
        \gcd(f,g-(p-1))
\end{eqnarray*}
L'ultimo passaggio segue dal fatto che $g-i$ e $g-j$ sono, se $i \not = j$, 
primi tra loro (infatti se un polinomio divide entrambi, deve dividere la 
loro differenza che \`e la costante $i-j$). Poich\`e il grado di $g$ \`e
inferiore al grado di $f$, ognuno dei polinomi
$\gcd(f, g-i)$ ha grado inferiore al grado di $f$; inoltre, 
poich\`e $g$ non \`e una costante, non pu\`o succedere che 
$\gcd(f, g-i)$ sia, per qualche $i\in \mathbb{Z}_p$, il 
polinomio $f$ stesso, quindi la fattorizzazione scritta sopra \`e 
effettiva. \hfill $\square$

Per riuscire a fattorizzare un polinomio $f$  di $\mathbb{Z}_p[x]$ si deve 
quindi trovare un polinomio $g$ con le propriet\`a indicate nel precedente 
teorema. Il problema diventa allora quello di trovare i polinomi $g$ 
che soddisfano alle seguenti due condizioni: 
\begin{enumerate}
\item $\deg(g) < d$ (dove $d = \deg(f)$);
\item $ f \mid g^p-g$.
\end{enumerate}
(per ora non richiediamo la condizione $deg(g) \geq 1$, come richiesta 
nel teorema precedente).

\goodbreak
Sia allora $g=b_0+b_1x+\cdots +b_{d-1}x^{d-1}$ il generico polinomio 
di grado al pi\`u $d-1$ con coefficienti $b_0, b_1, \dots, b_{d-1} 
\in \mathbb{Z}_p$. Vale: 
\begin{eqnarray}
g^p & = & \left(b_0+b_1x+\cdots +b_{d-1}x^{d-1}\right)^p \nonumber \\
    & = & b_0^p+b_1^px^p+\cdots +b_{d-1}^px^{(d-1)p}\label{e1}\\ 
    & = & b_0+b_1x^p+\cdots +b_{d-1}x^{(d-1)p}\label{e2}
\end{eqnarray}
dove (\ref{e1}) deriva dal fatto che nell'anello $\mathbb{Z}_p[x]$, 
che \`e di caratteristica $p$, vale $(\alpha + \beta)^p = \alpha^p + \beta^p$, 
mentre l'uguaglianza (\ref{e2}) segue dal piccolo teorema di Fermat, 
cio\`e dal fatto che ogni elemento di $\mathbb{Z}_p$ soddisfa all'equazione
$a^p = a$. Se dividiamo $g^p-g$ per $f$ otteniamo: 
\[
g^p-g = q\cdot f + r, 
\]
dove $\deg(r) < \deg(f)$, allora per avere che 
$f$ divida $g^p-g$ bisogna avere che $r$ sia $0$. Per calcolare in 
modo pi\`u esplicito il resto $r$ dividiamo intanto i monomi
$x^{jp}$ che compaiono in $g^p$; sia dunque:
\[
x^{jp} = q_j\cdot f + r_j, \quad \textrm{per} \ j = 0, \dots, d-1
\]
dove $\deg(r_j) < d$. Sostituendo questi valori di $x^{jp}$ in 
$g^p$ otteniamo: 
\begin{eqnarray*}
g^p - g & = & b_0x^0+b_1x^p+\cdots +b_{d-1}x^{(d-1)p} 
                    - b_0 - b_1x -\cdots - b_{d-1}x^{d-1} \\
  & = & b_0(q_0\cdot f + r_0) +b_1(q_1\cdot f + r_1) + \cdots + 
         b_{d-1}(q_{d-1}\cdot f + r_{d-1}) \\
   & & \quad      {}-b_0 - b_1x -\cdots - b_{d-1}x^{d-1} \\
  & = & (b_0q_0+\cdots+ b_{d-1}q_{d-1})\cdot f + b_0 r_0 
           + \cdots +b_{d-1}r_{d-1}\\
   & & \quad      {}-b_0 - b_1x -\cdots - b_{d-1}x^{d-1} 
\end{eqnarray*}
Pertanto il resto $r$ della divisione di $g^p-g$ per $f$ vale:
\begin{eqnarray}
r & = & b_0 r_0 + \cdots +b_{d-1}r_{d-1} -b_0 - b_1x -\cdots - b_{d-1}x^{d-1} 
\label{e3}
\end{eqnarray}
I polinomi $r_j$ sono polinomi di grado al pi\`u $d-1$, quindi sar\`a:
\[
r_j = r_{0\, j} + r_{1\, j}x + \cdots + r_{d-1 \, j}x^{d-1} 
  \quad \textrm{per} \ j = 0, \dots, d-1
\]
Sostituendo questi valori per $r_j$ in (\ref{e3}) si ottiene:
\begin{eqnarray*}
r & = & b_0(r_{0\, 0} + r_{1\, 0}x + \cdots + r_{d-1 \, 0}x^{d-1}) \\
  &  & {}+b_1(r_{0\, 1} + r_{1\, 1}x + \cdots + r_{d-1 \, 1}x^{d-1}) \\
  &  &  \cdots \\
  &  & {}+b_{d-1}(r_{0\, d-1} + r_{1\, d-1}x + \cdots 
                             + r_{d-1 \, d-1}x^{d-1}) \\
   & & {}-b_0 - b_1x -\cdots - b_{d-1}x^{d-1} \\
  & = & (b_0 r_{0\, 0} + \cdots +b_{d-1} r_{0\, d-1} -b_0) + \\
  &  &  (b_0 r_{1\, 0} + \cdots +b_{d-1} r_{1\, d-1} -b_1)x +\\
  &  &  \dots \\
  &  &  (b_0 r_{d-1\, 0} + \cdots +b_{d-1} r_{d-1\, d-1} -b_{d-1})x^{d-1}
\end{eqnarray*}
Affinch\'e il polinomio $r$ sia zero, per il principio di identit\`a dei
polinomi, devono essere zero tutti i suoi coefficienti, quindi abbiamo che:
$f$ divide $g^p-g$ se e solo se $b_0, \dots, b_{d-1}$ soddisfano il 
sistema lineare: 
\[
\left\{
\begin{array}{ccccccccc}
(b_0-1) r_{0\, 0} & + & b_1r_{0\, 1} & + & \cdots  & 
    + & b_{d-1} r_{0\, d-1} & = & 0\\
b_0 r_{1\, 0} & + & (b_1-1)r_{1\, 1} & + &\cdots  & 
   + & b_{d-1} r_{1\, d-1} & = & 0 \\
& \dots & & &\dots & & &\dots & \\
b_0 r_{d-1\, 0} & + & b_1r_{d-1\, 1} & + &\cdots  & 
   + & (b_{d-1}-1) r_{d-1\, d-1} & = & 0 
\end{array}
\right.
\]
Detta $Q$ la matrice seguente: 
\[
Q = \left(
\begin{array}{cccc}
r_{0\, 0} & r_{0\, 1} & \cdots & r_{0\, d-1} \\
r_{1\, 0} & r_{1\, 1} & \cdots & r_{1\, d-1} \\
& \cdots &\cdots & \\
r_{d-1\, 0} & r_{d-1\, 1} & \cdots & r_{d-1\, d-1} 
\end{array}
\right)
\]
otteniamo allora che $f$ divide $g^p-g$ se e solo se il vettore 
${}^t(b_0, b_1, \dots, b_{d-1})$ appartiene al nucleo di 
$Q-I$, dove $I$ \`e la matrice identica di ordine $d$.
Pertanto abbiamo trovato che vi \`e una corrispondenza biunivoca 
tra l'insieme 
\begin{eqnarray}
G = \left\{ g \in \mathbb{Z}_p[x]\ : \ \deg(g) < d \ \textrm{ e } 
\ f \mid g^p-g \right\} \label{defG}
\end{eqnarray}
e $\ker(Q-I)$. Nella corrispondenza biunivoca l'elemento $g = b_0+b_1x+
\cdots + b_{d-1}x^{d-1}$ viene mandato nel vettore 
${}^t(b_0+b_1+\cdots +b_{d-1})$. Si verifica poi facilmente che l'insieme
$G$ \`e uno $\mathbb{Z}_p$--spazio vettoriale, come anche $\ker(Q-I)$ e si
vede subito che la corrispondenza biunivoca in realt\`a \`e un isomorfismo
di spazi vettoriali. Le considerazioni fin qui fatte si possono 
riassumere nel: 
\begin{teor} \label{teor2}
Sia $f$ un polinomio di $\mathbb{Z}_p[x]$ di grado $d$. 
Allora vi \`e un isomorfismo di spazi vettoriali tra i polinomi $g$ dello
spazio  vettoriale $G$ definito in (\ref{defG})  
e $\ker(Q-I)$ dove $Q$ \`e la matrice le cui colonne
sono i coefficienti dei resti della divisione di $x^{jp}$ per $f$ 
(dove $j$ vale $0, 1, \dots, d-1$) \hfill $\square$
\end{teor} 
Dai teoremi \ref{teor1} e \ref{teor2} si ha quindi un metodo per fattorizzare
i polinomi di $\mathbb{Z}_p[x]$. 

\medskip
\noindent
\textbf{Osservazione} L'insieme $G$,  definito in (\ref{defG}), contiene 
sempre almeno tutte le costanti, cio\`e $\mathbb{Z}_p$ (come segue subito
dal piccolo teorema di Fermat). Pu\`o succedere per\`o che $G$ contenga 
\textit{solo} le costanti. In questo caso tutti i polinomi di $G$ hanno grado
0 e quindi non si \`e riusciti a costruire alcun polinomio di grado 
almeno 1, come richiesto dal teorema \ref{teor1}. Quando $G$ contiene 
solamente le costanti, la sua dimensione, come $\mathbb{Z}_p$--spazio
vettoriale, \`e 1 (e quindi \`e 1 anche la dimensione di $\ker(Q-I)$). 
Questo \`e il punto di partenza per un successivo teorema di Berlekamp.

\begin{teor} Sia $f$ un polinomio di $\mathbb{Z}_p[x]$ di grado $d$ 
e sia $Q$ la matrice sopra costruita. allora vale: 
\begin{enumerate}
\item La dimensione di $\ker(Q-I)$ come $\mathbb{Z}_p$--spazio vettoriale
coincide con il numero dei fattori irriducibili distinti di $f$;
\item $f$ \`e irriducibile se e solo se $\dim(\ker(Q-I))=1$ e $f$ e 
$f'$ sono primi tra loro.
\end{enumerate}
\end{teor}
\textsc{Dim.:} Supponiamo che il numero di fattori irriducibili 
distinti di $f$ sia $k$, quindi il polinomio $f$ pu\`o essere 
scomposto in: 
\[
f= q_1^{\alpha_1}\cdot q_2^{\alpha_2}\cdots q_k^{\alpha_k}
\]
(con $q_1, q_2, \dots, q_k$ polinomi irriducibili distinti 
di $\mathbb{Z}_p[x]$). Sia $G$ definito come in (\ref{defG}) e 
prendiamo $g \in G$. Quindi $f \mid g^p-g$, perci\`o $q_i \mid g^p-g
=(g-0)\cdot (g-1)\cdots (g-(p-1))$
per ogni $i=1, \dots, k$, da cui segue, essendo $q_i$ irriducibile, 
che per ogni $i$ esiste un $s_i\in \mathbb{Z}_p$ tale che $q_i$
divide $g-s_i$ (inoltre $s_i$ \`e univocamente determinato da 
$q_i$, in quanto i polinomi $g-i$ e $g-j$, se $i \not = j$, sono primi
tra loro). Pertanto abbiamo costruito un'applicazione 
$\phi: G \longrightarrow \mathbb{Z}_p^k$ tale che 
$\phi(g) = (s_1, \dots, s_k)$. Verifichiamo che $\phi$ \`e suriettiva: 
sia $(s_1, \dots, s_k) \in \mathbb{Z}_p^k$,  allora, per il teorema
cinese del resto, esiste un unico polinomio $g\in \mathbb{Z}_p$ tale
che $g \equiv s_i \ \mathrm{mod}(q_i^{\alpha_i})$ e $\deg(g) < \alpha_1
+ \cdots + \alpha_k = \deg(f)$. Inoltre, da $q_i^{\alpha_i} \mid g-s_i$
otteniamo che $q_i^{\alpha_i} \mid g^p-g$ e quindi, essendo i polinomi
$q_i^{\alpha_i}$ a due a due coprimi, anche il loro prodotto, che 
\`e $f$, deve dividere $g^p-g$. Questo prova che $g \in G$. Si verifica
poi subito che $\phi(g) = (s_1, \dots, s_k)$ e quindi $\phi$ \`e suriettiva; 
essendo un'applicazione tra insiemi finiti, \`e anche iniettiva, pertanto
$G$ ha lo stesso numero di elementi di $\mathbb{Z}_p^k$, cio\`e $G$ ha 
$p^k$ elementi. Si \`e precedentemente dimostrato che $G$ \`e
uno spazio vettoriale sul campo $\mathbb{Z}_p$, quindi per avere $p^k$ 
elementi deve necessariamente avere una base di $k$ elementi. Cio\`e
la sua dimensione, come $\mathbb{Z}_p$--spazio vettoriale, \`e $k$. 
Essendo $\ker(Q-I)$ isomorfo a $G$, anche $\dim(\ker(Q-I)) = k$. Questo
prova il primo punto. Il secondo punto segue facilmente dal primo 
punto e dal fatto che un polinomio (in $\mathbb{Z}_p[x]$) non ha fattori 
multipli se e solo se $f$ e $f'$ sono primi tra loro. \hfill $\square$



\end{document}