Constructing an irreducible polynomial of degree $2$ over $\mathbb{F}_p$

Question

I want to construct an irreducible polynomial of degree $2$ over $\mathbb{F}_p$ where $p$ is a prime that can be written as $4k+1$. My attempt is as follow: we can assume that this polynomial is of the form ${x^2} + ax + b$ for some $a,b \in {\mathbb{F}_p}$. So for all $\lambda \in {F_p}$, $p$ doesn't divide ${\lambda ^2} + a\lambda + b$. It follows that ${\lambda ^2}$ is not equal to $a\lambda + b \bmod p$. If we can find some $a,b \in {\mathbb{F}_p}$ such that $a\lambda + b$ is a nonresidue for all $\lambda \in {F_p}$, it is ok. But I cannot. I wait your response.

Answer 1

$x^2-b$ is irreducible mod $p$ iff $b$ is a quadratic non-residue mod $p$.

Since half the classes mod $p$ are quadratic non-residues, there are plenty of choices for $b$.

Explicitly finding one $b$ for a given $p$ is another matter, although it is usually quite small: see A053760. In particular, the smallest quadratic non-residue mod $p$ is at most $\sqrt{p}+1$ (proof).