\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}