Introduction to Quadratic Residue

定义

令$p$为奇质数。

• 定义 1 对于一个整数$n$，若存在整数$x$，使得$x^2 \equiv n \pmod p$，则称$n$是模$p$的二次剩余，否则称$n$是模$p$的二次非剩余。

• 定义 2（勒让德符号）

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

定理

• 定理 1（欧拉判别准则）

$$
\left({n \over p}\right) \equiv n^{p-1 \over 2} \pmod p
$$

证明 若$p \mid n$，则$n \equiv 0 \pmod p$，结论显然成立；

若$n$是模$p$的二次剩余，则存在$x$满足$x^2 \equiv n \pmod p$，于是$n^{p-1 \over 2} \equiv x^{p-1} \pmod p$，由费马小定理，结论成立；

若$n$是模$p$的二次非剩余，则不存在$x$满足$x^2 \equiv n \pmod p$。由逆元相关知识，对于任意$1 \le i \le p-1$，存在唯一的$1 \le j \le p-1$，使得$i \neq j$且$ij \equiv n \pmod p$。于是$1$到$p-1$这些数可以两两配对，每一对的乘积都与$n$同余，所以$(p-1)! \equiv n^{p-1 \over 2} \pmod p$，由威尔逊定理，$(p-1)! \equiv -1 \pmod p$，结论成立。

令$1 \le x, y \le p-1$。

• 定理 2

$$
x+y \equiv 0 \pmod p \Leftrightarrow x^2 \equiv y^2 \pmod p
$$

证明 $\Rightarrow$：$x+y \equiv 0 \pmod p \Rightarrow x \equiv -y \pmod p$，两边平方即得。

$\Leftarrow$： $x^2 \equiv y^2 \pmod p \Rightarrow x^2-y^2 \equiv (x-y)(x+y) \equiv 0 \pmod p$，显然$x-y \nmid p$，于是有$x+y \mid p \Rightarrow x+y \equiv 0 \pmod p$。

• 定理 3 在$1$到$p-1$中，模$p$的二次剩余和二次非剩余的个数均为${p-1 \over 2}$。

证明 由定理 2，$1$到$p-1$中有且仅有${p-1 \over 2}$个不同的二次剩余，其余${p-1 \over 2}$个即为二次非剩余。并且对于每一个二次剩余$n$，都存在两个不同的$x$满足$x^2 \equiv n \pmod p$。

算法

给定整数$n$和奇质数$p$，求满足$x^2 \equiv n \pmod p$的$x$。

1. 用欧拉判别准则判断$n$是否为模$p$的二次剩余，如果不是则返回$-1$表示无解，如果是$0$则返回$0$；
2. 从$1$到$p-1$中随机选一个整数$a$，使得$a^2-n$为模$p$的二次非剩余（根据定理 3，随机的次数不会太多）；
3. 令$\omega \equiv a^2-n \pmod p$，取$x \equiv (a+\sqrt{\omega})^{p-1 \over 2} \pmod p$，返回$x$（这里$\sqrt{\omega}$可以理解成虚数）。

• 引理 1

$$
\omega^{p \over 2} \equiv -\omega^{1 \over 2} \pmod p
$$

证明 由欧拉判别准则，显然成立。

• 引理 2

$$
(a+b)^p \equiv a^p+b^p \pmod p
$$

证明 $(a+b)^p \equiv \sum_{i=0}^p {p \choose i}a^ib^{p-i}$，由于$p$是奇质数，所以当且仅当$i=0$或$i=p$时${p \choose i}$没有因子$p$，于是成立。

算法证明
$$\begin{align} x^2 & \equiv (a+\sqrt{\omega})^{p-1} \\ & \equiv (a+\sqrt{\omega})^p(a+\sqrt{\omega}) \\ & \equiv (a^p+\omega^{p \over 2})(a+\sqrt{\omega}) \\ & \equiv (a-\sqrt{\omega})(a+\sqrt{\omega}) \\ & \equiv a^2-\omega \equiv n \pmod p \end{align}$$

由于$x^2 \equiv n \pmod p$有且仅有两根，且都不含$\sqrt{\omega}$项，而由算法给出的$x$是方程的一个根，所以它不含$\sqrt{\omega}$项。

代码

const int MOD = 998244353;

#define rnd (1ll * rand() * rand() % MOD)

struct Field {
    int a, b, w;
    Field(int _a = 0, int _b = 0, int _w = 0) : a(_a), b(_b), w(_w) {}
    friend Field operator*(const Field &x, const Field &y) {
        return Field((1ll * x.a * y.a + 1ll * x.b * y.b % MOD * x.w) % MOD, (1ll * x.a * y.b + 1ll * x.b * y.a) % MOD, x.w);
    }
} a[N];

int power(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            ret = 1ll * ret * a % MOD;
        }
        a = 1ll * a * a % MOD;
    }
    return ret;
}

Field power(Field a, int b) {
    Field ret = Field(1, 0, a.w);
    for (; b; b >>= 1) {
        if (b & 1) {
            ret = ret * a;
        }
        a = a * a;
    }
    return ret;
}

int quadratic(int t) {
    int l = power(t, MOD >> 1);
    return l > 1 ? l - MOD : l;
}

int solve(int t) {
    int l = quadratic(t);
    if (l < 1) {
        return l;
    }
    int a = rnd, w = (MOD + 1ll * a * a - t) % MOD;
    for (; ~quadratic(w); a = rnd, w = (MOD + 1ll * a * a - t) % MOD) ;
    return power(Field(a, 1, w), MOD + 1 >> 1).a;
}