\begin{document}
\documentclass[11pt]{article}

\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{complexity}
\usepackage{graphicx}

\usepackage{palatino} %what a beautiful font!


\newcommand{\handout}[5]{
  \noindent
  \begin{center}
    \framebox[\textwidth]{
      \vbox{
        \hbox to \textwidth { {\bf #2}\hfill {\bf Computational Number Theory }
       }
        \vspace{4mm}
        \hbox to \textwidth { {\Large \hfill #5  \hfill} }
        \vspace{2mm}
        \hbox to \textwidth { {\em #3 \hfill #4} }
      }
    }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Instructor: #3}{Scribe:
    #4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{theorem*}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[]{Fact}
\newtheorem{subclaim}[theorem]{Subclaim}

% my custom commands
\newcommand{\inparen}[1]{\left(#1\right)}             %\inparen{x+y}  is (x+y)
\newcommand{\inbrace}[1]{\left\{#1\right\}}           %\inbrace{x+y}  is {x+y}
\newcommand{\insquar}[1]{\left[#1\right]}             %\insquar{x+y}  is [x+y]
\newcommand{\inangle}[1]{\left\langle#1\right\rangle} %\inangle{A}    is <A>
\newcommand{\abs}[1]{\left|#1\right|}                 %\abs{x}        is |x|
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}        %\norm{x}       is ||x||
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\intersection}{\cap}
\newcommand{\Intersection}{\bigcap}
\newcommand{\super}[2]{#1^{\inparen{#2}}}             %\super{G}{i-1} is G^{(i-1)}
\newcommand{\setdef}[2]{\inbrace{{#1}\ : \ {#2}}}
\newcommand{\inv}[1]{#1^{-1}}
\newcommand{\inrpdt}[2]{\left\langle{#1},{#2}\right\rangle}%\inrpdt{x}{y} is <x,y>.
\newcommand{\pderiv}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\iso}{\cong}
\newcommand{\bea}[1]{\begin{eqnarray*} #1 \end{eqnarray*}}
\newcommand{\legendre}[2]{\inparen{\frac{#1}{#2}}}

% Commands specific to this file
% TODO: Find the right way to typeset group index
\DeclareMathOperator{\Sym}{Sym}
\newcommand{\gpidx}[2]{\insquar{#1 : #2}}             %\gpidx{H}{K}   is [H : K]
\newcommand{\gpigs}[2]{\gpidx{\super{G}{#1}}{\super{G}{#2}}} %Group index of g super ...
\newcommand{\llhd}{\!\!\lhd\!\!\lhd}
\newcommand{\roundoff}[1]{\left\lfloor #1 \right\rceil}


% \newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\R}{\mathbb{R}}
\renewcommand{\C}{\mathbb{C}}

%for algorithms
\renewcommand{\algorithmicrequire}{\textbf{Input:}}

% Problems we look at
\newcommand{\GIso}{\lang{Graph\text{-}Iso}} %Without \text, ugly minus instead of hyphen.
\newcommand{\GAut}{\lang{Graph\text{-}Aut}}
\newcommand{\SStab}{\lang{Set\text{-}Stab}}

%for Quantum computing
\newcommand{\q}[1]{\left|#1\right\rangle}


\lecture{12: Berlekamp's Algorithm}{CS681}{Piyush P Kurur}{Ramprasad Saptharishi}

\section*{Overview}

Last class we say a randomized algorithm for factoring univariate
polynomials over a finite field. This class we shall look at another
algorithm for factoring. This was given by Berlekamp.

\section{Berlekamp's Algorithm}

We are given a polynomial $f(X) \in \F_p[X].$ As in all factoring
algorithms, the first thing to do is make $f$ square free. Once we
have done this, the polynomial is of the form
$$
f = f_1f_2\cdots f_m
$$
where each $f_i$ is a distinct irreducible factor of $f.$ Then,
chinese remaindering tells us that
$$
R = \F_p[X]/(f)
= \inparen{\F_p[X]/(f_1)}\times\inparen{\F_p[X]/(f_2)}\times \cdots \times \inparen{\F_p[X]/(f_m)}
$$

Let the degree of $f_i$ be $d_i$ and the degree of $f$ be $n.$

\subsection{The Frobenius Map}

Here enters the frobenius map again. Consider the following function
from $R$ to itself. 

\bea{
T:R& \longrightarrow & R\\
a & \mapsto & a^p        
}

The first thing to note here is that all elements of $\F_p$ are
fixed in this map because we know that elements $\F_p$ satisfy $X^p -
X=0.$ And further, we also saw the special case of binomial theorem
that said $(X+Y)^p = X^p + Y^p.$ 

To understand this map $T$ better, let us understand $R.$ We have
defined $R = \F_p[X]/(f)$ which is basically polynomials over $\F_p$
modulo $f.$ And clearly, every element of $R$ has degree atmost $n-1$
and therefore a polynomial of the form $a_0 + a_1X + \cdots
a_{n-1}X^{n-1}$ can be thought of as the vector
$\inparen{a_0,a_1,\cdots, a_{n-1}}.$ Thus, the ring $R$ is a vector
space of dimension $n$ over $\F_p.$\\

Now, notice that the map $T$ described above is $\F_p$-linear. By
this, we mean that for all $\alpha,\beta \in \F_p$ and $u,v\in R$, we
have $T(\alpha u + \beta v) = \alpha T(u) + \beta T(v).$ If we think
of these elements of $\F_p$ as scalars, they can be 'pulled out of'
$T.$

Therefore, it's enough to know the image of each $X^i$ by the
map. 
\bea{
p(X) & = & a_0 + a_1X + \cdots + a_{n-1}X^{n-1}\\
T(p(X)) & = & a_0 + a_1T(X) + \cdots + a_{n-1}T(X^{n-1})
}

\subsection{The Berlekamp Sub-algebra}

Now let $B$ be the map $T -I$ where $I$ is the identity map (maps
everything to itself). Then $B$ sends any element $a\in R$ to $a^p -
a.$ Now define $\mathcal{B} = \ker(B) = \ker(T - I).$ It is easy to
check that the kernel of any linear map from one vector space into
another (in this case $R$ to $R$) forms a subspace of the vector
space. Hence $\mathcal{B}$ is a subspace of the vector space $R.$

This space $\mathcal{B}$ is called the Berlekamp sub-algebra. \\

What does this space look like? Let $a$ be any element in
$\mathcal{B}$ and therefore is an element of $R.$ Let the chinese
remainder theorem map this to the tuple $(a_1,a_2, \cdots, a_m).$ And
therefore $a^p - a = (a_1^p - a_1, \cdots, a_m^p - a_m).$ And since
$a\in \mathcal{B}$, each of the $a_i^p - a_i$ must be $0.$ Now, $a_i^p
- a_i$ is an element of $\F_p[X]/(g_i) \iso \F_{p^{d_i}}$ and
therefore $a_i^p - a_i = 0$ can happen only if
$a_i \in \F_p.$\footnote{the elements of $\F_{p^d}$ that satisfy $X^p
- X = 0$ are precisely those elements of $\F_p$} 

And therefore, each element of the tuple will infact be an element of
$\F_p$ and therefore
$$
\mathcal{B} \iso \F_p \times \cdots \times\F_p
$$

And since $\mathcal{B}$ is a product of $m$ copies of $\F_p$,
$\mathcal{B}$ is an $m$ dimensional subspace of $R$ over $\F_p.$

\subsection{Finding a Basis}

A basis for $R$ is obvious, $\inbrace{1,X,X^2,\cdots, X^{n-1}}$ but
how do we find a basis for $\mathcal{B}?$ Let us say $T$ acts on $R$
as
$$
T(X^i) = \sum_{j=0}^{n-1} \alpha_{ji}X^j
$$
then we can think of $T$ as a the matrix
$\inparen{\alpha_{ji}}_{i,j}.$ Thus, thinking of polynomials in $R$ as
a tuple of coefficients described above, then the action of $T$ is
just left multiplication by this matrix. 

Thus, the matrix for $B$ would be $\hat{B} = (\alpha_{ji})_{i,j} - I.$ Hence the
kernel of this map is just asking for all vectors $v$ such that
$\hat{B}v = 0.$ And therefore, a basis for $\mathcal{B}$ can be
obtained by gaussian elimination of $\hat{B}.$ 

Once we have a basis $\inbrace{b_1, b_2,\cdots, b_m}$, we can pick a
random element of $\mathcal{B}$ by just picking $m$ random elements
$a_m$ from $\F_p$ and $\sum a_ib_i$ would be our random element from
$\mathcal{B}.$ \\

Any element $a$ in $\mathcal{B}$ gets mapped to
$\F_p\times \cdots \times \F_p$ by the Chinese remainder theorem. And
therefore, we can use the Cantor-Zassenhaus idea there:
$a^{\frac{p-1}{2}}$ corresponds to a vector of just $1$s and $-1$s.

So here is the final algorithm. 

\begin{algorithm}
\caption{{\sc Berlekamp Factorization}}
\begin{algorithmic}[1]
\REQUIRE A polynomial $f\in \F_p[X]$ of degree $n$
\STATE Make $f$ square-free. 
\STATE Let $R$ be the ring $\F_p[X]/(f),$ considered as a $n$
dimensional vector space over $\F_p.$
\STATE Construct the matrix of transformation $\hat{B}$ corresponding
to the map $a\mapsto a^p - a.$
\STATE Use gaussian elimination and find a basis $\inbrace{b_1,
b_2, \cdots, b_m}$ for the berlekamp subalgebra $\mathcal{B}.$
\STATE Pick $\inbrace{a_1, \cdots, a_{m-1}} \in_R \F_p$ and let $b
= \sum a_ib_i.$
\IF{$gcd(b^{\frac{p-1}{2}}+1,f)$ is non-trivial}
\STATE {\bf return} $gcd(b^{\frac{p-1}{2}}+1,f)$
\COMMENT{Happens with probability atleast $1 - 2^{m-1}$}
\ENDIF
\STATE Repeat from step $5.$
\end{algorithmic}
\end{algorithm}

\end{document}