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