核心概述
模平方根（Modular Square Root，Tonelli–Shanks）：在奇素数模 p 下判定并求解 x^2≡a 的一个根；非二次剩余无解，边界情形 p=2 与 a≡0 需特判，复合模可拆分后用 CRT 合并。
原文引述
Description: Compute modular square root x with x^2≡a (mod p). Tests residue via Legendre symbol a^{(p−1)/2}. If residue and p is odd prime, use Tonelli–Shanks. Handles p=2 and composite moduli via CRT/Hensel. Time: O(log^2 p) modular multiplies (expected), non-residue found in expected O(1)
展开阐述
-
函数/接口（据实现）
- modSqrtPrime(a, p) → x 或 −1：p 为奇素数；若有解返回一个根 x∈[0,p)，另一个为 p−x（当 x≠0）。
- modSqrtPrimePower(a, p, k) → x 或 −1：p 为奇素数，模 p^k 的根，可用 Hensel 提升。
- modSqrtComposite(a, m) → x 或 −1：将 m 分解为素幂，分别求根并用 081-数论-中国剩余定理 合并。
- 相关依赖：091-数论-模幂、088-数论-模逆、083-数论-欧几里得算法。
-
预检与特判
- 归一化：令 a ← a mod p。
- 若 a==0：返回 0。
- 若 p==2：返回 a（0/1）。
- 二次剩余判定（勒让德符号）：r = a^{(p−1)/2} mod p；若 rp−1（即 −1）则无解，若 r0 则解为 0，若 r==1 则继续。
-
Tonelli–Shanks（p 为奇素数，且 a 为二次剩余）
- 分解 p−1 = q·2^s，q 为奇数。
- 寻找非二次剩余 z（随机试 a_i，首个 a_i^{(p−1)/2}≡−1 即可）。
- 初始化：
- c = z^q mod p
- x = a^{(q+1)/2} mod p
- t = a^q mod p
- m = s
- 迭代直到 t==1：
- 找到最小 i∈[1, m) 使 t^{2^i} ≡ 1 (mod p)。
- 设 b = c^{2^{m−i−1}} mod p
- x = x · b mod p
- t = t · b^2 mod p
- c = b^2 mod p
- m = i
- 返回 x（另一根为 p−x；若 x==0 则根唯一）。
-
素幂与合成模（可选）
- p^k（p 为奇素数）：先解模 p 的根 x0，用 Hensel 提升到 x_k 满足 x_k^2≡a (mod p^k)。
- 合数 m：对 m 的素幂分解上分别取根，经 081-数论-中国剩余定理 合并；若任一子问题无解则整体无解。
-
输出语义
- 若有解返回一个根 x（规范到 [0,p) 或 [0,m)），另一根为模的补值。
- 若无解返回 −1（按实现约定）。
-
复杂度
- 判定与幂运算 O(log p)，循环中平方次数不超过 s，整体期望 O(log^2 p)。
-
使用与注意
- 仅在奇素数模下，勒让德符号判定与 Tonelli–Shanks 适用；合成模需分解或用 Hensel/CRT。
- 乘法可能溢出时配合 090-数论-长整型模乘；幂运算见 091-数论-模幂。
- 返回两根时可统一返回较小者作为规范代表；调用方可按需取另一根。