\documentclass[10pt]{article} \usepackage{amsfonts} \newtheorem{define}{Definition} %\newcommand{\Z}{{\bf Z}} \usepackage{psfig} \oddsidemargin=0.15in \evensidemargin=0.15in \topmargin=-.5in \textheight=9in \textwidth=6.25in \begin{document} \input{preamble.tex} \lecture{5}{September 26, 2005}{Madhu Sudan}{Elena Grigorescu} In today's lecture we will first go through a brief response to the comments on the previous lecture. The comments and the brief responses will be posted soon. We will continue by introducing methods of polynomial factorization, in particular root finding algorithms in finite fields. \section{ A review of last lecture} In the last lecture we defined Strong Generating Sets (SGS) in a permutation group and we showed an algorithm for building a small-size ($O(n^2)$) SGS of a group $G=$. We then demonstrated an efficient algorithm for testing membership in a permutation group, which was based on the idea that if $\sigma\in G$ then $\sigma$ is the product of polynomially many elements of a SGS of $G$. The motivation for looking at these rather non-intuitive generating sets is that they give a good representation of a group, which in turn leads to good and sometimes unexpected algorithms ( membership seems rather exponential but it turns out not be). Generally, algebraic algorithms exhibit a couple of paradigms that we have already encountered in the concept of SGSs: \begin{enumerate} \item non-intuitive definition \item given an object meeting the definition the problem is easy to solve \item an object meeting the definition exists \item objects meeting the definition can be constructed efficiently. \end{enumerate} It is often the case that for the last two paradigms the proofs are very different. \subsection{ Summary of the membership testing algorithm} Let $\pi$ be a permutation and let $G=$ and $G\leq S_n.$\\ \noindent{\bf BUILD SGS(S):}\\ $T\leftarrow \emptyset;$\\ while $\sigma \in S\cup T\cdot T$ s.t. not MEM-CLOSURE$(\sigma, T)$\\ \indent $T\leftarrow $ ADD-ELEM($\sigma, T$) $\cup T$\\ return T. \\ \noindent{\bf ADD-ELEM($\sigma, T$):}\\ if $\sigma=1$ then return $\sigma$\\ else let $k=k(\sigma); j=\sigma^{-1}(k);$\\ \indent if $\exists \sigma'\in T $ s.t $k=k(\sigma'); \sigma'(j)=k$\\ \indent return ADD-ELEM($\sigma\cdot \sigma'^{-1}, T$)\\ \indent else return $\sigma$.\\ \noindent{\bf MEM-CLOSURE($\sigma, T$}:)\\ if ADD-ELEM($\sigma, T)=1$ return TRUE\\ else return FALSE.\\ \noindent{\bf MEM($\pi, S$:)}\\ $T\leftarrow $BUILD-SGS(S)\\ return MEM-CLOSURE($\pi, T$). \\ We can now move on to a new topic. \section{ Factorization of polynomials - a very simple scenario} INPUT: Integers $a, p$, with $p$ prime;\\ GOAL: Compute $\alpha \in \Z_p$ st $\alpha^2=a$ mod $p$, if $\alpha$ exists.\\ We are first interested in whether $\alpha $ exists, and we will show that the following test decides the existence of a root. {\bf Test:} If $a^{{{p-1}\over 2}}\equiv 1$ then $a$ has a root; else it does not. {\bf Proof:} Suppose $a$ has a root, and $\alpha^2=a$. By Fermat's Little Theorem we have that $\forall \alpha \in \Z_p^*, ~$ $\alpha^{p-1}\equiv 1$ mod $p$. Therefore, $\alpha^{p-1}\equiv a^{{{p-1}\over 2}}\equiv 1$. \noindent In proving the converse, we introduce ideas that will be useful in finding roots of polynomials in more general settings. Suppose that $a^{{{p-1}\over 2}}\equiv 1$ mod $p$. We want to show that $a$ has a root. \noindent Let $p(x)=x^{p-1}-1$, $p_1(x)=x^{{{p-1}\over 2}} -1$ and $p_2(x)=x^{{{p-1}\over 2}} +1$. Thus $p(x)=p_1(x)p_2(x)$. We know that each $\alpha \in \Z_p^*$ is a unique root of $p(x)$ and thus it is a unique root of either $p_1$ or $p_2$. Since for any square $b\in Z_p^*$, $x^2-b$ has exactly 2 roots in $\Z_p^*$, which are distinct, it follows that exactly ${{{p-1}\over 2}}$ elements in $\Z_p^*$ are squares. We also know that each of these squares are roots of $p_1(x)$, and since the degree of $p_1(x)$ is ${{{p-1}\over 2}}$, it follows that the squares in $\Z_p^*$ are the only roots of $p_1(x)$. This concludes the proof.\\ We can now try and find the square roots of $a$ when they exist. When $p$ is an odd prime we distinguish two cases, namely $p\equiv 3 $ mod $4$ for which we will give a deterministic algorithm, and $p\equiv 1$ mod $4$ for which we give a randomized algorithm that determines the roots.\\ {\it Case 1:} $p\equiv 3$ mod $4$\\ \noindent As before, let $p(x)=x^{p-1}-1=p_1(x)p_2(x)$, $p_1(x)=x^{{{p-1}\over 2}} -1$ and $p_2(x)=x^{{{p-1}\over 2}} +1$. We claim that \\ \noindent $x-\alpha \mid p_1(x),$ and \\ \noindent $x+\alpha \mid p_2(x).$ \noindent To see this, notice that since ${{{p-1}\over 2}}$ is odd, we have that $\alpha^{{{p-1}\over 2}}$ and $(-\alpha)^{{{p-1}\over 2}}$ have different signs. Thus, each of them are roots of only one of $p_1(x)$ and $p_2(x)$, which proves the claim. \noindent From the argument above we can deduce that $gcd( x^2-a, x^{{{p-1}\over 2}} -1)=x-\alpha$. Therefore, in order to compute $\alpha$ we only need to compute the above $gcd$, which only takes polynomial time in the smallest degree ($=2$). \\ {\it Case 2:} $p\equiv 1$ mod $4$ \noindent Consider the more general setting of finding roots of a polynomial of the form $g(x)=x^2-Ax-B=(x-\beta)(x-\gamma).$ If $\beta$ and $\gamma$ are random and independent elements of the field, then the $gcd( g(x), x^{{{p-1}\over 2}}-1)$ is of degree 1 when only one of $\beta$ and $\gamma$ are roots of $p_1(x)$. Since the size of the field is $p$ we can conclude that the probability of finding a linear factor of $g(x)$ is about $1/2$. We would now like to be able to map $\alpha$ and $-\alpha$ into $\beta$ and $\gamma$ respectively, such that we could apply this approach to finding the roots of $a\in \Z_p^*$. Notice that there exist $c$ and $d$ s.t. $c\alpha+d=\beta$ and $c(-\alpha)+d=\gamma$. To make $\beta$ and $\gamma$ random and independent, we only need to pick $c\not=0$ and $d$ randomly and independently of each other. We can deduce that $x^2-Ax-B=(x-\beta)(x-\gamma)=(x-(c\alpha+d))(x-(c(-\alpha)+d))=(x-d)^2-c^2a$. The promised algorithm follows.\\ {\bf SQ-ROOT(p, a):}\\ 1. If $a=0$ return 0; If $a^{{{p-1}\over 2}}\equiv -1$ return `none exists';\\ 2. Pick $c\in \Z_p^*$ and $d\in \Z_p$ at random\\ 3. Compute $q(x)=gcd( (x-d)^2-c^2a, x^{{{p-1}\over 2}}-1)$\\ 4. If $q(x)=x-\beta$ return $\pm {{\beta -d }\over c}$;\\ 5. Else go to 2.\\ As before,\\ $$Pr_{c\in \Z_p^*, d\in \Z_p}[ gcd( (x-d)^2-c^2a, x^{{{p-1}\over 2}}-1) \mbox{ is linear }]=$$ $$Pr_{c\in \Z_p^*, d\in \Z_p}[ gcd( (x-(c\alpha+d))(x-(c(-\alpha)+d), x^{{{p-1}\over 2}}-1)\mbox{ is linear }] \approx 1/2,$$ since $c\alpha+d$ and $c(-\alpha)+d$ are random and distinct elements of $\Z_p$. By repeating the algorithm, the success probability can be made arbitrarily large, which concludes the analysis. \section{Generalization - Roots modulo p of higher degree polynomials } INPUT: $p$ prime, $c_0, c_1, \ldots, c_n\in \Z_p$, $f(x)=\sum c_i x^i$.\\ GOAL: Find all $\alpha$ s.t. $x-\alpha \mid f(x)$. \\ We can assume W.l.o.g. that $f(x)$ has distinct linear factors. Otherwise, given a root $\alpha$ one could check in various ways if $(x-\alpha)^2 \mid f(x)$. As an exercise, show that if $(x-\alpha^2)\mid f(x)$ then $x-\alpha \mid gcd(f, f')$ ( note that the derivative $f'=\sum i c_i x^{i-1} \mbox{ mod }p~$ is a formal definition). From now on assume $f(x)=\sum c_i x^i=\Pi (x-\alpha_i)$ is st. $\alpha_i's$ are distinct. Notice that if $\alpha$ is a root of $f(x)$ then it is also a root of $x^p-x$, and thus, w.p. $\approx 1/2$, $\alpha$ is a root of $p_1(x)=x^{{{p-1}\over 2}}-1$. The goal of splitting $f(x)$ leads us into considering $q(x)=gcd(f(x), x^{{{p-1}\over 2}}-1)$. However, this approach will work only if not all of the roots of $x^{{{p-1}\over 2}}-1$ are also roots of $f$. The solution to this is that we can use randomization as we did in the square-root algorithm. Thus, map $\alpha_i$ into random $\beta_i$. We might not be able to get the independence of the $\beta_i$'s, but we are only interested in splitting the polynomial once. Therefore, it is enough to focus only on random $\beta_1$, and $\beta_2$. With random $c, d$ we could map $f(x)=\Pi (x-\alpha_i)$ into $\tilde{f}(x)=\Pi (x-(c\alpha_i+d))$. Then $\tilde{f}(x)=\Pi (x-(c\alpha_i+d))=c^n \Pi({{x-d}\over c} -\alpha_i)=c^n f({{x-d}\over c})$. If we found a root of $\tilde{f}$ we can therefore find a root of $f$. We are now ready to present the algorithm.\\ {\bf ROOT-FIND( $f(x)=\sum c_i x^i)$:}\\ 1. $f(x)\leftarrow gcd(x^p-x, f(x))$\\ 2. Pick $c\in \Z_p^*, d\in \Z_p$ at random\\ 3. $\tilde{f}(x)\leftarrow c^n f({{x-d}\over c})$\\ 4. If $\tilde{q}(x)=gcd(\tilde{f}(x), x^{{{p-1}\over 2}}-1)$ is non-trivial (not n)\\ \indent return ROOT-FIND($q(x)={1\over c^n}\tilde{q}(c x+d)$), ROOT-FIND ( ${f(x)\over q(x)}$).\\ Notice that the above algorithm only uses the fact that $p$ is odd, so $p$ does not necessarily need to be prime. The algorithm is due to Berlekamp, 1972 and it is probably the first algorithm in the literature that uses randomization. No deterministic such algorithm is known of. \\ In future lectures we will be dealing with the factorization of polynomials over even fields and with the factorization of polynomials into irreducible polynomials of degree higher than linear.\\ We conclude the lecture with the following exercise.\\ Given $\beta_1, \ldots, \beta_n\in \Z_p$, define the $k$'th symmetric function in $\{\beta_1, \ldots, \beta_n\}$ as $$\sigma(\beta_1, \ldots, \beta_n)=\sum_{S\subset [n], |S|=k} \Pi_{i\in S}\beta_i.$$ Compute $\sigma( \beta_1, \ldots, \beta_n)$ efficiently. \end{document}