二次剩余

勒让德记号

定义勒让德记号：

$$\begin{pmatrix} a\over p \end{pmatrix} = \begin{cases} 0 & a=0 \\ +1 & a^{(p-1)\over 2} \equiv 1 \pmod p,此时a在模p的意义下有二次剩余 \\ -1 & a^{(p-1)\over 2} \equiv -1 \pmod p ,此时a在模p意义下没有二次剩余 \\ \end{cases}$$

---

求二次剩余

解方程$x^2\equiv n \pmod p$ （$p$为奇质数）
随机选取一个数$a$，令$w=a^2-n$
当$w$不是$p$的二次剩余时（概率为0.5）
有$x=(a+\sqrt{w})^{p+1\over 2}$
证明：

$$(a+\sqrt{w})^p=C_{p}^{0}a^p+C_{p-1}^{2}a^{p-1}\sqrt{w}...+C_{p}^{p}\sqrt{w}^p$$

由于对于$C_{p}^{i}$，分母中不含有$p$，所以分子中的$p$一定不会被约掉
所以第$2$项至第$p$项在模$p$的意义下均为$0$

$$\therefore(a+\sqrt{w})^p\equiv a^p+\sqrt{w}^p(mod\ p)$$

由费马小定理得$a^{p-1}\equiv 1\\ \therefore a^p\equiv a\\ \because w^{p-1\over 2}\equiv -1\\ \therefore \sqrt{w}^{p-1}\equiv -1\\ \therefore \sqrt{w}^p\equiv -\sqrt{w}\\ \therefore (a+\sqrt{w})^p\equiv a^p+\sqrt{w}^p\equiv a-\sqrt{w}\\ \therefore x^2\equiv ((a+\sqrt{w})^{p+1\over 2})^2\\ \equiv (a+\sqrt{w})^{p+1}\\ \equiv (a+\sqrt{w})(a+\sqrt{w})^p\\ \equiv (a+\sqrt{w})(a-\sqrt{w})\\ \equiv a^2-w\\ \equiv a^2-(a^2-n)\\ \equiv n$
证毕

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <ctime>
#define PII pair<int,int>
#define MP make_pair
#define fir first
#define sec second
#define PB push_back
#define db long double
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
int mod;
int Pow(int x,int y) {
	int res=1;
	while(y) {
		if(y&1) res=res*(ll)x%mod;
		x=x*(ll)x%mod,y>>=1;
	}
	return res;
}
int _w;
struct node {
	int x,y;
	node(int x=0,int y=0): x(x),y(y) {}
	friend node operator * (node A,node B) { return node((A.x*(ll)B.x+A.y*(ll)B.y%mod*_w)%mod,(A.x*(ll)B.y+A.y*(ll)B.x)%mod); }
};
node Pow(node x,int y) {
	node res=node(1,0);
	while(y) {
		if(y&1) res=res*x;
		x=x*x; y>>=1;
	}
	return res;
}
int main() {
	int n; scanf("%d%d",&mod,&n);
	if(!n) { printf("0"); return 0; }
	if(mod==2) { printf("1"); return 0; }
	if(Pow(n,(mod-1)/2)==mod-1) { printf("No Solution\n"); return 0; }
	srand(time(0));
	while(1) {
		int a=(rand()|((rand()*1ll)<<16))%mod; _w=((a*(ll)a-n)%mod+mod)%mod;
		if(Pow(_w,(mod-1)/2)==mod-1) {
			node ans=Pow(node(a,1),(mod+1)/2);
			int x1=ans.x,x2=mod-ans.x;
			if(x1>x2) swap(x1,x2);
			printf("%d ",x1);
			if(x1!=x2) printf("%d",x2);
			return 0;
		}
	}
}

---

upd 2020.2.29

勒让德记号相关证明：

因为 $(a^{\frac{p-1}{2}})^2 \equiv 1(p\nmid a)$ ，所以 $a^{\frac{p-1}{2}} \equiv \pm 1$ 。

$a^{\frac{p-1}{2}}\equiv 1$：用 $g$ 表示 $p$ 的一个原根，$a\equiv g^k$ ，那么 $g^{k\frac{p-1}{2}} \equiv 1$，所以 $k \frac{p-1}{2} \mid p-1$ ，所以 $2 \mid k$ ，$\pm g^{\frac{k}{2}}$ 为 $a$ 的二次剩余。

$a^{\frac{p-1}{2}}\equiv -1$：若存在 $x$ 满足 $x^2 \equiv a$，那么 $a^{\frac{p-1}{2}} = x^{p-1} = -1$，矛盾。