\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{11: Cantor-Zassenhaus Algorithm}{CS681}{Piyush P Kurur}{Ramprasad Saptharishi}

\section*{Overview}

In this class, we shall look at the Cantor-Zassenhaus randomized
algorithm for factoring polynomials over $\F_p.$ We shall do it for
the case when $p\neq 2.$ The case when $p=2$, which isn't too
different from the other case, would be given as an exercise for the
students to solve.

\section{Irreducibility Testing}

We left off last class with a hint that the distinct degree
factorization infact gives a straightforward irreducibility test. Here
is the explicit answer. \\

We are given an $f$ and we need to check if this polynomial is
irreducible or not. First check if it is square free. If it isn't,
immediately reject it. Else, proceed to compute the distinct degree
factors of $f.$ If the degree of $f$ is $n$, the DDF algorithm returns
$g_1,g_2,\cdots, g_n$ such that each $g_i$ is the product of
irreducible factors of $f$ of degree $d.$

Now, suppose $f$ was irreducible, then clearly every $g_i = 1$ for
$1\leq i\leq n-1$ and $g_n = f.$ Thus just check if the returned
$g_i$'s satisfy this condition. 

\subsection{Generating Irreducible Elements}

Suppose are given a positive integer $d,$ we want to efficiently find
an irreducible polynomial of degree $d$ over $\F_p.$ Now before we get
into this, why is this important?

The answer is that this is the only way we can construct the field
$\F_{p^d}.$ There are lots of applications where we need to do
arithmetic over a field of large size and $\F_p$ would be a candidate
only if the prime $p$ is large. And finding such a large prime is
hard and inefficient. 

Instead, we pick a small prime $p$ and try and find an irreducible
polynomial of degree $d.$ Once we do that, we have $\F_p[X]/(f(X))$
which is isomorphic to $\F_{p^d}.$ This is precisely finding
irreducible polynomials of a given degree is very useful. \\

To generate an irreducible polynomial of degree $d,$ we shall just
randomly pick a polynomial of degree $d.$ It can be argued that the
probability that this polynomial is irreducible is pretty high. And
since we even have a deterministic test to check if a polynomial $f$
is irreducible, we just repeat this procedure: Pick an $f\in \F_p[X]$
of degree $d$ at random and repeat this if the irreducibility test
says that this polynomial is not irreducible. 

All we need to do is to argue that the density of irreducible
polynomials is large. 


\begin{theorem}
Let $I(d)$ be the number of irreducible polynomials of degree $d$ over
$\F_p.$ Then 
$$
I(d) = \frac{p^d}{d} + O\inparen{\sqrt{p}}
$$
\end{theorem}

And therefore,
$$
\Pr_{f\in \F_p[X], deg(f) = d}[f \in
\text{Irr}(\F_p,d)] \geq \frac{\frac{p^d}{d} + O(\sqrt{p})}{p^d} \geq \frac{1}{d}
$$

As for the proof of the theorem, here is a sketch of it.
\begin{proof}(sketch)
We know that 
$$
X^{p^m} - X = \prod_{\substack{f\in \text{Irr}(\F_p,d)\\d\mid m}} f(X)
$$
Comparing the degrees on both sides, 
$$
p^m = \sum_{d\mid m} I(d)\cdot d
$$
Equations of this kind can be inverted using the {\em M\"{o}bius
Inversion.} 

\begin{lemma}[M\"{o}bius Inversion]
If we have any equation of the form 
$$
f(m) = \sum_{d\mid m} g(d)
$$
then 
$$
g(m) = \sum_{d\mid m}\mu(d)f(m/d)
$$
\end{lemma}
{\bf Exercise: } Read up on the M\"{o}bius Inversion. \\

With the inversion formula, once can complete the proof of the theorem
by taking $f(m) = p^m$ and $g(m) = I(m)\cdot m.$
\end{proof}

\section{The Cantor-Zassenhaus Algorithm}

Now we get to factoring a polynomial over $\F_p.$ Given a
polynomial of degree $f$ over $\F_p$, it is enough to get one
non-trivial\footnote{trivial factors of $f$ are $1$ and $f$. Factors
though they may be, are useless for us.} factor of $f.$ 

As we said in the last few lectures, the first thing to do is to check
if $f$ is square free. If it isn't we can just return the square-free
part of $f$ as a factor and be done. If it is square-free, we compute
the distinct degree factorization of $f.$ If $f$ turns out to be
irreducible, we just return ``irreducible.'' Else, we have to proceed
to find a non-trivial factor of $f.$ 

We shall factor each $g_i$ returned by the DDF algorithm
separately. Hence, we now assume that we have an $f\in \F_p[X] =
g_1\cdots g_m$ such that each $g_i$ is irreducible, distinct and of
the same degree $d.$\\

Here enters our old friend Chinese Remaindering. Since $f = g_1\cdots
g_m$, we know that 
$$
\F_p[X]/(f(X)) \iso \F_p[X]/(g_1(X)) \times \cdots \times \F_p[X]/(g_m(X))
$$

Now note that each $g_i$ is an irreducible polynomial of degree $d.$
And therefore, $\F_p[X]/(g_i(X))$ is isomorphic to $\F_{p^d}.$ Hence
the product just looks like
$$
\F_p[X]/(f(X)) \iso \F_{p^d} \times \cdots \times \F_{p^d}
$$

And further, we know that 
$$
\inparen{\F_p[X]/(f(X))}^\star \iso \F_{p^d}^\star \times \cdots \F_{p^d}^\star
$$

Now what do zero divisors, say $g$, in $\F_p[X]/(f)$ look like? When you take
the image under the chinese remaindering, it should go to some tuple
$(a_1,a_2,\cdots,a_m)$ where some $a_i=0.$ Further, if this zero
divisor is non-trivial ($0$ is a trivial zero-divisor, useless), some
other $a_j \neq 0.$ What does this mean? $g$ has a $0$ in coordinate
$i$ which means that $g$ is divisible by $g_i,$ and hence $g\neq 1.$
And also, $g$ is non-zero at coordinate $j$ and therefore $g_j$ does
not divide $g$ and hence $g\neq f.$ Thus, $gcd(g,f)$ is certainly not
$f$ nor $1$ and hence is a non-trivial factor of $f$. 

Therefore, the problem of finding factors reduces to the problem of
finding zero divisors in $\F_p[X]/(f(X)).$

\subsection{Finding Zero-Divisors}

The idea is the following. We cross our fingers and pick a polynomial
$a(X)$ of degree less than $n$ at random. This is some element from
$\F_p[X]/(f(X)).$ If we are extremely lucky we might just get
$gcd(a,f) \neq 1$, and this already gives us a non-trivial factor of
$f$ and we are done. Hence, lets assume that $a$ is not a zero-divisor
of the ring. And therefor, $a$ must be an element of
$\inparen{\F_p[X]/(f)}^\star$, an invertible element. 

Note that since we do not know the factors $g_i$, we do not know the
chinese remainder map. We just know that a map exists, we don't know
how to compute it. But suppose someone secretly told us that one of
the coordinates of $a$ under the chinese remainder map is $-1$, then
what can we do? 

Look at the images of $a(X) + 1.$ The images of this is just $1$
added to every coordinate of the image of $a(X).$ And since
someone told us that one of the coordinates was $-1$, that coordinate
in the image of $a(X) + 1$ must be zero! Which means that, $a(X) + 1$
is a zero divisor. However it is possible that all the coordinates is
$-1$ and that would just make $a(X) + 1 = 0$ which is useless. 

Now, how do we make sure that there is some $-1$ in one of the
coordinates and not everywhere? Use the fact that each element of the
product is $\F_{p^d}.$ We know that $\F_{p^d}^\star$ is an abelian
group of order $p^d - 1.$ And therefore, for every element $b$ in this
group, $b^{p^d - 1} = 1.$

We need a $-1$, and therefore we look at the square-root of it. Since
we know that $b^{p^d - 1} = 1$, $b^{(p^d - 1)/2} = \sqrt{1}$ which can
either be $1$ or $-1.$\footnote{there can't be any other square-roots
of $1$. This is because square roots of $-1$ satisfy the equation $X^2
- 1 = 0$ and this equation can have only $2$ roots in a field} Let us
just call $(p^d - 1)/2 = M.$\\

Thus, we have a simple procedure. Pick up some random polynomial
$a(X)$ of degree less than $n.$ Check if you are lucky by computing
$gcd(a,f)$ and checking if it is $1.$ Else, compute $a(X)^{(p^d -
1)/2}\bmod{f(X)}$ using repeated squaring. Now if $a$ was mapping to
$(a_1, a_2,\cdots, a_m)$, then $a^M$ would be mapped to
$(a_1^M, \cdots, a_m^M).$ And we just saw that each of $a_i^M$ is
either $1$ or $-1.$ 

\begin{claim}
Each $a_i^M = 1$ with probability $1/2$, and they are independent. 
\end{claim}
\begin{proof}
Since the chinese remainder map is an isomorphism and each $g_i$'s are
distinct, they are clearly independent. To check that the probability
that $b^M=1$ is $1/2$, we look at the following map. 
\bea{
\psi: \F_{p^d}^\star & \longrightarrow & \inbrace{1,-1}\\
b & \longrightarrow & b^M
}
Note that the set $\inbrace{1,-1}$ form a group under
multiplication. Infact it can be identified with the group $\Z/2\Z.$

{\bf Exercise:} Prove that the map $\psi$ is indeed a group
homomorphism.\\

And therefore, the kernel of this map $\psi$ is a subgroup of
$\F_{p^d}^\star$ of all elements $b$ such that $b^m = 1.$ The other
coset of this kernel is the set of elements $b$ such that $b^M = -1.$
Since these two are cosets, they are of equal size. Hence a randomly
chosen $b$ will have $b^M = 1$ with probability $1/2.$
\end{proof}

And therefore, each $a_i$ is $1$ or $-1$ with probability $1/2.$ Thus
the probability that all the coordinates are $1$ or all the
coordinates are $-1$ is just $1/2^m.$ Thus with probability atleast $1
- 2^{m-1}$, we have some vector that has $1$s at certain places and
$-1$s at the rest. Thus, now we are in the case when someone had
secretly told us that some coordinate is $-1.$ 

And therefore, we can pick a random polynomial $a(X)$, raise it to the
power $M$ modulo $f$, and add $1$ to it. With probability atleast $1 - 2^{m-1}$,
this will be a zero-divisor and hence $gcd(a^M + 1,f)$ will be a
non-trivial factor of $f.$

So here is the algorithm:
\begin{algorithm}
\caption{{\sc Cantor-Zassenhaus Algorithm for Factoring}}
\begin{algorithmic}[1]
\REQUIRE A polynomial $f\in \F_p[X]$ of degree $n.$
\IF{$f$ is not square-free}
\STATE {\bf return} the square-free part
\ENDIF
\STATE Compute the distinct degree factors of $f$. Call them
$\inbrace{g_1,g_2, \cdots, g_n}.$
\IF{$g_n\neq 1$}
\STATE {\bf return} {\sc Irreducible}
\ENDIF
\FORALL{$g_i\neq 1$}
\STATE EqualDegreeFactorize($g_i,d$)
\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{{\sc EqualDegreeFactorize}}
\begin{algorithmic}[1]
\REQUIRE A polynomial $f\in \F_p[X]$ of degree $n$ all of whose $m$
irreducible factors are of degree $d.$
\STATE Pick a random polynomial $a(X)$ of degree less than $n.$
\IF{$gcd(a,f)\neq 1$}
\STATE {\bf return} $gcd(a,f)$
\ENDIF
\STATE Let $M = (p^d - 1)/2.$
\STATE Using repeated squaring, compute $a'(X) = a(X)^M + 1.$ 
\IF{$a'\neq 0$ and $gcd(a',f)\neq 1$}
\STATE {\bf return} $gcd(a',f)$
\COMMENT{Happens with probability atleast $1 - 2^{m-1}$}
\ENDIF
\STATE Repeat algorithm with a different choice for $a.$
\end{algorithmic}
\end{algorithm}

\end{document}