二次剩余

勒让德符号

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

即：

$$\large{ \left( \frac{n}{p} \right) \equiv n^{\frac{p - 1}{2}} (\bmod p) }$$

定理

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

流程

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

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

理论可以见 > here <。

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;