写在前面
上一节讲了原根及其定理,可以看出，原根通常也用来表示为循环群的生成元。
本节继续二次剩余方程的解法。回顾下二次剩余方程如下：
$x^2 \equiv n(mod \ p)$
求出满足条件的x.$x \in F_p$
预备知识
-
$(a+b)^p \equiv a^p +b^p(mod \ m)$
证明：二项式展开可以得到：
$(a+b)^p = \sum_{k=0}^p C_p^ka^kb^{p-k}$
因为当k不等于p且不为0时，$C_p^k$中的p是肯定存在的，于是就会在取p模时被消掉。
-
二次剩余方程有$\frac{p-1}{2}$个解（0除外）
证明：如果存在两个不同数u、v，它们的平方在模p意义下同余，即是二次剩余方程的两个解。
那么显然有$p|(u^2-v^2)$,[注：'|' 代表整除，即右边的数是左边的数的倍数]。得到$p|(u+v)(u−v)$。显然p不可能整除u−v，所以p整除u+v，因此：
$u + v ≡ 0 (mod\ p)$
这个结论反过来也成立，因此共有$\frac{p-1}{2}$种互不相同的平方，显然对应了所有有解的n，且每一个p的二次剩余恰好有两个解，互为相反数。
-
$x^2 \equiv (x+p)^2 (mod \ p)$
显然可得
有了预备知识，接着看下具体解法。
Cipolla算法
该算法由Michele Cipolla提出，以他的名字命名。使用前提条件：p是奇素数。算法步骤描述起来很简单：
-
找到一个数a，$\frac{a^2-n}{p}=-1$ 勒让德符号为-1, 即 $(a^2-n)^\frac{p-1}{2}=-1$, 令$w=a^2-n,w^{\frac{p-1}{2}}=-1,w$是一个二次非剩余。
-
计算 $x=(a+\sqrt{w})^\frac{p+1}{2} （mod \ p）$ 是方程的解。
看起来简单，为什么这样做能得到解呢？
证明过程：
要证明 $x=(a+\sqrt{w})^\frac{p+1}{2} $ 是解，只要证明 $x^2 \equiv n (mod \ p)$ 即可。
代入得，$(a+\sqrt{w})^{p+1}= (a+\sqrt{w})^p * (a+\sqrt{w})$
有预备知识1和w二次非剩余性质，$(a+\sqrt{w})^p =a^p+ \sqrt{w}^p \equiv a-\sqrt{w}(mod \ p)$
代入前式，得
$x^2 \equiv (a-\sqrt{w})*(a+\sqrt{w}) \equiv a^2-w \equiv a^2-(a^2-n) \equiv n(mod \ p)$
到此得证。
证明过程也不难，难的是只有脑洞打开的人，才能想到这种方法。既然过程简单，那实现起来也应该不难。说线做泪，真要实现起来没那么容易。
这里的核心要点是：在$F_p$域无法对w开根号,即模p意义下无平方根。
但是我们可以构造一个新的数域${F_p}_2$，使得ω在${F_p}_2$下能够开根。类似于−1在复数域下能够表示为$\sqrt{-1}$一样。
这样的话F${F_p}_2$内的数都可以写作: a+kω的形式或者（a,k）。可以证明确实是个合法的域，同时在${F_p}_2$下得到的解在${F_p}$下也成立，而且最后的答案中ω的系数一定为0。这个证明过程复杂，感兴趣的参见Wiki：
https://en.wikipedia.org/wiki/Cipolla%27s_algorithm#Proof
或者 http://people.math.gatech.edu/~mbaker/pdf/cipolla2011.pdf
类似于虚数，设$i=\sqrt{w}$ 如上所述，${F_p}_2$元素表示为：
$(a, b) = a + bi = a + b\sqrt{w}$
接下来定义一个代数系统$<{F_p}_2,+,x>$满足：
$(a,b) + (c,d) = (a + c , b + d)$
$(a,b) × (c,d) = (ac + bd, ad + bc)$
满足结合律了。就可以使用快速幂模了。
实现示例
具体到代码实现，GitHub或者网络blog都能找到，这里贴一下以便结合实践更好理解（建议代码电脑端查看）。
def square_root_of_quadratic_residue(n, modulo):
"""Square root of quadratic residue
Solve the square root of quadratic residue using Cipolla's algorithm with Legendre symbol
Returns:
int -- if n is a quadratic residue,
return x, such that x^{2} = n (mod modulo)
otherwise, return -1
"""
if modulo == 2:
return 1
if n % modulo == 0:
return 0
Legendre = lambda n: pow(n, modulo - 1 >> 1, modulo)
if Legendre(n) == modulo - 1:
return -1
t = 0
while Legendre(t ** 2 - n) != modulo - 1:
t += 1
w = (t ** 2 - n) % modulo
return (generate_quadratic_field(w, modulo)(t, 1) ** (modulo + 1 >> 1)).x
def generate_quadratic_field(d, modulo=0):
"""Generate quadratic field number class
Returns:
class -- quadratic field number class
"""
assert(isinstance(modulo, int) and modulo >= 0)
class QuadraticFieldNumber:
def __init__(self, x, y):
self.x = x % modulo
self.y = y % modulo
def __mul__(self, another):
x = self.x * another.x + d * self.y * another.y
y = self.x * another.y + self.y * another.x
return self.__class__(x, y)
def __pow__(self, exponent):
result = self.__class__(1, 0)
if exponent:
temporary = self.__class__(self.x, self.y)
while exponent:
if exponent & 1:
result *= temporary
temporary *= temporary
exponent >>= 1
return result
def __str__(self):
return '({}, {} \\sqrt({}))'.format(self.x, self.y, d)
return QuadraticFieldNumber
这是一段Python代码，流程基本和描述过程一致，不多说了。其他语言实现自行查阅。
小结
本节讲了使用Cipolla算法求解二次剩余方程，该算法涉及内涵比较丰富，没有展开。
另外如果当p不是奇素数时，还有更通用的求解方法。以后有时间再说吧
最近几篇文章的思路：
secp256k1公钥恢复-->二次剩余-->原根--> 二次剩余求解
接下来，下一篇该回头看secp256k1公钥恢复相关了！！
欢迎关注公众号：blocksight
