题目完整复述
理论背景
模素数 p 二次剩余定义： 若存在整数 a 满足 \(a^2 \equiv x \pmod p\)，则 x 为模 p二次剩余；不存在则为二次非剩余。 若 a 是 x 的平方根，则 \(p-a\)（即 \(-a \pmod p\)）也是平方根，一组根一大一小，取更小值作为答案。
已知条件： 模数素数 \(p=29\) 待判断数字列表：\(\text{ints} = [14, 6, 11]\) 题干说明列表内包含两个二次非剩余、一个二次剩余。
任务：
- 找出列表中唯一的二次剩余；
- 求出该数模 29 的一对平方根；
- 输出两个根中更小的数字作为 flag。
解题思路
- 暴力遍历 \(a \in [1,28]\)，计算 \(a^2 \bmod 29\)，建立「二次剩余值→平方根」映射表；
- 依次判断 14、6、11 是否存在于映射表中，筛选出唯一二次剩余；
- 取出该剩余对应的两个平方根，对比大小取较小值。
代码实现（Python）
运行结果与推导
执行代码输出：
手动验算：
- \(8^2 = 64\)，\(64 \bmod 29 = 6\)；
- 另一根：\(-8 \equiv 29-8 = 21 \pmod{29}\)，\(21^2 = 441\)，\(441 \bmod 29 = 6\)；
- 对比 8 和 21，更小值为 8。
验证另外两个数字（非二次剩余）：
- 14：不存在任何 \(a \in [1,28]\) 满足 \(a^2 \equiv 14 \pmod{29}\)；
- 11：不存在任何 \(a \in [1,28]\) 满足 \(a^2 \equiv 11 \pmod{29}\)； 完全符合题干 “两非剩余一剩余” 的描述。
最终答案
flag：8
拓展知识点
- 素数模 p 的有限域乘法群 \(\mathbb{F}_p^*\) 有 \(p-1\) 个元素，恰好一半是二次剩余、一半是非剩余；
- 任意二次剩余必然成对出现平方根 a 和 \(p-a\)，二者大小不同；
- 二次剩余是密码学 Rabin 加密、椭圆曲线、离散对数题型的基础前置知识。