二次剩余

解如下的方程

$$x^2 \equiv \, n \ (mod \; p)$$

前置

我们引入 $Legendre$ 记号

$$(\frac p n) = \begin{cases} 1 &\text { $p$ 为 $n$ 的二次剩余} \\ -1 &\text { $p$ 为 $n$ 非二次剩余} \\ 0 &\text{$n \equiv 0$} \end{cases}$$

引理一：

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

证明：
若 $n$ 为 $p$ 的 二次剩余，则 $x^2 \equiv \ n$ 所以 $x^{p-1} \equiv1$
费马小定理显然
反之则 $x^{p-1} \equiv -1$ , $x$显然不存在

引理二：
对于 $a$ 与 $a$ 互质的奇素数 $p$ 有

$$a^{\frac{p-1}{2}} \; \equiv \pm1 \;(mod \; p)$$

证明：

由费马小定理知：

$$a^{p-1} \equiv 1\;(mod\;p)$$

令 $2q = p-1$ 则有

\begin{align} a^{2q} &\equiv 1 \ (mod \; p)\nonumber\\ a^{2q}-1 &\equiv 0 \;\nonumber\\ (a^q+1)(a^q-1) &\equiv 0\;\nonumber\\ a^q &\equiv \pm1\nonumber\\ a^{p-1} &\equiv 1\nonumber\\ a^{\frac{p-1}{2}} &\equiv \pm 1 (mod \ p)\nonumber \end{align}

开摆

令 $w = a^2 - n$ 为 $mod\;p$ 的二次非生育 ， 则 $x = (a + \sqrt{w})^{\frac{p+1}{2}}$ 为方程的解

证明：

$$x^2 \equiv n \equiv a^2 - w \\ \equiv (a + \sqrt{w})(a - \sqrt{w})$$

费马小定理 $a^p \equiv a$

$\therefore a^2 \equiv a^{p+1}$

引理一知 $\sqrt {w}^{p-1} \equiv -1$

在模 $p$ 意义一下二项式定理

$$(a + b)^p \equiv a^p + b^p$$

所以

\begin{align} x^2 &\equiv (a + \sqrt{w})(a - \sqrt{w}) \nonumber \\ \nonumber &\equiv (a + \sqrt{w})(a^p + \sqrt {w}^{p-1}\times \sqrt{w}) \\\nonumber &\equiv (a + \sqrt{w})(a^p + \sqrt {w}^{p}) \nonumber \\ \nonumber &\equiv (a + \sqrt{w})^{p+1}\\ \nonumber x&\equiv (a+\sqrt{w})^{\frac{p+1}{2}} \end{align}

所以我们随机化整 $w$ 求解即可

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
86
87
88
89
90
91
92
93
94
95
96
97
98

#include<bits/stdc++.h>
#define  ll long long
using namespace std;
int t;
ll n,p,w;

struct dot
{
    ll x,y;

    dot operator * (dot b)
    {
        dot ans;
        ans.x = ((x*b.x%p + y*b.y%p*w%p) + p)%p;
        ans.y = ((x*b.y%p + y*b.x%p) + p)%p;
        return ans;
    } 
};


ll ksm(ll a,ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b&1)
        ans =a*ans%p;
        a = a*a%p;
        b >>= 1;
    }
    return ans;
}

ll ksm_w(dot a,ll b)
{
    dot ans = {1,0};
    while(b)
    {
        if(b&1)
        ans = a*ans;
        a = a*a;
        b >>= 1;
    }
    return ans.x%p;
}

ll solve(ll n)
{
    n %= p;
    if(p == 2) return n;

    if(ksm(n,(p-1)/2) == p-1)
    return -1;

    ll a;
    while(1)
    {
        a = rand()%p;
        w = (ksm(a,2)-n +p)%p;

        if(ksm(w,(p-1)/2) == p-1)
        break;
    }
    dot x = {a,1};

    return ksm_w(x,(p+1)/2);
}

int main()
{
    srand(time(0));

    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&p);
        if(!n)
        {
            printf("0\n");
            continue;
        }

        ll ans1 = solve(n),ans2;
        if(ans1 == -1) printf("Hola!\n");
        else
        {
            ans2 = p-ans1;
            if(ans2 < ans1) swap(ans1,ans2);
            
            if(ans1 == ans2)
            printf("%lld\n",ans1);
            else
            printf("%lld %lld\n",ans1,ans2);
        }
    }

    return 0;
}

注意 $w$ 类似于复数 要重载 $*$ 运算

wssb