题解 P5491 【【模板】二次剩余】

· · 题解

【一些定义】

1、二次剩余与二次非剩余：对于一个整数 q，若在模 m 意义下，有一个完全平方数与 q 同余，则称 q 为模 m 意义下的二次剩余，反之则为二次非剩余

2、勒让德符号：定义如下

\left( \frac{n}{p} \right) = \begin{cases} -1 \quad n \text{ is a quadratic non-residue modulo } p \\ 1 \quad n \text{ is a quadratic residue modulo } p \\ 0 \quad n \equiv 0 \pmod p\end{cases}

图：勒让德符号表

3、欧拉判别准则（Euler's criterion）：\left( \frac{n}{p} \right) = n^{\frac{p-1}{2}}

Preposition. 费马小定理，拉格朗日定理

证明：由于模数为奇素数，故拉格朗日定理适用：对于任意整数 n，方程 x^2 \equiv n \pmod p 的不同余的解只有 2 个。于是我们可以得出：除了 0 之外，一定有至少 \frac{p-1}{2} 个模 p 意义下的二次剩余。

由于 n \perp p，由费马小定理得到 a^{p-1} \equiv 1 \pmod p，进一步得到 (a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1) \equiv 0 \pmod p，\mod p 意义下的数构成一个数域，这两个因式中，必有一个因式的值为 0。

当 a 是模 p 意义下的二次剩余时，a \equiv x^2 \pmod p，故 a^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \pmod p。所以对于任意模 p 意义下的二次剩余，第一个因式的值都为零。

由拉格朗日定理，最多只有 \frac{p-1}{2} 个数满足 a^{\frac{p-1}{2}}-1 \equiv 0 \pmod p，然而模 p 意义下的二次剩余至少有 \frac{p-1}{2} 个。故这 \frac{p-1}{2} 个二次剩余刚好构成了能使 a^{\frac{p-1}{2}}-1 \equiv 0 \pmod p 的剩余系。而对于剩下 \frac{p-1}{2} 个二次非剩余，它们必须让第二个因式等于 0。

总结一下，即有：

n^{\frac{p-1}{2}} = \begin{cases} -1 \quad n \text{ is a quadratic non-residue modulo } p \\ 1 \quad n \text{ is a quadratic residue modulo } p \end{cases}

【算法流程】

对于模方程 x^2 \equiv n \pmod p，先随机选出一个整数 a，使得 a^2 - n 为模 p 意义下的二次非剩余。由于二次非剩余有 \frac{p-1}{2} 个，故期望试 2 次得到 a。

得到合法的 a 后，令 \zeta = \sqrt{a^2-n} \pmod p，则 (a + \zeta)^{\frac{p+1}{2}} 一定是原方程的解。

证明：

(a+\zeta)^{\frac{p+1}{2}} \pmod p =\sqrt{(a+\zeta)^{p+1}} \pmod p =\sqrt{(a+\zeta)^{p}(a+\zeta)} \pmod p =\sqrt{(a^{p}+\zeta^{p})(a+\zeta)} \pmod p

若上面一步不懂可用二项式定理理解。

由于 \zeta^2 为模 p 意义下的二次非剩余，故有 (\zeta^2)^{\frac{p-1}{2}} \equiv -1 \pmod p，即 \zeta^{p-1} \equiv -1，即 \zeta^p \equiv -\zeta \pmod p。\color{White}\text{WJPAKIOI}

由于费马小定理，a^{p-1} \equiv 1 \pmod p，故 a^p \equiv a \pmod p。

所以：

\sqrt{(a^{p}+\zeta^{p})(a+\zeta)} \pmod p =\sqrt{(a-\zeta)(a+\zeta)} \pmod p =\sqrt{a^2-\zeta^2} \pmod p =\sqrt{a^2-a^2+n} \pmod p =\sqrt{n} \pmod p

证毕。

啊但是 \zeta^2 不是模 p 意义下的非二次剩余吗... 这怎么开平方根啊...

类似复数的想法，我们可以扩展数域，搞出一个模 p 意义下的虚数，就可以解决开不了平方根的问题了。

如果这个虚数虚部不是零？事实上不会。

证明：设最终获得的二次剩余为 a+bI \pmod p。

故 (a+bI)^2 \equiv 0 \pmod p，有 a^2 - b^2 + 2abI \equiv 0 \pmod p。

若 b \neq 0，则 a = 0，(bI)^2 \equiv n \pmod p，I \equiv \sqrt\frac{n}{b^2} \pmod p，I 就变成了一个二次剩余，明显矛盾，故 b = 0。

那只找到了一个解啊，还有一个解呢？实际上另一个解就是 p-x，使用完全平方公式轻松证明，本文不再赘述。

【代码】

#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
#define LL long long
#define ULL unsigned long long
#define LD long double
using namespace std;
template <typename T>
inline void read(T &x) {
    x = 0; T f = (T) 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    x *= f;
}
template <typename T>
inline void write(T x) {
    if(x < 0) {putchar('-'); x = -x;}
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = '\n') {
    write(x); putchar(sp);
}
int T, n, p, omega, WJP_AK_IOI = 1;
struct cpx {
    int real, imag;
    void init(int r, int i) {real = r; imag = i;}
};
cpx multiply(cpx a, cpx b) { 
    cpx Z;
    Z.init((1ll * a.real * b.real % p + 1ll * a.imag * b.imag % p * omega % p) % p, (1ll * a.real * b.imag % p + 1ll * b.real * a.imag % p) % p); 
    return Z;
}
int pow_mod(int a, int b, int p) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return ans;
}
cpx pow_cpx(cpx a, int b) {
    cpx Ans; Ans.init(1, 0);
    while(b) {
        if(b & 1) Ans = multiply(Ans, a);
        a = multiply(a, a);
        b >>= 1;
    }
    return Ans;
}
int legendre(int n, int p) {
    if(!(n % p)) return 0;
    return pow_mod(n, (p - 1) / 2, p);
}
int quad_residue(int n, int p) {
    n %= p;
    if(legendre(n, p) == p - 1) return -1;
    int A;
    while(1) {
        A = rand() % p;
        omega = (1ll * A * A % p - n + p) % p;
        if(legendre(omega, p) == p - 1) break;
    }
    cpx I; I.init(A, 1);
    cpx Q = pow_cpx(I, (p + 1) / 2);
    return Q.real;
}
int main() {
    srand(time(0));
    read(T);
    while(T--) {
        read(n); read(p);
        if(!n) {writesp(n, '\n'); continue;}
        int k = quad_residue(n, p);
        if(k == -1) {
            puts("Hola!");
        } else {
            int k2 = p - k; 
            if(k > k2) swap(k, k2);
            if(k == k2) cout << k << endl;
            else cout << k << " " << k2 << endl;
         }
    }
    return 0;
}

【参考资料】

1、Magolor - 数论 PPT
2、【注：使用镜像】Wikipedia: Quadratic non-residue
3、【注：使用镜像】Wikipedia: Legendre Symbol