Back to the $p=a^2+b^2$ problem

In this section we describe the Rabin-Shallit polynomial-time Las Vegas algorithm to represent a given prime of the form $4k+1$ as the sum of two squares.

We know that $-1$ is a quadratic residue in ${\mathbb{F}}_p$ for $p\equiv 1 \pmod 4$, i.e. there exists $t$ such that $t^2\equiv -1 \pmod p$. Our first task is to find such $t$? This is equivalent to factoring the polynomial $x^2+1=(x+t)(x-t)=x^2-t^2 \in F_p[x]$.

Definition 0.4   The domain of Gaussian integers is defined as ${\mathbb{Z}}[i] = \{a+bi ~\colon~ a,b\in {\mathbb{Z}}\}$.

Divisibility, primes, g.c.d. are defined among Gaussian integers the same way as among integers. (Recall: by definition, the greatest common divisor is not ``largest'' among the common divisors but one that is a common multiple of all common divisors. So its existence is not evident.)

There are four units (numbers dividing $1$) among Gaussian integers, $1,-1,i$, and $-i$. Let us take a look at Gaussian primes. $2$ and $5$ are not primes in ${\mathbb{Z}}[i]$ (because $5 = (2+i)(2-i)$) but $3$ remains a prime.

Corollary 0.5   Every Gaussian integer has unique prime factorization in ${\mathbb{Z}}[i]$ (unique apart from order and units). (Prove!)

The algorithm

Let $p\equiv 1 \pmod 4$. By factoring the polynomial $x^2+1$ over ${\mathbb{F}}_p$, we found, in Las Vegas polynomial time, and integer $t$ such that $p\mid t^2+1$. Now $t^2+1 = (t+i)(t-i)$. Since $p=a^2+b^2$ ($a$, $b$ unknown) and $a+bi$ is a prime in ${\mathbb{Z}}[i]$, it follows that $a+bi$ divides either $t+i$ or $t-i$ (but not both - why?). Therefore $t+i$ splits $p$: if $a+bi\mid t+i$ then $a+bi=\mathop{\rm g.c.d.\,}\nolimits (t+i,p)$. Otherwise, $a-bi=\mathop{\rm g.c.d.\,}\nolimits (t+i,p)$. In either case, we find $a,b$ using Euclid's algorithm in ${\mathbb{Z}}[i]$.