Las Vegas factoring of quadratic polynomials over ${\mathbb{F}}_p$

Let $f\in {\mathbb{F}}_p[x]$ be a quadratic polynomial. We want to factor $f$ over ${\mathbb{F}}_p$. First we test whether $f$ is irreducible; if so, we are done. Otherwise we know that $f$ can be factored as $f(x)=(x-a)(x-b)$ where $a,b\in {\mathbb{F}}_p$. We want to find $a$ and $b$.

Definition 0.3   We say that a polynomial $g$ splits polynomial $f$ if $1\neq \mathop{\rm g.c.d.\,}\nolimits (f,g)\neq f$.

It suffices to find a polynomial that splits $f$.

If $a=b$ then $f'$ splits $f$. So if $f'$ does not split $f$ then we know that $a\neq b$. We may also assume that $ab\neq 0$ (why?)

We start with an easy case. Suppose ${\displaystyle\genfrac{(}{)}{}{}{a}{p}} \neq {\displaystyle\genfrac{(}{)}{}{}{b}{p}}$. In this case, according to the preceding exercise, $x^{(p-1)/2}-1$ splits $f$.

If now ${\displaystyle\genfrac{(}{)}{}{}{a}{p}} = {\displaystyle\genfrac{(}{)}{}{}{b}{p}}$, our next trick is to consider the polynomials $g_r(x) = f(x+r)$. Ideally, we want to find $r$ such that ${\displaystyle\genfrac{(}{)}{}{}{a-r}{p}} \neq {\displaystyle\genfrac{(}{)}{}{}{b-r}{p}}$. Then $x^{(p-1)/2}-1$ splits $g_r$ and therefore we can factor $f$. The next exercise shows that we have an excellent chance of finding $r$ by just picking it at random.