The two squares actually produced

The circle on the lattice gives three proofs that a prime one more than a multiple of four is a sum of two squares, and it is worth noticing what each of them leaves on the table.

Euler’s descent shrinks a multiple of $p$ until the multiplier is one, which does terminate and does produce the squares — slowly, and only after an arbitrary starting multiple has been found. Minkowski’s lattice argument says a disc of the right area must contain a non-zero lattice point, which is a statement about area and names no point. Zagier’s involution counts a set’s parity and deduces that a second involution has a fixed point, which exhibits nothing at all.

$10007$ is not a sum of two squares; $10009$ is. Which two?

Two divisions. The algorithm is Cornacchia’s, from 1908, and the surprising part is not that it is short but where it stops — the rule take the first remainder below the square root is not an optimisation, it is the entire correctness proof compressed into a comparison.

What has to be found first #

The chain needs a number $s$ with $s^2 \equiv -1 \pmod p$, and finding one is the only step with any cost in it.

Such an $s$ exists exactly when $p \equiv 1 \pmod 4$, which is the fact the two-square theorem rests on: the numbers modulo a prime form a cyclic group of order $p-1$, and an element of order four exists precisely when four divides $p-1$, which is the cyclic structure a generator’s powers run through used for the one thing it is most often used for. Its square has order two, and the only element of order two is $-1$.

Producing one is a different matter. The standard route takes any $a$ that is not a square modulo $p$ and computes $a^{(p-1)/4}$, which squares to $a^{(p-1)/2} = -1$ by Euler’s criterion. Testing whether a given $a$ is a non-residue is fast; half of all $a$ work; so a handful of tries suffice, and the figures here do exactly that.

That is the only randomised step in the whole computation, and it is worth flagging because it is where the practical difficulty of the problem actually sits. Everything after it is division.

Why stopping there is the proof #

The chain is run on $p$ and $s$, and the claim is that the first remainder below $\sqrt p$ is one of the two squares’ roots. Here is why.

Write $x$ for that remainder and $y$ for the value of the remainder above it reduced against $x$ — equivalently, $y = \sqrt{p - x^2}$, which the algorithm’s correctness is the claim about. The relation that carries down the chain is the one the congruence started from: every term is congruent to $\pm s$ times the next, modulo $p$, because each is obtained from the two before by subtracting a multiple. So

$$x \equiv \pm\, s\,y \pmod p, \qquad \text{hence} \qquad x^2 + y^2 \equiv s^2y^2 + y^2 = (s^2+1)y^2 \equiv 0 \pmod p.$$

So $x^2 + y^2$ is a multiple of $p$ at every stage. The only question is which multiple, and that is where the size condition comes in: once both $x$ and $y$ are below $\sqrt p$, the sum $x^2 + y^2$ is below $2p$ and positive, so the only multiple of $p$ it can be is $p$ itself.

That is the whole argument, and the figures check both halves of it: the answer is required to satisfy the congruence, and the row above the stopping line is required not to work — $p$ minus its square is not a square, so stopping one step early would produce nothing.

The same thing as a lattice #

Minkowski’s proof draws a lattice and says a short vector must exist. This algorithm produces it, and seeing the two as one object is the reason both belong in this family.

Take the sublattice generated by $(1, s)$ and $(0, p)$. Its points are exactly those with $b \equiv sa$, its fundamental cell has area $p$, and every one of its points has $a^2 + b^2 \equiv 0 \pmod p$ by the computation of the last section. So a non-zero point at squared distance below $2p$ is a representation of $p$, and Minkowski’s theorem says one exists.

Gauss reduction finds it. Start with the two generators; repeatedly subtract from the longer the nearest multiple of the shorter; stop when neither shortens the other. What remains is a shortest vector, and in two dimensions the procedure is exact rather than approximate — a fact that fails in three dimensions and fails badly in high ones, which is the whole difficulty of lattice-based cryptography.

The two are the same because a step of Gauss reduction is a step of the Euclidean algorithm. Subtracting $q$ copies of the shorter vector from the longer changes its first coordinate from $a$ to $a - qb$, which is the division step, and the rounding that chooses $q$ is the floor. So the chain of remainders in the table and the chain of shortening vectors in the lattice are one sequence, written in two notations, and the stopping rules match: the division chain stops when the remainder is below $\sqrt p$, and the reduction stops when the vector is short enough that nothing shortens it.

The figures check that the area is $p$ at every intermediate basis, which is the invariant a reduction preserves — and is the quantity Minkowski’s theorem is about.

The other square root, and the same answer #

There are two square roots of $-1$ modulo $p$, namely $s$ and $p - s$, and the chain behaves quite differently on them — which is worth knowing, because it is the one place the algorithm as usually stated has a convention that looks arbitrary and is not.

For $97$ the two are $22$ and $75$. Run the chain on $75$ and the remainders are $22$, then $9$, and the answer is $9^2 + 4^2$. Run it on $22$ and the first remainder is already below $\sqrt{97}$ before any division has happened, so the rule stop at the first remainder below the square root fires immediately and returns $22$ itself, which is above $\sqrt{97}$ and not a solution.

The convention is therefore to take the larger root, and the reason is the size argument rather than taste: the proof needs both $x$ and the term before it to be handled, and starting below $\sqrt p$ means the chain has not yet done the work the bound is about. A version that starts anywhere and stops at the first small remainder is wrong on about half its inputs, and wrong in a way that produces a number rather than an error.

That is a small instance of the recurring hazard in this collection: a stopping rule read as an optimisation rather than as the argument. The rule here is the argument, and moving it one step in either direction breaks it — one step later and both terms are small enough that the multiple could be zero, one step earlier and the sum is above $2p$ and the multiple could be two.

Set against descent, run rather than quoted #

Euler’s descent is the oldest of the three proofs, and it is worth putting the two computations beside each other, because the comparison says what the algorithm bought.

Descent starts from any multiple $m p = a^2 + b^2$ with $m$ below $p$ — one is available from $s^2 + 1 = m p$ directly — and manufactures a smaller multiplier from it by reducing $a$ and $b$ modulo $m$ into the range $\pm m/2$ and dividing. Each step at least halves the multiplier, so it terminates in about $\log p$ steps, which is the same order as the division chain.

So descent is not slow. What it is, is fiddly: each step needs a symmetric reduction, a division that must come out whole, and a check that the multiplier really fell. The division chain does the same work with a single while loop and a comparison, and the reason is that it never carries the multiplier at all — the congruence does the bookkeeping that descent does by hand.

The kinship is not superficial. Descent’s reduction step is a subtraction of the nearest multiple, which is what the Euclidean algorithm does to a rectangle and what Gauss reduction does to a basis. Three descriptions, one operation, and the one that is easiest to run is the one that keeps the least state.

What it costs, and what that is good for #

The whole computation is one square root modulo $p$ followed by a Euclidean chain, so it is fast in the sense that matters: the number of divisions is proportional to the number of digits, and each division is on numbers no larger than $p$.

That has a consequence worth stating, because it is easy to assume the opposite. Representing a prime as a sum of two squares is easy, and factoring a number is hard. Those two facts sit uncomfortably close together, since a number with two essentially different representations is composite and gives its factors — so if representations were easy to find for composites, factoring would be easy.

The resolution is that the algorithm above needs $s$, and finding a square root of $-1$ modulo a composite $n$ is exactly as hard as factoring $n$. Given such an $s$, $\gcd(s^2+1, n)$ splits $n$ immediately. So the easy step and the hard step are cleanly separated: the arithmetic of the chain is cheap, and the ingredient it needs is the whole difficulty.

That pattern recurs through computational number theory, and this is its smallest instance. The same square root modulo $p$ is what the Tonelli–Shanks algorithm computes for general residues; it is the reason a ring can factor uniquely and still be hard to factor in; and it is the step that makes primality testing and factoring such different problems despite being about the same objects.

Where the answer is used #

Modular square roots, everywhere. The one expensive ingredient here — a square root modulo a prime — is the same subroutine that decompresses an elliptic-curve point from its x-coordinate, that decides whether a quadratic congruence has a solution, and that sits underneath half the constructive results in this field. Its cost is a modular exponentiation, which is to say it is cheap and is still the dominant term.

Elliptic-curve point counting. The number of points on a curve over a field of $p$ elements, for curves with extra structure, is given by $p + 1 - a$ where $a$ is read off a representation $4p = a^2 + b^2 d$ — the two-square computation with a coefficient. Producing those representations is what Cornacchia’s algorithm is usually running for in a modern library.

Gaussian integer factorisation. Factoring an ordinary integer in $\mathbb{Z}[i]$ means splitting each prime $\equiv 1 \pmod 4$ into $(a+bi)(a-bi)$, which needs the same $a$ and $b$. Nothing else is required, since primes $\equiv 3$ stay prime and $2$ ramifies.

And sums of four squares. Lagrange’s theorem says every number is a sum of four squares, and the standard constructive proof runs a descent whose base case is the two-square computation. Rabin and Shallit’s randomised algorithm for it, from 1986, is built on exactly this chain.

Why two dimensions is where this works #

The lattice reading raises a question it is worth answering, because the answer explains why the two-square theorem has a clean algorithm and its natural generalisations do not.

Gauss reduction finds a genuinely shortest vector, and in two dimensions that is exact: the procedure terminates with a basis whose first vector is shortest in the whole lattice, and the proof is a page. In three dimensions there is a similar procedure and it is already harder. In high dimensions finding a shortest lattice vector is NP-hard, and the best general algorithms take exponential time; the workhorse approximations, of which LLL from 1982 is the first, return a vector within an exponential factor of shortest and are enormously useful precisely because nothing better is available.

So the picture in the two lattice figures is the last dimension in which it is easy. That is not a curiosity about this essay’s subject; it is the reason the hardness of lattice problems is now the standard foundation for cryptography meant to survive quantum computers, and the two-dimensional case is the toy that shows what the hard problem is a version of.

It also explains the shape of the generalisations. Representing $p$ by $x^2 + n y^2$ for other $n$ is the same lattice question with a different quadratic form, and Cornacchia’s algorithm handles it by the same chain with the stopping bound changed — because the lattice is still two-dimensional. Representing a number by a form in four variables, as Lagrange’s theorem does, is a four-dimensional lattice question and has no comparably clean method; the constructive proofs there descend instead, one square at a time.

Six instances, and a claim about every prime #

Every figure is one prime. The algorithm’s correctness is a statement about all $p \equiv 1 \pmod 4$, and the four tables and two lattices here are six instances. What each figure does check is that this instance’s answer satisfies the congruence and that stopping one step early would fail — which is the shape of the argument tested at a point, not the argument.

The square root of $-1$ arrives without explanation. Both views take $s$ as given and neither shows how it was found. The search for a non-residue is a loop with no geometry in it, and drawing it would be drawing a list of failed tests.

The lattice pictures are drawn at small primes for a reason that undermines them. At $29$ the lattice is visibly sparse and the shortest vector is visibly short. At $10009$ the same picture has one lattice point in every ten thousand grid points and cannot be drawn at all at a scale where the circle is visible — so the figures show the mechanism exactly where the mechanism is unnecessary, and are silent at the sizes anybody would run it.

And neither view shows the second representation. The circle of radius $\sqrt p$ passes through eight points, being the four sign choices on two coordinates and the swap; the algorithm returns one and the others are relabellings. For a composite with two genuinely different representations — the case that factors it — this chain returns only the one its $s$ leads to.

Still open here: producing what the counting formula counts #

Jacobi’s formula says exactly how many lattice points sit on the circle of radius $\sqrt n$, for every $n$, by counting divisors. That is a count and not a list, and this essay has produced one point of the list for a prime.

The general problem — list every representation of an arbitrary $n$ — reduces to factoring $n$ and then multiplying the prime representations together in the Gaussian integers, where the sign choices at each prime give the whole list. So it is exactly as hard as factoring, and the counting formula computes without any of that work how many answers there are. A formula that says how many and cannot say which is the standing shape here, and it is the same gap Frobenius’s count of coverings has in a completely different subject.

An existence proof, and the thing it does not contain #

The habit is worth stating because it is easy to be satisfied too early.

Three proofs of the two-square theorem are on record and all three are complete. Not one of them can be run. Descent needs a starting multiple and shrinks slowly; Minkowski’s argument is about area and names nothing; Zagier’s is a parity count that proves a fixed point exists without locating it.

An existence proof and a construction are different objects, and the gap between them is sometimes the whole subject. Here it is one line of division, and the line is short enough that the difference looks unimportant. In the design theory that settled existence asymptotically the gap is still open, and in factoring it is the gap that cryptography is built on.

The question to ask of any existence theorem is what would have to be added to make it run — and then whether that addition is a detail or is the problem.