| Problem: | \n", "Given a polynomial $f\\in \\mathbb F_q[x]$, determine the $\\mathbb F_q$-rational roots of $f$. | \n", "
| Solution: | \n", "Rabin's algorithm! | \n", "
| Theorem: | \n", "$\\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: | \n", "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$. \n", " 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$. | \n",
"
| Corollary: | \n", "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)$. | \n", "
| Corollary: | \n", "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! \n", "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). \n", " 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$, \n", " 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?
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "gcd(f,(pif(x)^p-x).lift())" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "s = (p-1) // 2 # we assume p (or more generally q) is odd\n", "gcd(f,(pif(x)^s-1).lift())" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "print(gcd(f,(pif(x)^p-x).lift())/gcd(f,(pif(x)^s-1).lift()))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "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).
\n",
" 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.$
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "product([x-a^2 for a in F if a < p-a]) == (x^s-1)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "But if $f$ has multiple roots that are quadratic residues (or maybe none), then what?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "Rabin: Instead of $x^s-1$, use $(x+\\delta)^s-1$ for a random $\\delta\\in \\mathbb F_q$.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "| Definition: | \n", "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. | \n", "
| Theorem: | \n", "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}.$$ | \n", "
| Proof: | \n", "See Section 3.11 in the lecture notes for a short easy proof. | \n", "
| Corollary: | \n", "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}.$$ | \n",
"
| Theorem: | \n", "Let $n=\\log q$ and $d=\\deg f$. The expected running time of $\\texttt{rational\\_root}$ is $\\tilde O(n^2d)$ bit operations. | \n", "
Here the soft-O notation means up to a poly-logarithmic factors. See the lecture notes for a more precise bound and a proof.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "for i in range(5):\n", " r = rational_root(f)\n", " print(\"Found root %s\\n\" % r)\n", " assert f(r) == 0\n" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "h = product([x-i for i in range(1,20)])\n", "for i in range(5):\n", " r = rational_root(h)\n", " print(\"Found root %s\\n\" % r)\n", " assert h(r) == 0\n" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "p=2^61-1; F=GF(p); R.What if we want all the rational roots?
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "def distinct_rational_roots(f,recurse=False):\n", " \"\"\"Returns a list of all the distinct rational roots of f.\"\"\"\n", " q = f.base_ring().cardinality()\n", " assert q % 2 == 1\n", " s = (q-1) // 2\n", " x = f.parent().gen()\n", " roots = []\n", " if recurse:\n", " g = f\n", " else:\n", " g = distinct_root_poly(f)\n", " if g(0) == 0:\n", " roots = [g.base_ring()(0)]\n", " g = g // x\n", " if g.degree() <= 1:\n", " return [-g[0]] if g.degree() == 1 else []\n", " while True:\n", " delta = g.base_ring().random_element()\n", " pig = g.parent().quotient(g)\n", " h = gcd(g, ((pig(x)-delta)^s-1).lift())\n", " if 0 < h.degree() < g.degree():\n", " roots += distinct_rational_roots(h, True)\n", " roots += distinct_rational_roots(g//h, True)\n", " return roots\n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "| Theorem: | \n", "Let $n=\\log q$ and $d=\\deg f$. The expected running time of $\\texttt{distinct\\_rational\\_root}$ is $\\tilde O(n^2d)$ bit operations. | \n", "
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.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "%time distinct_rational_roots(f)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "%time distinct_rational_roots(product([x-F.random_element() for i in range(10)]))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "What if we want all the rational roots and their multiplicities?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "Yun: Compute the squarefree factorization!
\n", "\n", "| Definition: | \n", "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$. | \n", "
| Key fact: | \n", "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. | \n",
"
| Theorem: | \n", "Let $n=\\log q$ and $d=\\deg f$. The running time of $\\texttt{squarefree\\_factorization}$ is $\\tilde O(nd)$ bit operations. | \n", "
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?
\n", "Rabin: You can do that with my root-finding algorithm.
\n", "Cantor-Zassenhaus: Yes, but that requires working in extension fields, and with our algorithm there is no need!
\n", "The first step is to compute the distinct degree factorization
\n", "| Definition: | \n", "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$. | \n", "
| Key point: | \n", "This can be done deterministically by taking succesive gcds with $x^{q^i}-x$. | \n", "
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.
\n", "| Theorem: | \n", "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}.$$ | \n", "
| Proof: | \n", "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. | \n", "
| Theorem: | \n", "Let $n=\\log q$ and $d=\\deg f$. The expected running time of $\\texttt{factorization}$ is $\\tilde O(n^2d^2)$ bit operations. | \n", "
There are other factorization methods based on linear algebra and modular composition that improve the dependence on $d$.
\n",
"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)$.