{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Factoring Polynomials\n",
"\n",
"In this handout we cover how to factor polynomials—in particular, we give a polynomial time algorithm for factoring polynomials whose coefficients are in a finite field. That is, given an $\\renewcommand{\\F}{\\mathbb{F}}f\\in\\F_q[x]$, write it as the decomposition\n",
"\n",
"\\begin{equation*} f = f_1\\cdot f_2\\dotsb f_n \\end{equation*}\n",
"\n",
"where $f_1$, $\\dotsc$, $f_n$ are irreducible polynomials. An _irreducible_ polynomial is one that cannot be written as a nontrivial product, i.e., $f$ is irreducible exactly when $f=gh$ implies at least one of $g$ and $h$ are a constant polynomial. Because the coefficients are from a field, all of the leading coefficients of the polynomials $f_i$ are invertible. Thus, one can write the decomposition as\n",
"\n",
"\\begin{equation*} f = c f_1\\cdot f_2\\dotsb f_n \\tag{$*$} \\end{equation*}\n",
"\n",
"where $c\\in\\F_q$ and all the $f_i$ are _monic_ (have a leading coefficient of 1).\n",
"We consider the factorization problem as finding the decomposition ($*$) given $f$.\n",
"By dividing both sides by $c$ we also make the leading coefficient on the left-hand side also 1. Thus, without loss of generality we will assume that the $f$ to factor is monic.\n",
"\n",
"Throughout this handout the reader can think of $\\F_q$ as being $\\renewcommand{\\Z}{\\mathbb{Z}}\\Z_p$ (i.e., the field of residues modulo a prime $p$), as $\\Z_p$ is the simplest kind of finite field. However, the algorithms we discuss will also work in general finite fields $\\F_q$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Roadmap\n",
"\n",
"We will break the problem of factoring $f\\in\\F_q[x]$ into various special cases. One important special case is to handle the case when $f$ is _squarefree_, meaning that in the decomposition $f=\\prod_i f_i$ all of the $f_i$ are distinct. That is, a polynomial is squarefree when it is not divisible by the square any polynomial (except constant polynomials). For example, $f=(x+1)^2$ is not squarefree and $f=(x+1)(x-1)$ is squarefree over any field $\\Z_p$ with $p>2$.\n",
"\n",
"A second special case of the factoring problem is to $f$ into _distinct-degree factors_, i.e., write $f$ as\n",
"$f = g_1\\dotsb g_n$ where $g_i$ is the product of all irreducible factors of degree $i$. For example, if $f=(x+1)^2(x-1)(x^2+3)(x^3+x+1)\\in\\F_5[x]$ then $g_1=(x+1)^2(x-1)$, $g_2=x^2+3$, $g_3=x^3+x+1$, and $g_4=\\dotsb=g_8=1$.\n",
"\n",
"The third special case is to factor the $g_i$ that appear in the distinct-degree factorization. That is, given a $g_i\\in\\F_q[x]$ of degree $d$ whose irreducible factors are all guaranteed to be of a known degree $i$ (and hence there must be $d/i$ of them), find all $d/i$ irreducible factors $g_i=h_1\\dotsm h_{d/i}$. For example, given $g_1=x^3+x^2-x-1\\in\\F_5[x]$ (which is a product of only linear factors), find its decomposition into linear factors $g_1=(x+1)^2(x-1)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Distinct-degree Factorization\n",
"\n",
"First, we consider the problem of taking a squarefree monic $f\\in\\F_q[x]$ of degree $n$ and writing it as the product $g_1\\dotsm g_n$ where $g_i$ is the product of the irreducible polynomials of degree $i$ dividing $f$.\n",
"Our algorithm for doing this will be based on a generalization of Fermat's little theorem in $\\F_q[x]$.\n",
"\n",
"### Fermat's Little Theorem\n",
"\n",
"Recall Fermat's little theorem says if $p$ is prime then $a^p\\equiv a\\pmod{p}$, i.e., all $a\\in\\Z_p$ are roots of the polynomial $x^p-x\\in\\Z_p[x]$. In fact, over general finite fields $\\F_q$ one still has that all $a\\in\\F_q$ are roots of $x^q-x$. Thus, Fermat's little theorem can equivalently be written as\n",
"\n",
"\\begin{equation*} x^q-x=\\prod_{a\\in\\F_q}(x-a). \\end{equation*}\n",
"\n",
"Thus, given $f$ one can compute $g_1$, the product of all linear factors of $f$, via $g_1:=\\gcd(f,x^q-x)$.\n",
"\n",
"Generalizing this, one can also show that\n",
"\n",
"\\begin{equation*} x^{q^2}-x = \\prod_{\\substack{\\alpha\\in\\F_q[x],\\text{ irred.}\\\\\\deg(\\alpha)\\leq2}}\\alpha(x) . \\end{equation*}\n",
"\n",
"In follows that once the linear factors of $f$ have been removed (by dividing by $g_1$) one can find $g_2$, all the quadratic factors of $f/g_1$, via $g_2:=\\gcd(f/g_1,x^{q^2}-x)$.\n",
"\n",
"This process can be generalized; the proper generalization of Fermat's last theorem that enables finding all irreducible factors of degree $d\\geq1$ is\n",
"\n",
"\\begin{equation*} x^{q^d}-x = \\prod_{\\substack{\\alpha\\in\\F_q[x],\\text{ irred.}\\\\\\deg(\\alpha)\\mid d}}\\alpha(x) . \\end{equation*}\n",
"\n",
"Once all factors of $f$ less than degree $d$ have been removed from $f$ (via $f\\cdot\\prod_{i2N$. Using the \"symmetric range\" $\\{-(p-1)/2,\\dotsc,(p-1)/2\\}$ of residues mod $p$, we can capture all of $\\alpha$'s coefficients exactly mod $p$, and therefore will be able to recover the $\\alpha$ from $\\bar\\alpha$.\n",
"\n",
"So by taking $p$ large enough we will be able to recover the coefficients of the factors of $f$ from their modular reductions—if we can compute their modular reductions. Say $f_1$ is an irreducible factor of $f$. Since $f\\bmod p$ can only factor _farther_ than $f$, it must be the case that some product of the $g_i$s in ($**$) must combine in order to give $f_1$, i.e., there is a set $S\\subseteq\\{1,\\dotsc,k\\}$ such that\n",
"\n",
"\\begin{equation*} f_1 = \\prod_{i\\in S} g_i . \\end{equation*}\n",
"\n",
"If we can find the set $S$ then we would be able to compute the product $f_1$ and we can easily test that $f_1$ is indeed a true factor of $f$ by checking that $f\\bmod f_1=0$. The problem with this approach is that there seems no easy way to find the set $S$. Of course, we can try all possible subsets $S\\subseteq\\{1,\\dotsc,k\\}$ and figure out which ones yield true factors in $\\Z[x]$, not $\\Z_p[x]$. Of course, this requires exponential time in the number of factors.\n",
"\n",
"### Squarefree Factorization\n",
"\n",
"Incidentally, it is easy to find the squarefree part of a polynomial in $\\Z[x]$ or $\\mathbb{Q}[x]$ (or more generally any field $\\F$ where $1+1+\\dotsb+1\\neq0$ for arbitrary many additions).\n",
"This is because in $\\F[x]$ a factor divides $f=\\sum_{i\\geq0}a_ix^i\\in\\F[x]$ more than once if and only if it divides the derivative of $f$, defined by $f':=\\sum_{i\\geq1}ia_ix^{i-1}$.\n",
"\n",
"Thus, the squarefree part of $f$ can be computed by $f/\\gcd(f,f')$.\n",
"You have to be careful over a finite field, as the precondition on the field isn't met (in that case $1+1+\\dotsb+1=0$ when there are $p$ ones) and it is possible that $f'=0$ even when $f\\neq0$. Though even in a finite field it still is the case that $\\gcd(f,f')=1$ does imply that $f$ is squarefree.\n",
"\n",
"### Pseudocode\n",
"\n",
"Input: A squarefree and monic $f\\in\\Z[x]$ of degree $n$ and maximum coefficient in absolute value of $A$\n",
"\n",
"Let $p\\in[2B,4B)$ be a random prime where $B := 2^nA\\sqrt{n+1}$\n",
"\n",
"Factor $\\bar f\\in\\Z_p[x]$ as $g_1\\dotsm g_k$ for irreducible $g_i$ (mod $p$) and write the $g_i$ as polynomials with coefficients absolutely bounded by $p/2$\n",
"\n",
"$T := \\{1,\\dotsc,k\\}$\n",
"\n",
"for all $S\\subseteq T$, starting with the smallest $S$:\n",
"\n",
"$\\hspace{1em} g:=\\prod_{i\\in S} g_i$\n",
"\n",
"$\\hspace{1em}$if $f\\bmod g=0$ then\n",
"\n",
"$\\hspace{2em} f:=f/g$\n",
"\n",
"$\\hspace{2em} T:=T\\setminus S$\n",
"\n",
"$\\hspace{2em}$add $g$ to the list of irreducible factors\n",
"\n",
"Output the list of irreducible factors of $f$\n",
"\n",
"### Analysis\n",
"\n",
"Unfortunately, the loop may run exponentially many times, since there are $2^k$ subsets of $T$.\n",
"There is a better method for determining which $g_i$ combine together to form actual irreducible factors of $f$, but it involves more mathematical machinery. In particular, an algorithm of Lenstra, Lenstra, and Lovász from 1982 is able to solve the factoring problem in $\\mathbb{Q}[x]$ in polynomial time in $\\deg(f)=n$ and in the size of the coefficients of $f$. At the time this was somewhat surprising, even to the discoverers. Their method is even totally deterministic, which at first seems paradoxical since it relies on the $\\Z_p[x]$ factoring method that uses randomness. This is possible because they are able to show that they can find a prime $p$ in polynomial time (without relying on randomness) for which the $\\Z_p[x]$ factoring algorithm is _guaranteed_ to find the factorization in $\\Z_p[x]$."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "SageMath 9.5",
"language": "sage",
"name": "sagemath"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.12"
},
"latex_metadata": {
"author": "Curtis Bright",
"date": "March 7, 2024",
"title": "Computational Mathematics: Handout 12"
}
},
"nbformat": 4,
"nbformat_minor": 2
}