前言

本来是为了多项式来学学,结果被震惊了......

正题

给定 $n,p$,保证 $p$ 是奇质数,求解 $x^2\equiv n\ (\bmod\ p)$。

模意义开根

以下运算都在模 $p$ 的意义下。

首先称使得 $x^2\equiv n\ (\bmod\ p)$ 有解的 $n$ 是二次剩余,无解的是非二次剩余。

解的数量

对于二次剩余 $n$,假设方程有多个解,取出其中两个 $x_0,x_1$。

有:$x_0^2\equiv x_1^2\ (\bmod\ p)$

移项得到:

$$(x_0-x_1)(x_0+x_1)\equiv 0\ (\bmod\ p)$$

但是 $x_0\ne x_1$,所以 $x_0+x_1=0$。也就是他们一定互为相反数。又模奇质数 $p$,所以 $x_0,x_1$ 在模 $p$ 意义下不等。所以该方程仅有 $2$ 个解,且两个解互为相反数。

反过来,任意一对相反数,都对应着一个二次剩余,且这些二次剩余显然两两不同。所以二次剩余的个数是 $\lfloor \dfrac{p}{2}\rfloor=\dfrac{p-1}{2}$。


欧拉准则

用于判定 $n$ 是否是模 $p$ 意义下的二次剩余。

由费马小定理 $n^{p-1}\equiv 1\ (\bmod\ p)$,可以得到:

$$n^{2(\frac{p-1}{2})}\equiv 1\ (\bmod\ p)$$

也就是 $n^{\frac{p-1}{2}}$ 是 $1$ 开根的解。又 $1$ 开根的结果只能是 $1$ 和 $-1$,所以 $n^{\frac{p-1}{2}}$ 只能同余于 $1$ 或者 $-1$。

下面证明:$n$ 是二次剩余 $\iff$ $n^{\frac{p-1}{2}}\equiv 1\ (\bmod\ p)$。

如果 $n$ 是二次剩余,则存在 $x$ 使得 $x^2\equiv n\ (\bmod\ p)$。费马小定理可知 $x^{p-1}\equiv 1\ (\bmod\ p)$,所以:$n^{\frac{p-1}{2}}\equiv 1\ (\bmod\ p)$。

如果 $n^{\frac{p-1}{2}}\equiv 1\ (\bmod\ p)$,考虑模 $p$ 意义下的原根 $g$,$n=g^k$。那么有 $g^{k\times \frac{p-1}{2}}\equiv 1\ (\bmod\ p)$,又费马小定理有:$g^{p-1}\equiv 1\ (\bmod\ p)$,那么有 $p-1|k\times \dfrac{p-1}{2}$,也就是 $k$ 必是偶数。那么 $x^2\equiv n\ (\bmod\ p)$ 一定有解 $x=g^{\frac{k}{2}}$。

因此 $n$ 是二次剩余 $\iff$ $n^{\frac{p-1}{2}}\equiv 1\ (\bmod\ p)$。

那么就有 $n$ 是非二次剩余 $\iff$ $n^{\frac{p-1}{2}}\equiv -1\ (\bmod\ p)$


$\text{Cipolla}$ 算法

解方程 $x^2\equiv n\ (\bmod\ p)$。

找到一个 $a$ 使得 $a^2-n$ 是非二次剩余,而非二次剩余的数量接近 $\dfrac{p}{2}$,所以随机一下,期望 $2$ 次就可以得到一个。

定义 $i$ 使得 $i^2\equiv a^2-n\ (\bmod\ p)$

可以考虑用类似复数的表示方法,把所有数表示为 $A+Bi$ 的形式,与实部,虚部类似。

那么有 $(a+i)^{p+1}\equiv n\ (\bmod\ p)$。

先证明两个引理:

$i^p\equiv i\ (\bmod\ p)$

证明:

$$i^p\equiv i\times (i^2)^{\frac{p-1}{2}}\equiv i\times (a^2-n)^{\frac{p-1}{2}}\equiv -i\ (\bmod\ p)$$

$(x+y)^p\equiv x^p+y^p\ (\bmod\ p)$

证明:

二项式定理拆开之后,由于 $p$ 是质数,所以除 $\binom{p}{0},\binom{p}{p}$ 之外的组合数,都会因为阶乘上有消不掉的 $p$ 而被模成 $0$,所以最后 $(x+y)^p\equiv \binom{p}{0}x^p y^0+\binom{p}{p}x^0 y^p\equiv x^p+y^p\ (\bmod\ p)$。

接着证明 $(a+i)^{p+1}\equiv n\ (\bmod\ p)$。

$$(a+i)^{p+1}\equiv (a+i)^p(a+i)\equiv (a^p+i^p)(a+i)\equiv (a-i)(a+i)\equiv a^2-i^2\equiv n\ (\bmod\ p)$$

因此 $(a+i)^{\frac{p+1}{2}}$ 和其相反数是方程 $x^2\equiv n\ (\bmod\ p)$ 的两个解。

证明 $(a+i)^{\frac{p+1}{2}}$ 的“虚部” 为 $0$。

设 $(a+i)^{\frac{p+1}{2}}=A+Bi$,则 $B\ne 0$。

那么先要满足 $(A+Bi)^2\equiv n\ (\bmod\ p)$。

拆掉括号有:

$$A^2+2ABi+B^2i^2\equiv n\ (\bmod\ p)$$

移项:

$$A^2+B^2i^2-n\equiv -2ABi\ (\bmod\ p)$$

不难发现左边“虚部”为 $0$,那右边“虚部”就需要也是 $0$。也就是 $AB=0$,又设了 $B\ne 0$,所以 $A=0$。

也就是 $(Bi)^2\equiv n\ (\bmod\ p)$,把 $B^2$ 求逆元乘过去可得:$i^2\equiv n\times B^{-2}\ (\bmod\ p)$,又 $n,B^{-2}$ 都是二次剩余,那么他们的乘积必是二次剩余。又 $i^2$ 不是二次剩余,所以与之前的设定矛盾。

也就是 $B=0$!

板子:

P5491 【模板】二次剩余

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
//#define ull unsigned long long
#define LL long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define scd second
#define inv(x) qpow((x),mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define vec vector

const int MAXN = 1;
const int INF = 2e9;
const double PI = acos(-1);
const double eps = 1e-6;
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int T, n, m, ans1, ans2;
int i2, mod;

struct Complex {
    int real, imag;
    Complex(int R = 0, int I = 0) : real(R), imag(I) {}
    Complex operator * (const Complex &b) const {
        return Complex((real * b.real % mod + i2 * imag % mod * b.imag % mod) % mod, (imag * b.real % mod + real * b.imag % mod) % mod);
    }
};

template<typename T> inline void read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    a *= f;
}

int qpow(int x, int b) {
    int res = 1;
    for(; b; b >>= 1, (x *= x) %= mod) if(b & 1) (res *= x) %= mod;
    return res;
}

Complex qpow(Complex x, int b) {
    Complex res = Complex(1, 0);
    for(; b; b >>= 1, x = x * x) if(b & 1) res = res * x;
    return res;
}

bool chk(int x) {
    return qpow(x, (mod - 1) >> 1) == 1 ? true : false;
}

int randint(int l, int r) {
    return rand() % (r - l + 1) + l;
}

void Solve(int n, int p, int &x0, int &x1) {
    mod = p;
    int a = randint(0, mod - 1);
    while(!a || chk(((a * a % mod - n) % mod + mod) % mod)) a = randint(0, mod - 1);
    i2 = ((a * a % mod - n) % mod + mod) % mod;
    Complex tmp = qpow(Complex(a, 1), (mod + 1) >> 1);
    assert(!tmp.imag);
    x0 = (qpow(Complex(a, 1), (mod + 1) >> 1).real % mod + mod) % mod;
    x1 = ((mod - x0) % mod + mod) % mod;
}

signed main () {
#ifdef FILE
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    srand(5224999);
    read(T);
    while(T--) {
        read(n); read(m);
        mod = m;
        if(!n) {
            puts("0");
            continue;
        }
        if(!chk(n)) {
            puts("Hola!");
            continue;
        }
        Solve(n, m, ans1, ans2);
        if(ans1 == ans2) printf("%lld\n",ans1);
        else printf("%lld %lld\n",min(ans1, ans2), max(ans1, ans2));
    }
    return 0;
}

标签: 数学, 二次剩余

已有 2 条评论



添加新评论