ubuntu2004-eol
| Problem: | Given a polynomial $f\in \mathbb F_q[x]$, determine the $\mathbb F_q$-rational roots of $f$. |
| Solution: | Rabin's algorithm! |
| Theorem: | $\mathbb F_{p^n} = \{\alpha\in \overline{\mathbb F}_p: \alpha^{p^n}=\alpha\}$, in other words, we have $$x^{p^n}-x=\prod_{\alpha\in \mathbb F_{p^n}}(x-\alpha)$$ |
| Proof: | For $n=1$ this follows from Fermat's little theorem. If we identify $\mathbb F_p\simeq \mathbb Z/p\mathbb Z$, we have $a^{p-1}=1\bmod p$ for $a\in [0,p-1]$, so the $p$ elements of $\mathbb Z/p\mathbb Z$ are precisely the roots of $x^p-x$. For $n>1$ this is true by definition: $\mathbb F_{p^n}:=\overline{\mathbb{F}}_{p}^{\langle \alpha \mapsto \alpha^{p^n}\rangle}$ is the fixed field of the $p^n$-power Frobenius automorphism of $\overline{\mathbb F}_p$, equivalently, the splitting field of $x^{p^n}-x$ over $\mathbb F_p$. |
| Corollary: | For any prime power $q$ we have $\mathbb F_{q^n} = \{\alpha\in \overline{\mathbb F}_q: \alpha^{q^n}=\alpha\}$ and $x^{q^n}-x=\prod_{\alpha\in \mathbb F_{q^n}}(x-\alpha)$. |
| Corollary: | Let $f\in \mathbb F_q[x]$ be nonzero and let $S:=\{\alpha\in \mathbb F_{q^n}:f(\alpha)=0\}$. Then $$\gcd(f(x),x^{q^n}-x)=\prod_{\alpha\in S}(x-\alpha).$$ In particular, $\#S=\deg(\gcd(f(x),x^{q^n}-x)$. |
| Key point: | Make sure you exponentiate in the right ring! The first step in computing $\gcd(f(x),x^q-x)$ is to compute $x^q-x\bmod f$ (note that $q$ may be exponentially large, but $\deg f$ certainly won't be). If $\pi_f\colon \mathbb{F}_q[x]\to\mathbb{F}_q[x]/(f)$ is the ring homomorphism defined by $x\mapsto x\bmod f$, then $$\pi_f(x^q-x)=\pi_f(x^q)-\pi_f(x)=\pi_f(x)^q-\pi_f(x),$$ so the order of operations makes no mathematical difference, but the RHS can be computed exponentially faster than either the middle or the LHS! The complexity of computing $x^q\bmod f$ with Euclidean division is quasi-linear in $q$, The complexity of computing $\pi_f(x)^q$ using binary exponentiation is quasi-linear in $\log q$. |
Okay, we can count (distinct) roots, but what if we actually want to know what they are?
Excellent, we managed to split the roots of $f$ by picking out two that are roots of $x^s-1$, where $s=(q-1)/2$ (we are assuming $q$ is odd).
What are the roots of $x^s-1$ anyway?
My keen sense of pattern recognition (or a recollection of Euler's criterion) tells me these are the roots of $x^s-1$ are precisely the squares (quadratic residues) in $\mathbb F_p^\times.$
But if $f$ has multiple roots that are quadratic residues (or maybe none), then what?
Rabin: Instead of $x^s-1$, use $(x+\delta)^s-1$ for a random $\delta\in \mathbb F_q$.
| Definition: | Let us say that $\alpha,\beta\in \mathbb F_q$ are of different type if both are nonzero and $\alpha^s\ne \beta^s$, in other words, one is a quadratic residue and one is not. |
| Theorem: | For every pair of distinct $\alpha,\beta\in \mathbb F_q$ we have $$\#\{\delta\in \mathbb F_q:\alpha+\delta \text{ and } \beta+\delta \text{ are of different type }\} = \frac{q-1}{2}.$$ |
| Proof: | See Section 3.11 in the lecture notes for a short easy proof. |
| Corollary: | Let $f\in \mathbb F_q[x]$, let $g(x)=\gcd(f,x^q-x)$, let $s=(q-1)/2\in \Z$, and let $\delta$ be a uniformly random element of $\mathbb F_q$. If $g$ has more than one nonzero root, then $$\Pr[0<\deg\gcd(g,(x+\delta)^s-1)<\deg g] \ge \frac{1}{2}.$$ |
| Theorem: | Let $n=\log q$ and $d=\deg f$. The expected running time of $\texttt{rational\_root}$ is $\tilde O(n^2d)$ bit operations. |
Here the soft-O notation means up to a poly-logarithmic factors. See the lecture notes for a more precise bound and a proof.
What if we want all the rational roots?
| Theorem: | Let $n=\log q$ and $d=\deg f$. The expected running time of $\texttt{distinct\_rational\_root}$ is $\tilde O(n^2d)$ bit operations. |
This looks the same as the bound for $\texttt{rational\_root}$, but in fact there is an extra factor of $\log d$ hidden in the soft-O notation.
What if we want all the rational roots and their multiplicities?
Yun: Compute the squarefree factorization!
| Definition: | The squarefree factorization of a monic $f\in \mathbb F_q[x]$ is the unique list of monic squarefree polynomials $g_1,\ldots,g_m$ with $g_m\ne 1$ for which $f=g_1g_2^2\cdots g_m^m$. |
| Key fact: | If $f=f_1\cdots f_n$ is the factorization of a monic $f\in \mathbb F_q[x]$ into irreducibles then $f_i=f_j$ for some $i\ne j$ if and only if $f_i|\gcd(f,f')$. This holds in any perfect field. |
| Theorem: | Let $n=\log q$ and $d=\deg f$. The running time of $\texttt{squarefree\_factorization}$ is $\tilde O(nd)$ bit operations. |
This is negligible compared to the complexity of $\texttt{distinct\_rational\_roots}$, so we might as well call $\texttt{squarefree\_factorization}$ first.
Even if we only want distinct roots, this will actually save time if $f$ is not squarefree.
What if we want to factor $f$ into irreducibles?
Rabin: You can do that with my root-finding algorithm.
Cantor-Zassenhaus: Yes, but that requires working in extension fields, and with our algorithm there is no need!
The first step is to compute the distinct degree factorization
| Definition: | The distinct degree factorization of a monic $f\in \mathbb F_q[x]$ is the unique list of polynomials $g_1,\ldots,g_d$ with $f=g_1\cdots g_d$ such that each $g_i$ is a (possibly empty) product of distinct monic irreducible polynomials of degree $i$, for $1\le i\le d=\deg f$. |
| Key point: | This can be done deterministically by taking succesive gcds with $x^{q^i}-x$. |
The key innovation introduced by Cantor-Zassenhaus is that when searching for irreducible factors $g$ of $f$ of degree $j$, rather than computing $\gcd(f,(x+\delta)^s-1))$ using a random $\delta\in \mathbb F_{q^j}$ and computing the gcd in $\mathbb F_{q^j}[x]$ (which is how one would go about finding a root of $g$ using Rabin's algorithm), it is better to compute $\gcd(f,u^s-1)$ in $\mathbb F_q[x]$ using a random $u\in \mathbb F_q[x]$ coprime to $f$ with $\deg u < \deg f$. This faster because we are working the ring $\mathbb F_q[x]/(f)$ rather than $\mathbb F_{q^j}[x]/(f)$ (so the bit-size of each element is smaller by a factor of $j$), and the probability of success is the same.
| Theorem: | Let $f\in \mathbb F_q[x]$ be the product of $r\ge 2$ distinct monic irreducible polynomials of degree $j$ and let $u\in \mathbb F_q[j]$ be a random polynomial coprime to $f$ with $\deg u < \deg f$. Then $$\Pr[0<\deg\gcd(f,u^s-1)<\deg f] = 2^{1-r} \ge \frac{1}{2}.$$ |
| Proof: | This follows from applying the Chinese Remainder Theorem to $\mathbb F_q[x]/(f)\simeq \mathbb F_{q^j}^r$. See Section 3.12 of the lecture notes for details. |
| Theorem: | Let $n=\log q$ and $d=\deg f$. The expected running time of $\texttt{factorization}$ is $\tilde O(n^2d^2)$ bit operations. |
There are other factorization methods based on linear algebra and modular composition that improve the dependence on $d$.
Currently the best asymptotic bound is achieved by the Kedlaya-Umans algorithm with an expected running time of $\tilde O(d^{3/2}n + dn^2)$.