二次剩余 | crypto弱鸡自进阶

定义

若p是素数且a<p,

$x^2 \equiv a \pmod p$

若这个方程有解，则称a是模p的二次剩余；否则称a是模p的二次非剩余。

若a是模n的二次剩余，则a是对模n所有因子的二次剩余。

fee24f4971e3f80a080ec1ed6504150

对于奇素数，模p的二次剩余个数有且只有（p-1)/2,如果a是模p的二次剩余，那么上述方程恰好有两个解，解为

$x_0,p-x_0$

判别方法

欧拉判别法：

设素数p>2，a≠kp，那么a是模p的二次剩余充要条件是

$a^{\frac{p-1}{2}} \equiv 1 \pmod p$

非二次剩余的充要条件为

$a^{\frac{p-1}{2}} \equiv -1 \pmod p$

因为任意a，

$a^{p-1} \equiv 1 \pmod p \\ p \ | \ (a^{p-1}-1) = (a^{\frac{p-1}{2}}+1)(a^{\frac{p-1}{2}}-1)$

二次剩余的根

模4余3

当p是素数并且 p模4余3，若a是模p的二次剩余，则其二次根是 $a^{\frac{p+1}{4}}$

证明：

$(a^{\frac{p+1}{4}})^2 \equiv a^{\frac{p+1}{2}}\equiv a^{\frac{p-1}{2} }\cdot a \equiv 1\cdot a \pmod p$

模4余1

cipolla 算法：

设

$b^2 - a \equiv w \pmod p$

其中w是模p意义下的二次非剩余。由于w在模p意义下不存在平方根，类似与虚数设i = w^0.5。类似于复数重新定义模p意义下一个数为（a，b）。

接下来定义一个代数系统

$<G,+,\times> \mathcal{满足:} \\\\ (a,b)+(c,d) = (a+c,b+d) \\\\ (a,b) \times (c,d) = (ac+bdw,ad+bc)$

显然G是一个环。既然有了结合律。就可以快速幂。

那么上述方程的解为

$x = (b+i)^{\frac{p+1}{2}}$

证明如下：

$\begin{aligned} x^2 & = (b+i)^{p+1} \\ & = (b+i)^p(b+i) \end{aligned}$

其中，由二项式定理

$(b+i)^p = \sum_{k=0}^p C_p^kb^ki^{p-k}$

显然k≠0 or p，所以

$C_p^k \equiv 0 \pmod p$

所以有

$(b+i)^p \equiv b^p +i^p \equiv b^{p-1}b +w^{\frac{p-1}{2}} \equiv b-i\pmod p$

所以有

$x^2 \equiv (b-i)(b+i) \equiv b^2 - w \equiv a \pmod p$

于是我们就得到了一个优秀的 O ( log ⁡ p )的求解奇质数二次剩余的方法了。

Python实现。其实是网上扒的，小改了一下。

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