\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{23 and 24 : The Cyclotomic Polynomial }{CS681}{Piyush P Kurur}{Ramprasad Saptharishi} \section*{Overview} We started looking at the AKS primality test in the last class. The idea was to check if $(X+a)^n - X^n - a = 0 \pmod{n,X^r - 1}$ for many values for $a.$ We first need to understand the polynomial $X^r - 1$ and extensions associated with it. \section{The polynomial $X^r - 1=0$} The roots of this polynomial are the $r$-th roots of unity. Over $\Q$ these are the complex numbers $e^{\frac{2\pi i}{r}}$ where $0\leq i\leq r-1.$ Note that the roots of unity form a group under multiplication. If $\zeta_1$ and $\zeta_2$ are roots, then so is $\zeta_1\zeta_2.$ Infact, it forms a cyclic group. And therefore, we can talk about a generator of this group. \begin{definition} An $r$-th root of unity $\zeta$ is called a primitive $r$-th root of unity if $\zeta$ is a generator of the group of roots. \end{definition} Or in other words, $\zeta$ is a number such that $\zeta^r = 1$ and $\zeta^t \neq 1$ for any $t<r.$ Now, let $\zeta$ be a primitive $r$-th root of unity. What are the other primitive roots? Any other root $\zeta'$ can be written as $\zeta^t.$ Suppose the $\gcd(r,t) = d$ then look at $\zeta'^{r/d}.$ Since $d$ divides $r$, the exponent is an integer. $$ \zeta'^{r/d} = \zeta^{tr/d} = (\zeta^r)^{t/d} = 1 $$ Therefore, the primitive $r$-th roots of unity are $\zeta^t$ where $t$ is coprime with $r.$ And therefore, there are $\varphi(r)$ of them. Let us consider the following polynomial: $$ \Phi_r(X) = \prod_{\zeta \text{ primitive}}(X-\zeta) $$ This is called the $r$-th cyclotomic polynomial. Clearly, the degree of $\Phi_r(X)$ is $\varphi(r).$ \subsection{Cyclotomic Polynomials over $\Q$} Let us restrict our attention to the field of rational numbers. We want to study $\prod(X - \zeta).$ The first important property is the following: \begin{proposition} The coefficients of $\Phi_r(X)$ are rational numbers. \end{proposition} \begin{proof} The idea is quite simple. The equation $X^r - 1$ has all the $r$-th roots of unity as roots and certainly includes the primitive roots as well. Therefore, $\Phi_r(X)$ divides $X^r - 1.$ So the idea is to eliminate all the non-primitive roots of unity. Note that since the roots of unity form a group under multiplication, for any root of unity $\zeta$ the order of $\zeta$ divides $r.$ So the order could either be $r$ or some proper factor of $r.$ We are interested in only the $\zeta$s whose order is equal to $r.$ For every $\zeta$, if the order of $\zeta$ is $t$, then $t\mid r$ and $\zeta$ is a root of $\Phi_t(X)$ by definition. And running over all the roots of unity, we have $$ X^r - 1 = \prod_{d\mid r}\Phi_d(X) $$ And therefore, $$ \Phi_r(X) = \frac{X^r - 1}{\prod_{d\mid r, d\neq r}\Phi_d(X)} $$ By induction, if we assume that $\Phi_d(X)$ has rational coefficients, for all $d<r$, it follows that $\Phi_r(X)$ has rational coefficients too. \end{proof} To see a few examples, \begin{enumerate} \item $\Phi_1(X) = X-1$ \item $\Phi_2(X) = \frac{X^2 - 1}{X-1}= X+1$ \item $\Phi_3(X) = \frac{X^3 - 1}{X-1} = X^2 + X + 1$ \item $\Phi_4(X) = \frac{X^4 - 1}{(X+1)(X-1)} = X^2 + 1$ \end{enumerate} And if you notice, the coefficients are not only rationals but infact integers. This can be got from the earlier proof using the following very useful lemma. \begin{lemma}[Gauss Lemma] Let $f$ be a monic polynomial with integer coefficients. If $f$ is irreducible in $\Z$, that is there are no polynomials $g,h$ with integer coefficients such that $f(X) = g(X)h(X)$, then $f$ is irreducible over $\Q$ as well. \end{lemma} Therefore if $f$ and $g$ are integer monic polynomials such that there $g$ divides $f$ over $\Q$, that is there exists a polynomial $h$ with rational coefficients such that $f(X) = g(X)h(X)$, the $g$ infact divides $f$ over $\Z$ or $h$ infact has only integer coefficients. Thus all the above divisions will only yeild integer polynomials and hence $\Phi_r(X)$ is an integer polynomial.\\ Another important property of cyclotomic polynomials is that they are irreducible over $\Q.$ We shall prove this soon. But what's important is that it needn't be so in the case of finite fields. For example, if $r = p-1$ and we looked at $\Phi_r(X)$ in $\F_p.$ Note that $\Phi_r(X)$ is a factor of $X^r - 1 = X^{p-1}-1$ which inturn is a factor of $X^p - X$ and this completely splits. However, if we can show that $\Phi_r(X)$ was irreducible over some prime $p$, then it has to be irreducible over $\Q.$ Because if it were reducible as $f(X)\cdot g(X)$ over $\Q$, then we can reduce the equation $\Phi_r(X) = f(X)g(X)\bmod{p}$ and get a factorization in $\F_p.$ \subsection{Cyclotomic polynomials over $\F_p$} Let $\zeta$ be a primitive $r$-th root of unity over $\F_p.$ Note that $\zeta$ could very well be in $\F_p$ itself; when $r = p-1$ for example. In any case, consider the field extensio $\F_p(\zeta)$ over $\F_p$ by just adjoining $\zeta$ to $\F_p.$ Let us say the degree of this extension $[\F_p(\zeta):\F_p] = d.$ Recall that the degree of a field extension $[K(\alpha):K]$ is the degree of the $K(\alpha)$ as vector space over $K$ and therefore is equal to the degree of the minimum polynomial of $\alpha$ over $K.$ Therefore, if $\mu(X)$ is the minimum polynomial of $\zeta$ over $\F_p$, $\mu(\zeta) = a_0 + a_1\zeta + \cdots a_d\zeta^d = 0$ and therefore the set $1,\zeta,\zeta^2, \cdots, \zeta^{d-1}$ is the largest linearly independent subset. Therefore, $[\F_p(\zeta):\F_p] = \deg{\mu(X)} = d.$ Now, $\zeta$ is a root. What about the other roots of this polynomial? Recall our old friend Fr\"{o}benius. The automorphism $a\mapsto a^p$ fixes every element in $\F_p.$ \bea{ \mu(\zeta) & = & a_0 + a_1\zeta + \cdots + a_d\zeta^d = 0\\ \implies (\mu(X))^p & = & 0\\ & = & \inparen{a_0 + a_1\zeta + \cdots + a_d\zeta^d}\\ & = & a_0^p + a_1^p\zeta^p + \cdots + a_d^p\zeta^{dp}\\ & = & a_0 + a_1\zeta^p + \cdots + a_d(\zeta^p)^d\\ & = & \mu(\zeta^p) } and hence, $\zeta^p$ is also a root. Applying the map again, we can show $\zeta, \zeta^p, \zeta^{p^2}, \cdots, \zeta^{p^{d-1}}$ are all roots of $\mu(X).$ One can't go up to more than $d$ such applications because the degree of $\mu$ is bounded by $d$ and therefore can have only $d$ roots. And if we were to apply the Fr\"{o}benius map again, then we would end up in $\zeta$ again. Or in other words, $$ \zeta^{p^d} = \zeta \implies \zeta^{p^d - 1} = 1 \implies r\mid p^d - 1\implies p^d = 1\bmod{r} $$ Since $d$ was the first place where this sort of wraparound happened, $d$ is the least such number such that $p^d = 1\bmod{r}$ which implies that $d$ is the order of $p$ modulo $r$. This is denoted by $d = ord_r(p)$. Thus, the degree of the the minimum polynomial of $\zeta$ over $\F_p$ for any primitive $r$-th root is $ord_r(p).$ And since we just specified $\zeta$ as any primitive root, it follows that every primitive root has the degree of its minimum polynomial as $ord_r(p).$ \\ But with a little thought, this will tell us that the approach that $\Phi_r(X)$ is irreducible in $\F_p$ for some $p$ may not work. Suppose this was true, then the minimum polynomial of $\zeta$ must infact be $\Phi_r(X).$ And from what we have proved above, the degree of this polynomial must be $ord_r(p)$ and therefore $\varphi(r) = ord_r(p).$ Now notice that if we consider $\inparen{\Z/r\Z}^\star$, then the size of this group is $\varphi(r)$ and if $ord_r(p) = \varphi(r)$, then $p$ generates the group $\inparen{\Z/r\Z}^\star.$ But not all $(\Z/n\Z)^\star$s are cyclic and therefore such a $p$ may not exist at all. But let us just take it on faith that the cyclotomic polynomial is irreducible. The proof is not hard but would be a significant digression. The interested reader can look it up online or on any abstract algebra text. But what is important that any primitive $r$-th root has a minimum polynomial of degree $ord_r(p)$ in $\F_p.$ \section{AKS Primality Test: A sketch} Now we have enough machinary to go ahead with the primality test. The algorithm would be the following: \begin{enumerate} \item Find two numbers $r$ and $l$ based on some requirements \item Do some small preprocessing \item For all $1\leq a\leq r,$ check if the following identity holds $$ (X+a)^n = X^n + a \pmod{n,X^r - 1} $$ Use repeated squaring to evaluate the LHS and RHS and check. If any of the test failed, output {\sc composite}. \item If all the above tests succeeded, output {\sc prime} \end{enumerate} Our preprocessing steps would be the following: \begin{itemize} \item Check if $n$ is a perfect power of some number. If it is some non-trivial power, output {\sc composite.} This will rule out the case that $n = p^k$ for $k\geq 2.$ \item For each $2\leq d\leq r$, check if $\gcd(n,d)=1.$ If you find a factor, output {\sc composite.} \end{itemize} And the parameters will be fixed soon and we shall see that both $r$ and $l$ are less than $(\log n)^c$ for some constant $c.$ Therefore, the preprocessing steps take only polylog time, checking if the identity holds for each $a$ in that range also takes polylog time and therefore the entire algorithm runs in time polynomial in $\log n.$ Further, if $n$ was indeed a prime, the algorithm would definitely output {\sc prime.} The tricky part is to show that if $n$ had atleast $2$ distinct prime factors, the algorithm will catch it. \\ To prove the correctness of this algorithm, we would be studying $2$ rings: \begin{itemize} \item $R = \frac{\Z[X]}{(n,X^r - 1)} = \inparen{\Z/n\Z[X]}/(X^r - 1)$ \item $R = \frac{\Z[X]}{(p,h(X))} = \inparen{\Z/p\Z[X]}/(h(X))$ where $p$ is a prime factor of $n$ and $h(X)$ is an irreducible factor of $\Phi_r(X)$ over $\F_p.$ Note that we have shown that $t = \deg(h(X)) = ord_r(p).$ \end{itemize} Suppose the algorithm said $n$ was a prime even when it had $p$ as a prime factor of $n$. What we would do is construct a group $\mathcal{G}$ and get bounds on the size of $\mathcal{G}$ in two different ways. We will show that $|\mathcal{G}|\geq \binom{t+l}{t-1}.$ And also, if $n$ had at least $2$ distinct prime factors, then $|\mathcal{G}| \leq n^{\sqrt{t}}.$ Thus, unifying the two, we have $$ \binom{t+l}{t-1} \leq \mathcal{G} \leq n^{\sqrt{t}} $$ And then, with suitable choice of $r$ and $l$, we shall show that the lower bound is larger than the upper bound which would give the required contradiction. That is the general idea. \\ We shall see this in detail in the next class. \end{document}