区块链中的数学-用Cipolla算法求解二次剩余方程

本节讲了使用Cipolla算法求解二次剩余方程,该算法涉及内涵比较丰富,没有展开。

## 写在前面 上一节讲了[原根及其定理](https://learnblockchain.cn/article/1523),可以看出,原根通常也用来表示为循环群的生成元。 本节继续二次剩余方程的解法。回顾下二次剩余方程如下: $x^2 \equiv n(mod \ p)$ 求出满足条件的x.$x \in F_p$ ## 预备知识 1. $(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模时被消掉。 2. 二次剩余方程有$\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的二次剩余恰好有两个解,互为相反数。 3. $x^2 \equiv (x+p)^2 (mod \ p)$ 显然可得 有了预备知识,接着看下具体解法。 ## Cipolla算法 该算法由Michele Cipolla提出,以他的名字命名。使用前提条件:p是奇素数。算法步骤描述起来很简单: 1. 找到一个数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$是一个二次非剩余。 2. 计算 $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)$ 满足结合律了。就可以使用[快速幂模](https://learnblockchain.cn/article/1573)了。 ### 实现示例 具体到代码实现,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公钥恢复](https://learnblockchain.cn/article/1518)相关了!! — 欢迎关注公众号:blocksight

写在前面

上一节讲了原根及其定理,可以看出,原根通常也用来表示为循环群的生成元。

本节继续二次剩余方程的解法。回顾下二次剩余方程如下:

$x^2 \equiv n(mod \ p)$

求出满足条件的x.$x \in F_p$

预备知识

  1. $(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模时被消掉。

  1. 二次剩余方程有$\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的二次剩余恰好有两个解,互为相反数。

  2. $x^2 \equiv (x+p)^2 (mod \ p)$ 显然可得

有了预备知识,接着看下具体解法。

Cipolla算法

该算法由Michele Cipolla提出,以他的名字命名。使用前提条件:p是奇素数。算法步骤描述起来很简单:

  1. 找到一个数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$是一个二次非剩余。

  2. 计算 $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

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-08-04 23:40
  • 阅读 ( 77 )
  • 学分 ( 5 )
  • 分类:入门/理论

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/27831

联系我们

aliyinhang@gmail.com