浅谈二次剩余

Ruiqun2009 · 2022-07-27 14:42:10 · 算法·理论

二次剩余，是方程 x^2\equiv a\pmod p 的解。

为了方便起见，这里的模数均为奇素数。~~（毕竟其他情况考的很少）~~

我们先引出一个符号：

勒让德符号。

(\dfrac ap)=\begin{cases}1 & a\text{ 是 }p\text{ 的二次剩余}\\0 & a\bmod p=0\\-1 & a\text{ 是 }p\text{ 的二次非剩余}\end{cases}

然后我们再看这个东西：x^\frac{p-1}{2}\pmod p。

当 p\perp a，我们设 p=2q+1，即 q=\frac{p-1}{2}，于是根据费马小定理，有 a^{p+1}\equiv1\pmod p，也就是 a^{2q}\equiv 1\pmod p，或 (a^q+1)(a^q-1)\equiv 0\pmod p。再根据二次探测定理（后面会 Miller-Rabin 素数判定方法，这是极其关键的一步），a^q\equiv\pm1\pmod p，也就是 a^\frac{p-1}{2}\equiv\pm 1\pmod p。

当 a\bmod p = 0 时，则 a^\frac{p-1}{2}\equiv 0\pmod p。

发现这个东西和勒让德符号的关系了吗？

事实上，有这个东西：

欧拉判定准则。

它指出：(\dfrac ap)=a^\frac{p-1}{2}\bmod p=1 是 a 是 p 的二次剩余的充要条件。

我们试着证明它。

引理：令 p 为素数和模 p 意义下原根 g 并令 a=g^k。那么 x^2\equiv a\pmod p 有解当且仅当 k 为偶数。

引理的证明：

（充分性）假设 x^2\equiv a\pmod p 有解为 g^l 对于某个 l 成立。那么 (g^l)^2\equiv a\pmod p\implies g^{2l}\equiv a\pmod p。因此 k\equiv2l\pmod{p-1}（费马小定理），而 p-1 为偶数，所以 k 为偶数。
（必要性）假设 k 为偶数，那么 x^2\equiv g^k\pmod p\iff x^2\equiv (g^{k/2})^2\pmod p。而因为 k 为偶数，所以 k/2 为整数，因此 x^2\equiv g^k\pmod p 有解为 g^{k/2}。

因为 g 为模 p 的原根，那么 g 的阶为 \varphi(p)=p-1，所以 g^{p-1}\equiv 1\pmod p 。

且根据阶的定义，对于所有 k\in\mathbb Z 满足 1\leq k\lt p-1 都有 g^k\not\equiv1\pmod p，所以

\begin{aligned} &{ }g^{p-1}\equiv1\pmod p\\ \iff &g^{p-1}-1\equiv0\pmod p\\ \iff &(g^\frac{p-1}2-1)(g^\frac{p-1}2+1)\equiv0\pmod p\\ \iff &g^\frac{p-1}2\equiv-1\pmod p \end{aligned}

考虑同余方程 x^2\equiv a\pmod p。因为 a\in\mathbb F_p\setminus\lbrace 0\rbrace 且 a\equiv g^k\pmod p 对于某个 k 满足 1\leq k\leq p-1 成立。若同余方程存在解，则 k 为偶数，通过上述引理和费马小定理有

\begin{aligned} a^\frac{p-1}{2}&\equiv(g^k)^\frac{p-1}{2}\pmod p\\ &\equiv(g^{p-1})^\frac k{2}\pmod p\\ &\equiv1\pmod p \end{aligned}

所以当 a^\frac{p-1}{2}\equiv1\pmod p 时解存在。

又因上述引理，x^2\equiv a\pmod p 无解时 k 为奇数。假设 k 为奇数，那么

\begin{aligned} a^\frac{p-1}{2}&\equiv(g^k)^\frac{p-1}{2}\pmod p\\ &\equiv(g^\frac{p-1}{2})^k\pmod p\\ &\equiv (-1)^k\pmod p\\ &\equiv -1\pmod p \end{aligned}

即得欧拉判别准则，也可以推断出勒让德符号为完全积性函数。

然后就是这篇文章最重要的环节：

\texttt{Cipolla} 算法！

~~这东西就是扩域的升级版。~~

现实中有个东西叫虚数，我们可以把虚数单位变成我们想要的。

现在我们要找虚数单位，方便我们计算。

这个算法的第一步是：

找到 m，使得 m^2-a 为 \bmod p 意义下的非二次剩余。
令 i^2\equiv m^2-a\pmod p。

这里你就有疑问了：既然 m^2-a 为 \bmod p 意义下的非二次剩余，为什么还存在 i？

因为 i 是虚数单位呀。不然还叫它什么虚数呢。

然后我们计算 (m+i)^\frac{p+1}2 （注意指数），就得到一个解了。

先证明一个引理：a^p+b^p\equiv (a+b)^p\pmod p。

我们将右边用二项式定理展开。得到：

\begin{aligned} (a+b)^p&=\sum\limits_{i=0}^p\binom ipa^ib^{p-i}\\ &=\sum\limits_{i=0}^p\dfrac{p!}{i!(p-i)!}a^ib^{n-i} \end{aligned}

然后我们发现这个式子在 i=0 或 i=p 的情况下分母会消掉分子上的 p，使得 a^p 和 b^p 保留下来。而其他项由于没有分母上的 p，又因为 p 是素数，所以 p 没有被消掉，于是这些项在 \bmod p 下就变成了 0。

所以，等式成立。

于是

\begin{aligned} (a+i)^{p+1}&=(a+i)^p\times(a+i)\\ &=(a^p+i^p)\times(a+i) \end{aligned}

由于费马小定理，a^p\equiv a\pmod p，而 i^p=i^{p-1}\times i\equiv(a^2-n)^\frac{p-1}2\times i\equiv-i，所以

\begin{aligned} (a+i)^{p+1}&=(a+i)^p\times(a+i)\\ &\equiv(a^p+i^p)\times(a+i)\pmod p\\ &\equiv(a-i)(a+i)\pmod p\\ &\equiv a^2-i^2\pmod p\\ &\equiv a^2-(a^2-n)\pmod p\\ &\equiv n\pmod p\\ \end{aligned}

然后再根据定义，得到 (a+i)^{p+1} 是 a 在 \bmod p 意义下的二次剩余（注意，第一个 a 是 \texttt{Cipolla} 算法的 a，第二个 a 是标题上的 a）。

于是我们证明了 \texttt{Cipolla} 算法结果的正确性。

例题实现：

#include <cstdio>
#define int long long
inline int qpow(int base, int power, int p) {
    int ans = 1;
    for (; power; base = base * base % p, power >>= 1) 
        if (power & 1) ans = ans * base % p;
    return ans;
}
inline int mod(int a, int p) {
    return (a % p + p) % p;
}
namespace Cipolla {
    inline int legendre(int a, int p) {
        return qpow(mod(a, p), (p - 1) / 2, p); // must mod first!
    }
    inline int find_not_sqrt(int n, int p) {
        for (int a = 0; a < p; a++)
            if (legendre(a * a - n, p) == p - 1) return a;
        return -1;
    }
    int a, p, n;
    struct cp {
        int m_real, m_imag;
    };
    cp mul(cp _a, cp _b) {
        int c = a * a - n;
        return 
        cp{(_a.m_real * _b.m_real % p + _a.m_imag * _b.m_imag % p * c) % p, 
           (_b.m_imag * _a.m_real + _a.m_imag * _b.m_real) % p};
    }
    cp qpow(cp base, int power) {
        cp ans{1, 0};
        for (; power; base = mul(base, base), power >>= 1) 
            if (power & 1) ans = mul(ans, base);
        return ans;
    }
    int query(int n, int p) {
        if (n % p == 0) return 0;
        if (legendre(n, p) != 1) return -1;
        Cipolla::n = n;
        Cipolla::p = p;
        a = find_not_sqrt(n, p);
        return mod(qpow(cp{a, 1}, (p + 1) >> 1).m_real, p);
    }
}
void solve() {
    int x, p;
    scanf("%lld%lld", &x, &p);
    int val = Cipolla::query(x, p);
    if (val == -1) puts("Hola!");
    else if (val == 0) puts("0");
    else {
        if (val > p - val) val = p - val;
        printf("%lld %lld\n", val, p - val);
    }
}
signed main() {
    int T;
    scanf("%lld", &T);
    while (T--) solve();
}

练习：

P1962 斐波那契数列

参考文献：

二次剩余 - OI-Wiki
算法学习笔记(41):二次剩余 - 知乎

后记：

任意模数二次剩余咋做？中国剩余定理！（后面会讲）
关于二次剩余的其他内容，参见本文.