二次剩余问题是求解满足 \(x^2\equiv n\pmod P\) 的 \(x\) 。

BSGS求解

可以使用 \(\text{BSGS}\) 在 \(O(\sqrt{P}\log P)\) 的复杂度内求解。

数论基础

二次剩余

对于式子 \(x^2\equiv n\pmod P\) ，如果存在 \(x\) 则称 \(n\) 为 \(P\) 的二次剩余，如果不存在则称 \(n\) 为 \(P\) 的二次非剩余。

勒让德符号

记：

\[ \left(\frac{n}{p}\right)= \begin{cases} 1&n\not\equiv0\pmod p\And n是p的二次剩余\\ -1&n\not\equiv0\pmod p\And n是p的二次非剩余\\ 0&n\equiv0\pmod p \end{cases} \]

欧拉判别准则

\[ \left(\frac{n}{p}\right)\equiv n^{\frac{p-1}{2}}\pmod p \]

二次剩余与二次非剩余个数相同

对于方程 \(x^2\equiv n\pmod P\) 如果有两个不同的解 \(u\) 和 \(v\) ，则有 \(u^2-v^2\equiv0\pmod P\) ，于是 \((u-v)(u+v)\equiv0\pmod P\) ，又 \(u-v\not\equiv 0\pmod P\) 那么必有 \(u+v\equiv0\pmod P\) ，于是对于任意的数 \(n\in[1,P-1]\) 总有 \(n^2\equiv(P-n)^2\pmod P\) ，那么 \(P\) 的二次剩余数量 \(\le\frac{P}{2}\) ，实际上取等。

严格证明看oi-wiki

Cipolla算法

Step1 随机

随机找到一个 \(a\) 满足 \(a^2-n\) 为 \(P\) 的二次非剩余，由于 \(P\) 的二次剩余与二次非剩余个数相同，则找到 \(a\) 的期望次数为 \(2\) 次。

Step2 扩域

令 \(\omega^2=a^2-n\) ，则我们建立了一个新域 \(F_{p^2}\) ，其中的数可以表示为 \(a+b\omega\) ，运算为四则运算。

Step3 得出答案

有结论答案为 \((a+\omega)^{\frac{p+1}{2}}\) ，模拟复数乘法即可得到一个解 \(x\) ，另一个解为 \(P-x\) 。

模板

namespace remain2 {
    // _P 为奇素数
	int _P; ll I; void setP(int P_) { _P = P_; }

	struct cplx { ll x, y; cplx(ll x_ = 0, ll y_ = 0) : x(x_), y(y_) {} };
	bool operator== (cplx a, cplx b) { return a.x == b.x && a.y == b.y; }
	cplx operator*  (cplx a, cplx b) {
		return cplx( (a.x * b.x + I * a.y % _P * b.y) % _P,
					 (a.x * b.y + a.y * b.x) % _P           );
	}
	cplx qpow(cplx a, int b) {
		cplx res = 1;
		while(b) {
			if(b & 1) res = res * a;
			a = a * a, b >>= 1;
		}
		return res;
	}

	bool residue(int x) { // x 是否为模 _P 意义下的二次剩余
		return qpow(x, (_P - 1) / 2) == 1;
	}

	vi cipolla(int n) { // solve x^2 = n (mod _P)
        if(n == 0) return {0};
		if(!residue(n)) return {-1};
		ll a = get(1, _P - 1);
		while(residue((a * a - n + _P) % _P))
			a = get(1, _P - 1);
		I = (a * a - n + _P) % _P;
		int x1 = qpow(cplx(a, 1), (_P + 1) / 2).x;
		int x2 = _P - x1;
        if(x1 > x2) swap(x1, x2);
		if(x1 == x2) return {x1};
		else return {x1, x2};
	}
};
using namespace remain2;

例题 CF763C

题意

给定 \(n\) 和 \(P\in Prime\) ，以及长度为 \(n\) 的互不相同的序列 \(a\) ，问序列 \(a\) 是否是模 \(P\) 意义下的等差数列。

题解

令等差数列为 \(\{x+di\}\) 考虑有结果：

\[ \sum_{i=0}^{n-1}a_i\equiv nx+\frac{n(n-1)}{2}d\\ \sum_{i=0}^{n-1}a_i^2\equiv nx^2+n(n-1)d+\frac{(n-1)n(2n-1)}{6}d\\ \left(\sum_{i=0}^{n-1}a_i\right)^2=n^2x^2+\frac{n^2(n-1)^2}{4}d^2+n(n-1)dx \]

则有：

\[ n\sum_{i=0}^{n-1}a_i^2-\left(\sum_{i=0}^{n-1}a_i\right)^2=\frac{n^2(n-1)(n+1)}{12}d^2 \]

\(n=P\) 与 \(n=P-1\) 情况不难，对于其他情况 \(n^2(n-1)(n+1)\) 存在逆元，则可以求出 \(d^2\equiv t\pmod P\) ，做二次剩余得到至多 \(2\) 个可能的 \(d\) ，通过等差数列求和公式得到 \(x\) ，再逐一检验即可。

THC

二次剩余学习笔记