2 months ago
- For an odd prime p, exactly half of the numbers from 1 to p-1 are quadratic residues (squares modulo p).
- A square modulo p is called 'low' if it is less than p/2, and 'high' if greater than p/2.
- For primes p > 3 with p ≡ 3 mod 4, the signature is defined as the sum of all low squares modulo p.
- The signature uniquely determines the prime p; the prime can be recovered as the largest prime factor of 16s + 1, or as (16s+1)/m where m is the smallest in {3,7,11,15} that yields a prime.