Cipolla

问题

给定 $n​$, 在模 $p​$意义下求 $x​$，使得 $x^2\equiv n \pmod p​$。其中 $p​$是一个奇素数。

原理

为了解决这个问题，我们首先需要知道以下几个定理。

定理 1：

使得 $x^2\equiv n \mod p​$有解的 $n​$在 $[0,p-1]​$有恰好 $\frac{p+1}{2}​$个。

证明 1：

假设有两个不同的数它们的平方在模意义下相等，则有：
$$
a^2-b^2\equiv 0\pmod p\\
(a+b)(a-b)\equiv 0\pmod p
$$
又因为，$a,b$不相等，所以 $a+b=p$。这说明：1. 一个数如果存在二次剩余，那么一定有两个二次剩余，且这两个数和为 $p$。2. 只有 $\frac{p+1}{2}$个数存在二次剩余 (分别为 $0^2,1^2,\cdots,(\frac{p-1}{2})^2$)。

定理 2：

$$
x^\frac{p-1}{2}\equiv\begin{cases}
1& (x 存在二次剩余)\\
-1& (x 不存在二次剩余)\\
0& (x 是 0)
\end{cases}
$$

这个判断过程也叫 “勒让德符号”。

证明 2：

当 $x=0$时定理显然成立。

如果 $x$不为 $0$，根据费马小定理，$x^{p-1}\equiv 1$，由于 $1$的二次剩余只有 $1$和 $-1$，$x^{\frac{p-1}{2}}$就只能是 $1$或 $-1$，

如果 $x$的二次剩余 $t$存在，那么 $t^{p-1}\equiv x^\frac{p-1}{2}\equiv 1$。否则，找不到 $t$，$x^\frac{p-1}{2}$就只能是 $-1$了。

定理 3：

如果 $a^2-n$没有二次剩余，那么 $n$有二次剩余，并且 $n$的二次剩余就是 $(a+\sqrt{a^2-n})^\frac{p+1}{2}$。

证明 3：

因为 $a^2-n$没有二次剩余，因此我们直接用无理数 $\sqrt{a^2-n}$表示它。

将 $(a+\sqrt{a^2-n})^{p+1}$展开：
$$
\begin{aligned}
&\sum_{i=0}^{p+1}\binom{p+1}{i}a^i\sqrt{a^2-n}^{p+1-i}\\
=&\sum_{i=0}^{p+1}\binom{(p+1)/p}{i/p}\binom{(p+1)\mod p}{i\mod p}a^i\sqrt{a^2-n}^{p+1-i}\\
=&\binom{1}{0}\binom{1}{0}\sqrt{a^2-n}^{p+1}+\binom{1}{0}\binom{1}{1}a\sqrt{a^2-n}^p+\binom{1}{1}\binom{1}{0}a^p\sqrt{a^2-n}+\binom{1}{1}\binom{1}{1}a^{p+1}\\
=&(a^2-n)(a^2-n)^\frac{p-1}{2}+a\sqrt{a^2-n}(a^2-n)^\frac{p-1}{2}+a\sqrt{a^2-n}+a^2\\
=&n
\end{aligned}
$$
得证。这同时也说明了无理数 $\sqrt{a^2-n}^{p+1}$次是 $\mathbb{P}$内的数。但是我们还不知道这个无理数的 $\frac{p+1}{2}$次究竟是不是 $\mathbb{P}$内的数。

因此下面我们需要说明 $\sqrt{a^2-n}^\frac{p+1}{2}$是 $\mathbb{P}$内的数。

由于方程 $x^2\equiv n$只有两根，并且因为 $n$有二次剩余，这两个根都在 $\mathbb{P}$内，所以既然我们找到了一个 $x$，它一定在 $\mathbb{P}$内。

算法

根据上面的定理，我们可以这样寻找一个数 $n$的二次剩余。

首先随便选一个 $a$，判断 $a^2-n$有没有二次剩余。

如果有，继续找 $a$，直到找到为止。

如果没有有，直接根据定理 3 求出 $n$的二次剩余

由于约有一半的数没有二次剩余，我们这样做的尝试次数期望是 $2$，因此算法总复杂度为 $O(\log n)$

实现

在实现中我们要手动实现一个数域 $a+b\sqrt{w}$

ll p, w;    //p 为模数，w 为数域的 “虚部”

struct NUM
{
    ll x, y;

    NUM (const ll& x0 = 0, const ll& y0 = 0) : x(x0), y(y0) {}
    NUM operator * (const NUM& t) const {return NUM((x*t.x + y*t.y%p*w) % p, (x*t.y + y*t.x) % p);}
    NUM operator % (const ll& t) const {return *this;}
};

template<typename T> T qpow(T x, int t)
{
    T a(1);
    while(t)
    {
        if(t & 1) a = a * x % p;
        x = x * x % p;
        t >>= 1;
    }
    return a;
}

ll legend(ll a) {return qpow(a, (p-1)/2);}  //勒让德符号，用于判断 a 是否存在二次剩余

ll root(ll n)
{
    if(n == 0) return 0;
    if(legend(n) == p-1) return -1;
    while(1)
    {
        ll a = rand() % (p-2) + 1; w = (a*a-n+p)%p;
        ll l = legend(w);
        if(l == p-1) return qpow(NUM(a, 1), (p+1)/2).x;
    }
}