二次剩余

定理1：n^(p-1)/2≡±1(mod p)，p是奇素数。

定理2：给出方程 x²≡n(mod p)，其中p是奇素数，则方程有解当且仅当n^(p-1)/2≡1(mod p)。

定理3：若方程 x²≡w(mod p)，其中p是奇素数无解，设a满足a²=w+n，则(a+sqrt(w))^p+1≡n(mod p)，也即对任意a²>w，则有(a+sqrt(w))^p+1≡a²-w(mod p)。

下面开始正文。我们为啥要搞这个二次剩余呢？问题的起源在于，如果我们已知一个 x²≡n(mod p)，我们想知道x对p的模，也即，同余方程两边同时开根号，这能做到吗？

当n不是p的二次剩余时，显然这样的x并不存在，自然无法开根号。但是当n是p的二次剩余时，一定能，而且若n不等于0，则一定有两个x，满足x₁+x₂≡0(mod p)，均是该二次剩余方程的解。

给出求sqrt(n)的板子，如果不存在返回-1。

 1 #include <iostream>   
 2 #include <ctime>
 3 using namespace std;
 4 typedef long long ll;
 5 #define random(a,b) (rand()%(b-a+1)+a)
 6 ll quick_mod(ll a, ll b, ll c){
 7     ll ans = 1;
 8     while(b){
 9         if(b%2==1) ans=(ans*a)%c;
10         b/=2;
11         a=(a*a)%c;
12     }
13     return ans;
14 }
15 ll p;
16 ll w;//二次域的D值,使同余方程无解的那个值 
17 struct QuadraticField//二次域
18 {
19     ll x, y;
20     QuadraticField operator*(QuadraticField T)//二次域乘法重载
21     {
22         QuadraticField ans;
23         ans.x = (this->x*T.x%p + this->y*T.y%p*w%p) % p;
24         ans.y = (this->x*T.y%p + this->y*T.x%p) % p;
25         return ans;
26     }
27     QuadraticField operator^(ll b)//二次域快速幂
28     {
29         QuadraticField ans;
30         QuadraticField a = *this;
31         ans.x = 1;
32         ans.y = 0;
33         while (b)
34         {
35             if (b & 1)
36             {
37                 ans = ans*a;
38                 b--;
39             }
40             b /= 2;
41             a = a*a;
42         }
43         return ans;
44     }
45 };
46  
47 ll Legender(ll a)//求勒让德符号
48 {
49     ll ans=quick_mod(a, (p - 1) / 2, p);
50     if (ans + 1 == p)//如果ans的值为-1，%p之后会变成p-1。
51         return -1;
52     else
53         return ans;
54 }
55  
56 ll Getw(ll n, ll a)//根据随机出来a的值确定对应w的值
57 {
58     return ((a*a - n) % p + p) % p;//防爆处理
59 }
60  
61 ll Solve(ll n)//没有解返回-1 
62 {
63     ll a;
64     if (p == 2)//当p为2的时候，n只会是0或1，然后0和1就是对应的解
65         return n;
66     if (Legender(n) == -1)//无解
67         return -1;
68     srand((unsigned)time(NULL));
69     while (1)//随机a的值直到有解
70     {
71         a = random(0, p - 1);
72         w = Getw(n, a);
73         if (Legender(w) == -1)
74             break;
75     }
76     QuadraticField ans,res;
77     res.x = a;
78     res.y = 1;//res的值就是a+根号w
79     ans = res ^ ((p + 1) / 2);
80     return ans.x;
81 }
82  
83 int main()
84 {
85     ll n,ans1,ans2;
86     while (scanf("%lld%lld",&n,&p)!=EOF)
87     {
88         n %= p;
89         ans1 = Solve(n);
90         ans2 = p - ans1;//一组解的和是p
91     }
92 }