二次剩余

· · 算法·理论

0 前言

二次剩余，是一个并不高频的考点，但是它会在你意想不到的地方出现，就比如说一个月前的省选模拟的一道题目。

二次剩余通常是指求以下同余方程的两个解

x^2 \equiv n \pmod p

容易发现，这与开根的计算类似，故又被称做模意义开根，这里给出了二次剩余的严格定义：

设 m 是正整数，a 是与 m 互素的整数，若 (a,m) = 1，且同余方程 x^2 \equiv a \pmod m 有解，则称 a 为 m 的二次剩余。若同余方程 x^2 \equiv a \pmod m 无解，则称 a 为 m 的二次非剩余。

1 勒让德符号

为了方便讨论，我们引入了勒让德符号，如果下面没有说明，我们保证 a 不是 p 的倍数，且 p 为奇素数。

关于勒让德符号的定义如下（\text {Yes} 表明 a 是 p 的二次剩余，\text{No} 则表示是二次非剩余）：

(\frac ap) = \begin{cases} 1, \text {Yes}, \\ -1, \text {No}. \end{cases}

（部分的参考资料上，还存在 (\frac ap) = 0 的情况，此时满足 p|a，不过这里不予讨论。）

2 欧拉准则及其证明

我们首先以一个命题开始。

尝试证明以下命题，其中 (\frac ap) 为勒让德符号：

(\frac ap) \equiv a^{(p - 1) / 2} \pmod p

对于 (\frac ap) = 1 的情况，那么 x^2 \equiv a \pmod p 则有解，设 x_0 = x，那么有

a^{(p - 1) / 2} \equiv (x_0^2)^{p - 1 / 2} \equiv x_0^{p - 1} \pmod p

根据费马小定理，有

x_0^{p - 1} \equiv 1 \pmod p

即为 (\frac ap)。

对于 (\frac ap) = -1 的情况，那么 x^2 \equiv a \pmod p 无解，根据以下引理：

对于 (\frac ap) = 1 的情况， ax \equiv b \pmod p（b 为任意整数），一定有 \text{mod } p 的唯一解（换句话说，在 [0,p) 的整数内有解）。

因为 i = 1,2,...,p - 1 均互质于 p，所以一定有 ij \equiv a \pmod p。

由于 x^2 \equiv a \pmod p 无解，所以 i \neq j。

考虑将 1,2,...,p - 1 分成两组，满足 i 在一组，j 在另一组。

将这两个组相乘起来得到：

(p - 1) ! \equiv a^{(p - 1) / 2} \pmod p

根据威尔逊定理：

(p - 1) ! \equiv -1 \pmod p \leftrightarrow p \text { is a prime.}

得到

a^{(p - 1)/2} \equiv -1 \pmod p

即为 (\frac ap)，命题得证。Q.E.D.

这个定理被称作欧拉准则，或者说欧拉判别式。

2 求解 —— Cipolla 算法

对于同余方程

x^2 \equiv n \pmod p

我们寻找整数 a 满足 (\frac{a^2 - n}{p}) = -1，换句话说，使得 x^2 = a^2 - n \pmod p 无解。

但同时我们定义 i^2 \equiv a^2 - n \pmod p，注意这里的 i 不一定属于整数域，我们临时定义一个新的值域，满足 i^2 \equiv a^2 - n \pmod p。

容易发现，对于 x^2 \equiv n \pmod p 的同余方程，(a + i)^{(p + 1) / 2} 是其一个解（而且不存在 i），这个方法被称作寻找二次剩余的 Cipolla 算法，如果计算幂次的时间是 O(\log n) 的，那么 Cipolla 算法 的时间复杂度亦为 O(\log n)。

2.1 关于 Cipolla 算法的证明

2.1.1 关于正确性

下面我们来证明 Cipolla 算法的正确性，以及时间复杂度。

我们考虑分解 (a + i)^{p + 1}：

(a + i)^{p + 1} = (a+i)^p \cdot (a + i)

我们发现对于 (a+i)^p，若使用二项式定理展开，除了 a^p 和 i^p 项，其余的全部都为 p 的倍数（注意，p 为奇数），所以可以被消掉。

所以原式可以化成

(a+i)^p \cdot (a + i) \equiv (a^p + i^p) \cdot (a + i) \pmod p

根据费马小定理，我们有

a^p \equiv a \pmod p

同时对于 i^p 一项，尝试对其分解得到

i^p = i^{p - 1} \cdot i \equiv i \cdot (a^2 - n)^{(p - 1) / 2} \pmod p

根据欧拉准则，我们可以将其化为 -i。

所以将原式转化为

(a^p + i^p) \cdot (a + i) \equiv (a + i)(a - i) \equiv a^2 - i^2 \equiv a^2 - (a^2 - n) = n\pmod p

所以我们证明了 (a+i)^{p+1} 同余 n，所以 (a+i)^{(p + 1)/2} 的二次方自然就同余 n 了，至于另一个答案，明显是 -(a+i)^{(p + 1)/2}，所以 Cipolla 算法是正确的。Q.E.D.

2.1.2 关于时间复杂度

前面说过，Cipolla 算法的时间复杂度是 O(\log n) 的，此处便加以不是很严格的证明。

考虑关于 (a, x) 的同余方程

a^2 - n \equiv x^2 \pmod p

这等价于

(a + x)(a - x) \equiv n \pmod p

容易发现，对于 x = 1,2,..,p - 1，总是存在一组合法的 a,x 使得满足上述同余方程。

因此我们一共有 p - 1 个解，对于 x,-x 他们同属一个 a，所以我们一共能够取到 \frac {p - 1}{2} 个 a，换而言之，在 p - 1 个 a 中，总是有 \frac{p - 1}{2} 是满足有解的。

所以满足没有解的 a，即我们想要的 a，一共有 p - 1 - \frac{p - 1}2，即 \frac{p - 1}2 个，计算其随机选取的期望值为：

\frac{p - 1}{\frac{p - 1}2} = \frac{2(p - 1)}{p - 1} = 2

所以在期望下，寻找 a 的次数为 c = 2 次，而即使是在拓展的值域上做快速幂，仍然是 O(\log n) 的，所以最后的时间复杂度即为 O(\log n)，Q.E.D.

3 Cipolla 算法的代码

expand{a,b} 表示拓展之后的值域，代表 a + bi，对于它的加法、乘法，与复数是类似的，不过需要注意 i^2 \equiv n - a^2 \pmod p，这一点需要在 times(expand &a, expand b) 即拓展乘法中考虑到。

模板题：P5491，我真的在努力让代码变短了！

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll T, n, p, a;

struct expand {
    ll a, b;
};

ll qpow(ll bas, ll exp) {
    ll res = 1;
    while(exp) {
        if(exp & 1)
            res *= bas,
            res %= p;
        bas *= bas;
        bas %= p;
        exp >>= 1;
    }
    return (res % p + p) % p;
}

void times(expand &x, expand y) {
    expand c;
    c.a = c.b = 0;
    c.a = x.a * y.a % p + (a * a - n) * x.b % p * y.b % p;
    c.a %= p;
    c.b = x.a * y.b % p + x.b * y.a % p;
    c.b %= p;
    x = c;
    return;
}

expand expand_qpow(expand bas, ll exp) {
    expand res;
    res.a = 1, res.b = 0;
    while(exp) {
        if(exp & 1)
            times(res, bas);
        times(bas, bas);
        exp >>= 1;
    }
    res.a = (res.a % p + p) % p;
    return res;
}

int main() {
    scanf("%lld", &T);
    for(; T; --T) {
        scanf("%lld%lld", &n, &p);
        if(qpow(n, (p - 1) / 2) != 1) {
            printf("Hola!\n");
            continue;
        }
        a = 0;
        for(ll i = 0; i <= p; i++) {
            if(qpow(i * i - n, (p - 1) >> 1) == p - 1) {
                a = i;
                break;
            }
        }
        expand init;
        init.a = a, init.b = 1;
        expand x0 = expand_qpow(init, (p + 1) >> 1);
        if(!x0.a)
            printf("0\n");
        else {
            if(x0.a <= (-x0.a % p + p) % p)
                printf("%lld %lld\n", x0.a, (-x0.a % p + p) % p);
            else
                printf("%lld %lld\n", (-x0.a % p + p) % p, x0.a);
        }
    }
    return 0;
}

4 参考引用文献

  1. 《Elementary Number Theory and Its Applications》，第六版，Kenneth H.Rosen；
  2. Pecco大神的算法学习笔记(41): 二次剩余；
  3. 匿名用户回答的关于Cipolla性质的证明请问如何证明求二次剩余的经典cipolla算法中的一个简单性质？。