Sum of low squares

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 an 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): assert(p > 3) assert(isprime(p)) assert(p % 4 == 3) s = 0 for k in range(1, 1 + p//2): if is_quad_residue(k, p): s += k return s % p Inverse signatures Surprisingly, the signature of each p is unique. Given the…