Representing a prime as a sum of two squares

We proved in this class that if $p$ is aq prime and $p\equiv 1 \pmod 4$ then there exist integers $a,b$ such that $p=a^2+b^2$. The goal is to find such $a$ and $b$ in polynomial time (i.e., in time $(\log p)^{O(1)}$).

Rabin and Shallit showed that we can find $a,b$ in randomized polynomial time (a Las Vegas algorithm). As a subroutine, they need to factor polynomials in ${\mathbb{F}}_p$. This can be done in randomized polynomial time using a Las Vegas algorithm by Berlekamp. (Polynomial-time factoring of polynomials over ${\mathbb{Q}}$ is a consequence of the lattice basis reduction algorithm. This algorithm does not work for factoring over ${\mathbb{F}}_p$ and no deterministic polynomial-time algorithm is known for this case.)

How can we guarantee that a factoring is correct? By multiplying the factors we can verify that the product equals the input polynomial. But we also need to test that the factors are irreducible. Indeed, we have a deterministic test for irreducibility of polynomials over ${\mathbb{F}}_p$.