Liveddd's Blog

愛にできることはまだあるかい

二次剩余

发表于 更新于 分类于
本文字数： 4.4k 阅读时长 ≈ 10 分钟

二次剩余，模意义开根。

1.定义

对于整数 $a,p$ 满足 $(a,p)=1$，若存在整数 $x$ 使得：

则称 $a$ 为模 $p$ 的二次剩余，否则为模 $p$ 的非二次剩余。我们只讨论 $p$ 为奇素数的情况。

2.欧拉准则

2.1 内容

用于快速判断 $a$ 是否为二次剩余。

2.2 证明

首先使用费马小定理，有 $a^{p-1}\equiv 1\pmod p$，故：

所以对于任意满足 $(a,p)=1$ 的 $a$ 均有 $a^{p-1}\equiv \pm 1\pmod p$。

我们先证明 “ $a$ 是模 $p$ 的二次剩余” 是 “ $a^{\frac{p-1}{2}}\equiv1\pmod p$” 的充要条件。

  1. 充分性
    设 $a\equiv x^2\pmod p$，则 $a^{\frac{p-1}{2}}\equiv x^{p-1} \equiv 1\pmod p$。
  2. 必要性
    因为 $p$ 为奇素数，所以必然存在原根。设 $g$ 是模 $p$ 的一个原根，且 $a\equiv g^k\pmod p$。那么 $a^{\frac{p-1}{2}}\equiv g^{\frac{k}{2}(p-1)}\equiv 1\pmod p$，所以 $\frac{k}{2}(p-1)$ 是 $\varphi (p)=p-1$ 的倍数，所以 $k$ 是偶数，故令 $x\equiv g^{\frac{k}{2}}\pmod p$ 即可使 $a^{\frac{p-1}{2}}\equiv1\pmod p$。

既然” $a$ 是模 $p$ 的二次剩余” 是 “ $a^{\frac{p-1}{2}}\equiv1\pmod p$” 的充要条件，又因为 $a^{p-1}\equiv \pm 1\pmod p$，那么对应的，” $a$ 是模 $p$ 的非二次剩余” 是 “ $a^{\frac{p-1}{2}}\equiv -1\pmod p$” 的充要条件。欧拉准则就成立了。

这样还有一个推论：设 $a$ 为模 $p$ 的二次剩余 ，当 $\frac{p-1}{2}$ 是奇数时，$-a$ 是模 $p$ 的二次非剩余。相反，当 $\frac{p-1}{2}$ 是偶数时，$-a$ 是模 $p$ 的二次剩余。

3.Cipolla 算法

3.1 二次剩余数量

对于方程 $x^2\equiv a\pmod p$，设 $x_1,x_2$ 为方程两个解，那么 $x_1^2-x_2^2\equiv 0\pmod p$，所以 $x_1\equiv -x_2\pmod p$，即 $x_1,x_2$ 互为模 $p$ 意义下相反数。所以对于 $p$ 以内 $\frac{p-1}{2}$ 对模 $p$ 意义下相反数对应着 $\frac{p-1}{2}$ 个 $a$。所以模 $p$ 意义下二次剩余和非二次剩余个数均为 $\dfrac{p-1}{2}$。

3.2 算法

我们首先随便找到一个 $r$ 使得 $r^2-a$ 为二次非剩余。上面我们已经研究过非二次剩余数量为 $\dfrac{p-1}{2}$，我们随机选取期望两次即可得到一个 $r$。

类比实数域向复数域的推广，我们定义一个 $i^2=r^2-a$，可以将该域中所有数表示为 $a+bi$ 的形式，其中 $a,b$ 均为模 $p$ 意义下的数。其实可以证明这是一个环，这里略去。接下来推导都是在模 $p$ 意义下进行。

我们发现直接求 $(r+i)^{\frac{p+1}{2}}$。我们简单证明一下。

由费马小定理得到：$r^p\equiv r\pmod p$。并且有：

所以得到：

所以我们得到 $(r+i)^{p+1}\equiv a\pmod p$，所以得到 $(r+i)^{\frac{p+1}{2}}\equiv x\pmod p$。我们使用快速幂求即可。

整个算法时间复杂度为 $\mathcal O(\log p)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstdio>
#include<random>

using namespace std;
using ll = long long;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int T;
namespace Cipolla
{
    int n,a,p;
    int x0,x1;
    mt19937 rnd(114514);
    inline int adj(int x){return x>=p?x-p:x;}
    struct Complex
    {
        int x,y;
        const Complex operator*(const Complex &t)const
        {
            return (Complex){adj(1ll*x*t.x%p+1ll*y*t.y%p*adj(1ll*a*a%p-n+p)%p),
                adj(1ll*x*t.y%p+1ll*y*t.x%p)};
        }
    };
    inline int qpow(int x,int k)
    {
        int res=1;
        while(k)
        {
            if(k&1)res=1ll*res*x%p;
            x=1ll*x*x%p;
            k>>=1;
        }
        return res;
    }
    inline int legendre(int a,int p){return qpow(a,(p-1)/2);}
    inline void get_a()
    {
        for(a=0;legendre(adj(1ll*a*a%p-n+p),p)==1;a=rnd()%p);
    }
    inline Complex qpow(Complex x,int k)
    {
        Complex res=(Complex){1,0};
        while(k)
        {
            if(k&1)res=res*x;
            x=x*x;
            k>>=1;
        }
        return res;
    }
    inline void solve()
    {
        n%=p;
        if(legendre(n,p)==p-1)return x0=-1,void();
        get_a();
        x0=qpow((Complex){a,1},(p+1)/2).x,x1=p-x0;
        if(x0>x1)swap(x0,x1);
    }
};
int main()
{
    read(T);
    while(T--)
    {
        read(Cipolla::n,Cipolla::p);
        if(!Cipolla::n){puts("0");continue;}
        Cipolla::solve();
        if(Cipolla::x0==-1)puts("Hola!");
        else printf("%d %d\n",Cipolla::x0,Cipolla::x1);
    }
    return 0;
}