低平方和Sum of low squares

平方数，高与低

设 p 为一个奇素数。那么从 1 到 p − 1 的数字中，一半是平方数，一半不是。也就是说，对于 1 ≤ k < p 中的一半数字，方程

x² = k mod p

有解。这些数字的传统名称是“二次剩余”，但如果上下文清晰，我们可以直接称其为“平方数”。例如，数字 1、2 和 4 是模 7 的平方数，而数字 3、5 和 6 则不是。

如果 k 是模 p 的平方数，当 0 ≤ k < p/2 时，我们称其为低平方数；当 p/2 < k < p 时，称其为高平方数。

签名

现在设 p > 3 为一个同余于 3 mod 4 的素数。将模 p 的所有低平方数相加，并对 p 取余数。我们将此称为 p 的签名。下面是用 Python 编写的代码，以使其更加明确。

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

逆签名

令人惊讶的是，每个 p 的签名都是唯一的。给定 p 的签名，你就可以唯一确定 p，事实上这很容易做到。我在一篇论文 [1] 中偶然发现了这一点，该论文以室内魔术的形式展示了这一结果：让某人选择一个素数 p，使得 p = 3 mod 4，并要求他们计算其签名，即模 p 的低平方数之和。然后你就可以迅速告诉他们所选择的 p 是多少。

给定签名 s，对应的素数 p 是 16s + 1 的最大素因子。

不仅如此，

p = (16s + 1)/m

其中 m 是集合 {3, 7, 11, 15} 中使得上述分式为素数的最小数字。用 Python 代码表示的话，以下两个函数都应该能求出 p 的逆签名。

def inverse_signature1(s):
    return max(factorint(n).keys())

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

以下代码证明了对于小于 1,000 的数字，情况确实如此。

for n in range(7, 1000, 4):
    if isprime(n):
        s = signature(n)
        assert(n == inverse_signature1(s))
        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.