Gaussian Integers — factoring sums of two squares in Z[i]

The Gaussian integers Z[i] = {a + bi : a,b ∈ Z} are a Euclidean domain with norm N(a+bi) = a²+b², so they have unique factorization and their own GCD algorithm — which makes "sum of two squares" and related-factorization problems tractable: a prime p ≡ 1 (mod 4) splits as p = π·π̄, directly recovering p = a² + b².

The signal that gives it away

- The challenge literally hands you N = a² + b² (or a prime p) and asks for (a,b). - You're given a prime p ≡ 1 (mod 4) and need to write it as a sum of two squares — this is a necessary and sufficient condition: p ≡ 1 mod 4 always splits, p ≡ 3 mod 4 never does (verified against Keith Conrad's Gaussian integers notes). - A composite N is presented whose factorization you already know (or can get cheaply), and the challenge wants the *two-square* representation(s) of N, not the factorization itself. - An RSA-like or curve-adjacent setup embeds data in a Gaussian prime, or gives you a norm that's a product of split primes. - Connects to Quadratic Residues — deciding if x² ≡ a (mod n) has a solution before you go looking for one: p ≡ 1 mod 4 splitting is exactly the statement that -1 is a quadratic residue mod p — check that first if p mod 4 alone feels too thin a signal.

How to exploit

1. Confirm the necessary condition first. Check p mod 4. Only p ≡ 1 (mod 4) (or p = 2) has a two-square representation; run Primality Testing — confirming a number is prime without factoring it if primality itself isn't given. 2. Find a square root of -1 mod p. Use Tonelli-Shanks — computing an actual modular square root, not just whether one exists (or sympy.ntheory.residue_ntheory.sqrt_mod(-1, p)) to get x with x² ≡ -1 (mod p). 3. Run the Gaussian Euclidean algorithm on `(p, x+i)`. This is Cornacchia's algorithm in disguise: repeatedly reduce a, b = b, a % b (integer division) starting from a=p, b=x; the first remainder with norm < p (i.e. b*b < p) is one of the two square roots you want — the other is recovered from p - b². ``python # Cornacchia-style descent: p = a^2 + b^2 for prime p % 4 == 1 def two_squares(p): from sympy.ntheory.residue_ntheory import sqrt_mod x = sqrt_mod(-1, p) # x^2 = -1 mod p a, b = p, x while b * b > p: a, b = b, a % b c = int((p - b * b) ** 0.5) # verify c*c == p - b*b before trusting it return b, c # b^2 + c^2 == p ` 4. **Let a CAS do it directly for composites too.** SageMath: K.<I> = GaussianIntegers(); K(N).factor() factors N over Z[i] directly; sum_of_k_squares(2, n) returns one two-square representation of n without you hand-rolling Cornacchia. 5. **Use multiplicativity of the norm to constrain divisors.** N(zw) = N(z)·N(w), so if you already have N's rational-prime factorization, you get every two-square representation by factoring each p ≡ 1 mod 4` factor into its Gaussian prime pair, distributing conjugates across the two "slots," and multiplying back out — this is how you enumerate *all* representations, not just one.

What does NOT work

- Running Cornacchia/Tonelli-Shanks on a prime `p ≡ 3 (mod 4)`. Such a prime is itself a Gaussian prime (inert, doesn't split) and has *no* representation as a sum of two squares — full stop. Check p mod 4 before spending any effort; this single check saves the most time of anything in this technique. - Asking for the two-square representation of a composite `N` without its factorization. Unique factorization lives in Z[i], but to use it you need N's factorization into *rational* primes (or you're trying to factor N itself, which is a much harder problem this technique does not solve for you — see Integer Factorization Methodology — which factoring attack to try, in what order for that). Gaussian-integer factoring is the payoff *after* you know the rational factorization, not a shortcut around it. - Assuming every composite has a two-square representation. A positive integer is a sum of two squares iff every prime factor ≡ 3 (mod 4) in its factorization appears to an *even* power. If even one such prime appears to an odd power, no representation exists — don't chase one. - Treating this as a general-purpose RSA-modulus factorer. Z[i] factoring is fast because it operates on numbers whose rational-prime factorization is already known or small; it gives no leverage on factoring a hard, unstructured RSA n = p·q with both primes large and unknown.

Related

Quadratic Residues — deciding if x² ≡ a (mod n) has a solution before you go looking for one Tonelli-Shanks — computing an actual modular square root, not just whether one exists Integer Factorization Methodology — which factoring attack to try, in what order Finite Field Arithmetic — the GF(p^k) substrate under AES, LFSRs, and extension-field curves/DLP Primality Testing — confirming a number is prime without factoring it