二次剩余

给出 $N,p$ ，求解方程

$$x^2 \equiv N \pmod{p} $$

$p$ 是奇素数。

欧拉判别准则

勒让德记号：

$$\left(\frac{n}{p}\right)=\begin{cases} 1&(\,p\nmid n\ \text{且}\,n\,\text{是模}\,p\,\text{的二次剩余})\\ -1&(\,p\nmid n\ \text{且}\,n\,\text{是模}\,p\,\text{的二次非剩余})\\ 0&(\,p\mid n) \end{cases}$$

有欧拉判别准则

$$\left(\frac{n}{p}\right)=n^{\frac{p-1}2} $$

可以由费马小定理证得。

Cipolla

随机一个整数 $a\in[0,p)$ ，令 $\omega^2=a^2-n$ 使得 $\left(\frac{\omega^2}{n}\right)=-1$ 。可证期望两次能随到符合的 $a$ 。

便有解 $(a+\omega)^{\frac{p+1}{2}}$ ，另一解就是其相反数。

证明

由 $(a+b)^p\equiv a^p+b^p\pmod{p}$ ，令 $x\equiv(a+\omega)^{\frac{p+1}2}\pmod{p}\Rightarrow x^2\equiv (a^p+\omega^p)(a+\omega)\pmod p$ 。

又由 $\left(\frac{\omega^2}{n}\right)\equiv \omega^{p-1}\equiv-1,a^{p-1}\equiv1$ ， $x^2\equiv (a^p+\omega^p)(a+\omega)\equiv(a-\omega)(a+\omega)\equiv a^2-\omega^2\pmod p$ 。所以 $x^2\equiv n\pmod p$ 。

实现

求 $(a+\omega)^{\frac{p+1}{2}}$ 这样知 $\omega^2$ 而不知 $\omega$ 的问题，可以把 $\omega$ 看作是虚数单位。

代码

	ll N1;
	struct Complex {
		ll a, b;
		Complex (ll a = 0, ll b = 0): a(a), b(b) {}
	};

	bool operator ==  (Complex a, Complex b) { return a.a == b.a && a.b == b.b; }
	Complex operator * (Complex a, Complex b) {
		return Complex((a.a * b.a % mod + N1 * a.b % mod * b.b) % mod, 
				(a.b * b.a % mod + a.a * b.b % mod) % mod);
	}

	Complex qpow (Complex a, int b) {
		Complex ans = Complex(1, 0);
		for (; b; b >>= 1, a = a * a)
			if (b & 1) ans = ans * a;
		return ans;
	}

	ll qpowR (ll a, int b) {
		ll ans = 1;
		for (; b; b >>= 1, a = a * a % mod) 
			if (b & 1) ans = ans * a % mod;
		return ans;
	}

	void Cipolla () {
		ll a = rand() % mod;
		N1 = (a * a % mod - n + mod) % mod;
		for (; qpowR(N1, (mod - 1) / 2) != mod - 1; a = rand() % mod, 
				N1 = (a * a % mod - n + mod) % mod);
		ll x1 = qpow(Complex(a, 1), (mod + 1) / 2).a, x2 = mod - x1;
		if (x1 > x2) swap(x1, x2);
		if (x1 == x2) printf ("%lld\n", x1);
		else printf ("%lld %lld\n", x1, x2);
	}