浅谈二次剩余

· · 个人记录

写在前面

由于作者是一个初一蒟蒻，有一些地方可能存在问题，请多指教。喷轻点
这次我将会讲的是二次剩余，目测难度提高+\~省选，不过先别怕。毕竟我是普及蒟蒻
你以为我会先讲二次剩余吗？
好吧真的会

前置芝士

0.加 减 乘 除

1.同余的基本芝士

右转同余定理——百度百科
几句话描述，如果 a\equiv b\pmod{p},c\equiv d\pmod{p}，那么 a\pm c\equiv b\pm d\pmod{p},ac\equiv bd\pmod{p},a^n\equiv b^n \pmod{p},b\equiv a\pmod{p}
如果ac\equiv bc\pmod{p}，那么 a\equiv b\pmod{\frac{p}{\gcd(c,p)}}
如果a\equiv b\pmod{m_i}，那么 a\equiv b\pmod{\operatorname{lcm}(m_1,m_2\cdots,m_k)}

a\equiv a+kp\pmod{p}(k\text{ 是整数})\text{ 所以}-1\equiv p-1\pmod{p}

2.欧拉定理

左转欧拉定理——百度百科
其实就是当\gcd(a,p)=1时，a^{\varphi(p)}\equiv 1\pmod{p}
而费马小定理就是它的特例，因为当 p 是质数时，\varphi(p)=p-1。

3.原根

直走原根——百度百科
简单地说就是g^i \not\equiv g^j\pmod{p},\forall 1\leqslant i,j\leqslant p-1
还有一些必记的原根

p g
3 2
5 2
998244353 3
1004535809 3
4179340454199820289 3

\text{Part\ 1} 基本定义

二次剩余

二次剩余，就是当存在某个 x，式子 x^2\equiv a\pmod{p} 成立时，称“a 是模 p 的二次剩余”，否则就称“a 是模 p 的二次非剩余”。

勒让德符号（二次特征）

勒让德符号，写作 (\frac{a}{p})，定义如下：

\left(\frac{a}{p}\right)=\left\{\begin{matrix}0 & \text{如果}a\equiv 0\pmod{p}\\ 1 & \text{如果存在整数 }x\text{，使得 }x^2\equiv a\pmod{p}\\ -1 & \text{如果不存在整数 }x\text{，使得 }x^2\equiv a\pmod{p}\end{matrix}\right.

所以a 是模 p 的二次剩余时，(\frac{a}{p})=1。
拓展到 p 是整数的定义是：(\frac{a}{p})=a^{\frac{\varphi(p)}{2}}。

欧拉准则

欧拉准则，就是 x^2\equiv a\pmod{p}\text{有解}\Leftrightarrow a^{\frac{p-1}{2}}\equiv 1\pmod{p}。

证明

a^{\frac{p-1}{2}}\equiv (x^2)^{\frac{p-1}{2}}\equiv x^{p-1}\pmod{p}\text{，由费马小定理可得 }x^{p-1}\equiv 1\pmod{p}\text{，所以 }a^{\frac{p-1}{2}}\equiv 1\pmod{p}

定义结束！！！

\text{Part\ 2} 最基本解法

爆搜就算了吧……

以下推理都是在 p 为奇质数的前提下讨论，特判一下 p=2 或 a=0 的情况就好了。

\begin{matrix}\text{设 }g\text{ 为模 }p\text{ 意义下的原根，}g^i\equiv a\pmod{p}\\ \text{有 }g^{\frac{i(p-1)}{2}}\equiv 1\pmod{p}\\ \because g\text{ 为模 }p\text{ 意义下的原根}\\ \therefore (p-1)\mid(\frac{i(p-1)}{2})\end{matrix}

此时 i 一定是偶数，用 \text{Shank's BSGS}求解。
解完 i 代入 x=g^{\frac{i}{2}} 就是答案了。

# $\text{Part\ 3}$ 再快一点？？？ 以下推理都是在 $p$ 为奇质数的前提下讨论，特判一下 $p=2$ 或 $a=0$ 的情况就好了。 $$\text{设 }p-1=2^tk,\left(\frac{w}{p}\right)=-1,a^{-1}\text{为 }a\text{ 在}\bmod{p}\text{ 意义下的乘法逆元，由欧拉准则可得 }a^{2^tk}\equiv 1\pmod{p}$$ $$\text{解 }x^2\equiv a\pmod{p}\text{，即 }a^{-1}x^2\equiv 1\pmod{p}$$ $$\text{设 }\varepsilon_q=a^{-1}x^2_q\text{，}x_{t-1}=a^{\frac{k+1}{2}}\text{，要求 }x=x_0\text{，则 }\varepsilon_q^{2^q}\equiv 1\pmod{p}\text{，则}\varepsilon_q^{2^{q-1}}\equiv \pm1\pmod{p}$$ $$\text{若 }\varepsilon_q^{2^{p-1}}\equiv1\pmod{p}\text{，则令 }x_{q-1}=x_q$$ $$\text{否则设 }\lambda x_q=x_{q-1}$$ $$\because\varepsilon_{q-1}^{2^{q-1}}=(a^{-1}x_{q-1}^2)^{2^{q-1}}\equiv 1 \pmod{p}$$ $$\therefore \varepsilon_{q-1}^{2^{q-1}}=(a^{-1}x^2_q\lambda^2)^{2^{q-1}}\equiv1\pmod{p}$$ $$\text{又}\because\varepsilon_q^{q-1}=(a^{-1}x_{q-1}^2)^{2^{q-1}}\equiv -1\pmod{p}$$ $$\therefore \lambda^{2^q}\equiv -1\pmod{p}\text{，则 }w^{2^{t-1}k}\equiv-1\pmod{p}$$ $$\text{令 }\lambda=w^{2^{t-q-1}k}\text{即可构造出一组解}$$ $$\text{直接随机选择，时间复杂度O}(\log^2 p)$$ # $\text{Part 4}$ 扩展——$x^2\equiv a\pmod{p^n}$ 的情况 有欧拉准则 $x^2\equiv a\pmod{p^n}\text{有解}\Leftrightarrow a^{\frac{\varphi(p^n)}{2}}\equiv 1\pmod{p^n}$，方法同上。 # $\text{Part 5}$ 最快？？？——$\text{Cipolla算法}

以下推理都是在 p 为奇质数的前提下讨论，特判一下 p=2 或 a=0 的情况就好了。

\text{设 }b^2-a=w\text{ 满足 }w\text{ 是 }p\text{ 的二次非剩余系} \text{设 }i=\sqrt{w}\text{，定义代数系统}\left<G,+,\cdot\right>\text{，定义于此代数系统的数可以用二元组 }(r,d)\text{ 表示} (r_1,d_1)+(r_2,d_2)=(r_1+r_2,d_1+d_2),(r_1,d_1)\cdot(r_2,d_2)=(r_1r_2+wd_1d_2,r_1d_2+r_2d_1) \text{可以证明 }\left<G,+,\cdot\right>\text{ 为环} \text{所以 }pi\equiv0\pmod{p} x\equiv(b+i)^{\frac{p+1}{2}}\text{ 就是答案了} \text{证明如下：}

\text{所以我们可以随机出一个 }b\text{，期望随机次数为 }2\text{ 次} \text{使用快速幂求 }x\equiv(b+i)^{\frac{p+1}{2}}\text{，另一个解为 }p-x\text{，时间复杂度O}(\log p) \text{这个就是Cipolla算法}

标程：

#include<cstdio>
#include<cstdlib>
using namespace std;
long long w;
struct num{long long r,i;};
num mul(num a,num b,long long p)
{
    return (num){((a.r*b.r%p+a.i*b.i%p*w%p)%p+p)%p,((a.r*b.i%p+a.i*b.r%p)%p+p)%p};
}
long long pow(long long a,long long b,long long p)
{
    long long ans(1);
    while (b)
    {
        if(b%2) ans=ans*a%p;
        a=a*a%p;
        b/=2;
    }
    return ans%p;
}
long long pow_complex(num a,long long b,long long p)
{
    num ans={1,0};
    while (b)
    {
        if (b%2) ans=mul(ans,a,p);
        a=mul(a,a,p);
        b/=2;
    }
    return ans.r;//此时“虚部”为0 
}
long long solve(long long a,long long p)
{
    a%=p;
    if (p==2) return a;
    if (pow(a,(p-1)/2,p)==p-1) return -1;//无解（欧拉准则）
    long long b;
    do
    {
        b=rand()%p;
        w=((b*b-a)%p+p)%p; 
    } while (pow(w,(p-1)/2,p)!=p-1);//循环结束后w是二次非剩余（欧拉准则） 
    return pow_complex((num){b,1},(p+1)/2,p);
}
int main()
{
    long long a,p;
    scanf("%lld %lld",&a,&p);
    if (!a) puts("0"); else
    {
        long long ans1(solve(a,p)),ans2(p-ans1);
        if (ans1==-1) puts("Unsolvable!");
        else
        {
            if (ans1>ans2)
            {
                long long t=ans1;
                ans1=ans2;
                ans2=t;
            } 
            if (ans1==ans2) printf("%lld\n",ans1); else printf("%lld %lld\n",ans1,ans2);
        }
    }
}

\text{EXPart 5} 一般二次方程

\text{对于形如 }ax^2+bx+c\equiv0\pmod{p}\text{ 的方程} \text{先配方化为 }(ax+b)^2\equiv b^2-4ac\pmod{p} \text{可通过换元得到 }X^2\equiv b^2-4ac\pmod{p} \text{用Cipolla算法解出 }X\text{ 的取值，然后用 }2ax+b\text{ 回带} \text{用扩展欧几里得解线性同余方程就可以得到方程本来的解}

\text{Part 6} 三次剩余——\text{Peralta Method Extension}

\text{类比 Part 5 二次剩余，我们可以使用类似的方法} \text{对于三次剩余，同样有欧拉准则}x^3\equiv a\pmod{p}\text{有解}\Leftrightarrow a^{\frac{\varphi(p)}{3}}\equiv 1\pmod{p} \text{如果 }p\equiv -1\pmod{3}\text{，则 }x\equiv a^{\frac{2p-1}{3}}\pmod{p}\text{ 是唯一解。} \text{先随机出一个 }b\text{ 使得 }b^3-a \text{ 是三次非剩余，即 }(b^3-a)^\frac{\varphi(p)}{3}\not\equiv 1\pmod{p}\text{ 期望次数为 }9 \text{设 }w=b^3-a,i=\sqrt[3]{w}\text{，}\bmod p\text{意义下的原根为 }g \text{则三次单位根 }\epsilon=g^{\frac{p-1}{3}} \text{则 }x_1\equiv(b+i)^{\frac{p^2+p+1}{3}}\pmod{p},x_2=x_1\epsilon,x_3=x_2\epsilon \text{证明类似} \text{记住特判 }a=0\text{ 或 }p\leq 3\text{ 的情况}

\text{Part 7} k次剩余？

\text{类比 Part 6，我们可以将它拓展至 }k\text{ 次剩余} \text{先随机出一个 }b\text{ 使得 }b^k-a \text{ 是三次非剩余，即 }(b^k-a)^\frac{\varphi(p)}{k}\not\equiv 1\pmod{p} \text{设 }i=\sqrt[k]{b^k-a} \text{则 }x\equiv(b+i)^{\frac{\sum_{i=0}^{k-1}p^i}{k}}\pmod{p} \text{记住特判 }a=0\text{ 或 }p\leq k\text{ 的情况}

好像是对的，但我不会证明……反正没错过

\text{Part 8} k次剩余\times 2？

这个是对的……

x^k\equiv a\pmod{p} \text{设 }p\text{ 的原根是 }g,x\equiv g^y\pmod{p} x^k\equiv(g^y)^k\equiv g^{yk}\equiv a\equiv g^{\operatorname{in}\!\operatorname d_g a}\pmod{p} ky\equiv\operatorname{in}\!\operatorname d_g a\pmod{\varphi(p)} \operatorname{in}\!\operatorname d_g a\text{ 就是以 }g\text{ 为底，}a\text{ 的离散对数，使用(ex)Shank's BSGS解出} \text{化为 }ky+f\varphi(p)=\operatorname{in}\!\operatorname d_g a\text{，使用exGCD解出 }y x\equiv g^y\pmod{p} \Huge\color{purple}\text{完结撒花！！！}

参考资料