---
title: Introduction to Quadratic Residue
tags:
  - Note
  - Quadratic Residue
id: "3658"
categories:
  - - OI
    - Number Theory
date: 2020-02-06 23:55:36
---

## 定义

令$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}$项。

## 代码

```cpp
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;
}
```