二次剩余

发表于 更新于 本文字数： 1.5k 阅读时长 ≈ 1 分钟
二次剩余

勒让德符号

(np)={1,n在模 p 意义下的二次剩余−1,n在模 p 意义下的非二次剩余0,n≡0( mod p) \large{ \left( \frac{n}{p} \right) = \begin{cases} 1, &n \text{在模 $ p $ 意义下的二次剩余}\\\\ -1, &n \text{在模 $ p $ 意义下的非二次剩余}\\\\ 0, &n \equiv 0 (\bmod p) \end{cases} }

即：

(np)≡np−12( mod p) \large{ \left( \frac{n}{p} \right) \equiv n^{\frac{p - 1}{2}} (\bmod p) }

定理

n2≡(p−n)2p 的二次剩余和二次非剩余的个数均为 p−12 （除 0） \large{ n^2 \equiv (p - n)^2 } \\\\ \large{ \text{$ p $ 的二次剩余和二次非剩余的个数均为 $ \frac{p - 1}{2} $ （除 $ 0 $）} }

流程

  1. 随机找一个 (a2−np)=−1 \left( \frac{a^2 - n}{p} \right) = -1 ，令 ω=a2−n \omega = \sqrt{a^2 - n} 。
  2. 合法解 x≡(a+ω)p+12( mod p) x \equiv (a + \omega)^{\frac{p + 1}{2}} (\bmod p) 。

过程中实数运算需要用结构体维护正数部分和根号部分。

理论可以见 > here <。 

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
namespace Math {
	int n, p, w; struct P { int x, y; };
	inline P mul(const P &x, const P &y, int p) {
		P res;
		res.x = (1ll * x.x * y.x + 1ll * x.y * y.y % p * w % p) % p;
		res.y = (1ll * x.y * y.x + 1ll * x.x * y.y) % p;
		return res;
	}
	int ksm(int x, int y, int p) {
		int w = 1;
		for(; y; y >>= 1, x = 1ll * x * x % p) if(y & 1) w = 1ll * w * x % p;
		return w;
	}
	int Pow(P x, int y, int p) {
		P w = (P){1, 0};
		for(; y; y >>= 1, x = mul(x, x, p)) if(y & 1) w = mul(w, x, p);
		return w.x;
	}
	int calc(int x, int p) {
		x %= p; if(p == 2) return x;
		if(ksm(n, (p - 1) / 2, p) == p - 1) return -1;
		int ans;
		for(;;) {
			ans = rand() % p, w = (1ll * ans * ans % p - x + p) % p;
			if(ksm(w, (p - 1) / 2, p) == p - 1) break;
		}
		P t = (P){ans, 1}; return Pow(t, (p + 1) / 2, p);
	}
	int Sqrt(int x, int pr) { n = x, p = pr; if(!x) return 0; return calc(x, p); }
} using Math::Sqrt;