Tonelli-Shanks Algorithm
Tonelli-Shanks 求模素数 p 的二次剩余平方根：x^2≡n (mod p) 的解 x。
用途
求解模素数二次剩余的平方根，用于椭圆曲线点压缩与数论。
机制
p=2 或 p≡3 (mod 4) 有直接解。一般 p-1=2^s*q，找非二次剩余 z，令 c=z^q，迭代调整使指数降低至 1。复杂度 O(s^2 log p)。
用例
- 椭圆曲线点解压
- 模平方根
- 数论算法
Tonelli-Shanks 求模素数 p 的二次剩余平方根：x^2≡n (mod p) 的解 x。
求解模素数二次剩余的平方根，用于椭圆曲线点压缩与数论。
p=2 或 p≡3 (mod 4) 有直接解。一般 p-1=2^s*q，找非二次剩余 z，令 c=z^q，迭代调整使指数降低至 1。复杂度 O(s^2 log p)。