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;
    }
}
分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注