$$\newcommand\legendre[2]{\left(\frac{#1}{#2}\right)}$$

二次剩余

当存在数$X$使得$X^2\equiv n\mod p$成立时，称n是模p意义下的二次剩余(QR)。

特别的，对于$p=2$，每一个整数都是它的二次剩余；

本文中符号$QR$代表二次剩余，$NR$代表非二次剩余

下面只考虑$p$为奇素数的情况。

若p为奇素数，则恰有$\frac{(p-1)}{2}$个模p的二次剩余，且恰有$\frac{(p-1)}{2}$个模p的非二次剩余

下面的同余式默认省略$\mod p$符号

设$1\le x \lt p$，首先证明$x^2\equiv (p-x)^2$

显然$(p-x)^2\equiv p^2-2px+x^2\equiv x^2$

这么一来，可知$1^2\equiv (p-1)^2, 2^2 \equiv (p-2)^2,\cdots$

接下来只需要证明$1^2,2^2,\cdots, (\frac{p-1}{2})^2$两两不相等即可

假设$1\le b_1, b_2\le \frac{p-1}{2}$，且$b_1\ne b_2$

若$b_1^2\equiv b_2^2$，则$p$整除$b_1^2-b_2^2\equiv (b_1-b_2)(b_1+b_2)$

显然$b_1+b_2<p$，因此$b_1+b_2$与$p$互质；

又因为$\mid b_1-b_2\mid <p$，唯一的可能便是$b_1=b_2$，与假设相违背

命题得证

$QR \times QR = QR, QR \times NR = NR, NR \times NR = QR$

请自行证明

勒让德符号(legendre symbol)

$$(\frac{a}{p}) = \begin{cases}1 , &\text{a在模$p$意义下是二次剩余}\\-1, &\text{a在模$p$意义下是非二次剩余}\\0, &\text{a mod p = 0}\end{cases}$$

设$p$为奇素数，则

$$\legendre{a}{p}\legendre{b}{p}=\legendre{ab}{p}$$

且有欧拉准则：

$$a^{\frac{p-1}{2}}\equiv \legendre{a}{p}\tag 1$$

式(1)证明略

Cipolla

算法步骤：

对于$x^2\equiv n$，随机找一个$a$使得$a^2-n$为非二次剩余，定义$i^2\equiv a^2-n,i\equiv \sqrt{a^2-n}$（类比虚数）

那么$(a+i)^{p+1}\equiv n$

证明见参考资料

模板

#define ll long long
namespace residue{
    // p 必须是奇素数
    ll square_i = 0, mod = 1;

    struct complex{
        ll real, imag;
        complex operator *(const complex & p){
            return {(real * p.real % mod + square_i * p.imag % mod * imag % mod) % mod,
                    (real * p.imag + imag * p.real) % mod};
        }
    };

    complex qpow(complex a, ll t){
        complex res = {1, 0};
        while(t){
            if(t & 1) res = res * a;
            t >>= 1, a = a * a;
        }
        return res;
    }

    bool is_residue(ll n, ll p){ // 判断n是否是剩余
        ll res = 1, t = (p - 1) / 2;
        while(t){
            if(t & 1) res = res * n % p;
            t >>= 1, n = n * n % p;
        }
        return res == 1;
    }

    pair<ll, ll> get_res(ll n, ll p){
        n %= p, mod = p;
        if(n == 0) return {0, 0}; 
        if(!is_residue(n, p)) return {-1, -1}; // 非二次剩余
        ll a;
        do{
            a = rand() % (p - 1) + 1;
            square_i = (a * a % p - n + p) % p;
        }while(is_residue(square_i, p));
        ll ans1 = qpow({a, 1}, (p + 1) / 2).real, ans2 = p - ans1;
        if(ans1 > ans2) swap(ans1, ans2);
        return {ans1, ans2};
    }
}

参考资料

• 《数论概论》第4版
• 《哈代数论》第6版
• https://www.cnblogs.com/zwfymqz/p/10605181.html
• https://www.luogu.com.cn/blog/_post/181742