Introduction to Quadratic Residue

定义

令$p$为奇质数。

  • 定义1 对于一个整数$n$,若存在整数$x$,使得$x^2 \equiv n \pmod p$,则称$n$是模$p$的二次剩余,否则称$n$是模$p$的二次非剩余
  • 定义2(勒让德符号) $$\left(\frac{n}{p}\right)=\begin{cases}1, & n是模p的二次剩余 \\ -1, & n是模p的二次非剩余 \\ 0, & p \mid n\end{cases}$$

定理

  • 定理1(欧拉判别准则) $$\left(\frac{n}{p}\right) \equiv n^{\frac{p-1}{2}} \pmod p$$
  • 证明
    若$p \mid n$,则$n \equiv 0 \pmod p$,结论显然成立;
    若$n$是模$p$的二次剩余,则存在$x$满足$x^2 \equiv n \pmod p$,于是$n^{\frac{p-1}{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^{\frac{p-1}{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$的二次剩余和二次非剩余的个数均为$\frac{p-1}{2}$。
  • 证明
    定理2,$1$到$p-1$中有且仅有$\frac{p-1}{2}$个不同的二次剩余,其余$\frac{p-1}{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})^{\frac{p-1}{2}} \pmod p$,返回$x$(这里$\sqrt{\omega}$可以理解成虚数)。
  • 引理1 $$\omega^{\frac{p}{2}} \equiv -\omega^{\frac{1}{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^{\frac{p}{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;
}

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *