分类：
2010-10-31 19:20:36
a^2 = r (mod p) ，式中的 r 称为平方剩余。
已知 r, p 求 a 。如果 p 是合数，上述问题的复杂度和整数的因数分解问题复杂度相同，目前为止没有多项式复杂度的算法。当 p 是素数，这个问题有高效算法
Tonelli-Shanks 算法。特别的，当 p-1 的因数分解中只有一个 2 的时候（即 p = 3 (mod 4) ）， Tonelli-Shanks 算法能够进一步简化为
a = (+-)(r ^ ((p+1)/4)) (mod p)
使用
Tonelli-Shanks 算法的时候还需要求 x^y
(mod m) 的高效算法，这个算法可以网上搜“ modular exponentiation ”或者中文“同余幂”。
同余幂是一个单向函数。已知 x, y, m 求 R = x^y (mod m) 是容易的，即使 x, y, m 都是很大的数字（数百位的十进制数）也没关系。但是求所谓的“离散对数”，即已知 R, x, m 求 y ，目前为止还是公认的难解问题。
一开始提到的平方剩余问题，英文是 Quadratic residue 。
