Sum of low squares<br>3 is a prime number and p = 3 mod 4, then the sum of the low squares of p uniquely determines p." />

3 is a prime number and p = 3 mod 4, then the sum of the low squares of p uniquely determines p." />

3 is a prime number and p = 3 mod 4, then the sum of the low squares of p uniquely determines p." />

(832) 422-8646

Contact

Squares, high and low

Let p be an odd prime number. Then half the numbers from 1 through p − 1 are squares and half are not. That is, for half of numbers 1 ≤ k p, the equation

x² = k mod p

has a solution. The traditional name for these numbers is "quadratic residues" but we can just say "squares" if the context is clear. So, for example, the numbers 1, 2, and 4 are squares mod 7, and the numbers 3, 5, and 6 are not.

If k is a square mod p we will call is a low square if 0 ≤ k p/2 and a high square if p/2 k p.

Signatures

Now let p > 3 be a prime congruent to 3 mod 4. Add up all the low squares mod p and take the remainder mod p. Call this the signature of p. Here’s Python code to make this explicit.

from sympy import isprime, factorint, is_quad_residue

def signature(p):<br>assert(p > 3)<br>assert(isprime(p))<br>assert(p % 4 == 3)<br>s = 0<br>for k in range(1, 1 + p//2):<br>if is_quad_residue(k, p):<br>s += k<br>return s % p

Inverse signatures

Surprisingly, the signature of each p is unique. Given the signature of p, you can uniquely determine p, and in fact you can do so easily. I ran across this in a paper [1] that presented the results in the form of a parlor trick: have someone pick a prime p such that p = 3 mod 4 and ask them to compute its signature, the sum of the low squares mod p. Then you can quickly tell them what their choice of p was.

Given a signature s, the corresponding prime p is the largest prime factor of 16s + 1.

Not only that,

p = (16s + 1)/m

where m is the smallest of the numbers {3, 7, 11, 15} such that the fraction above is a prime number. In term of Python code, both the following functions should invert the signature of p.

def inverse_signature1(s):<br>n = 16*s + 1<br>return max(factorint(n).keys())

def inverse_signature2(s):<br>n = 16*s + 1<br>for m in [3, 7, 11, 15]:<br>if n % m == 0 and isprime(n // m):<br>return n // m

The following code demonstrates that this is the case for numbers less than 1,000.

for n in range(7, 1000, 4):<br>if isprime(n):<br>s = signature(n)<br>assert(n == inverse_signature1(s))<br>assert(n == inverse_signature2(s))

[1] David M. Bloom. A Quadratic Residues Parlor Trick. Mathematics Magazine, Vol. 71, No. 3 (Jun., 1998), pp. 201–203.

One thought on &ldquo;Sum of low squares&rdquo;

Steve

20 July 2026 at 01:25

Hi John.

Thanks for your interesting posts. Just letting you know that you omitted the line in inverse_signature1 where you compute n from s.

Steve

Leave a Reply<br>Your email address will not be published. Required fields are marked *<br>Comment *<br>Name *

Email *

Website

Search for:

John D. Cook, PhD

My colleagues and I have decades of consulting experience helping companies solve complex problems involving data privacy, applied math, and statistics.

Let’s talk. We look forward to exploring the opportunity to help your company too.