二次剩余－学习

二次剩余

形如: $x^2\equiv d\left(modp\right)$x2≡d(modp) ,d为模p意义下的二次剩余
本文讨论的是p为质数的二次剩余

在数学中有个勒让德符号，判断是否是二次剩余
$\left(\frac{n}{p}\right)=\{\begin{array}{c}{\displaystyle 1\left(n是模p意义下的二次剩余\right)}\\ {\displaystyle -1\left(n是模p意义下的非二次剩余\right)}\\ {\displaystyle 0(n\equiv 0(modp\left)\right)}\end{array}$(pn​)=⎩⎪⎨⎪⎧​1 (n是模p意义下的二次剩余)−1 (n是模p意义下的非二次剩余)0 (n≡0(modp))​
由费马小定理知: $a^{p-1}\equiv 1\left(modp\right)$ap−1≡1(modp)
由欧拉准则知:
$a^{\frac{p-1}{2}}\equiv \left\{\begin{array}{c}{\displaystyle 1\left(a是模p意义下的二次剩余\right)}\\ {\displaystyle -1\left(a是模p意义下的非二次剩余\right)}\\ {\displaystyle 0(a\equiv 0(modp\left)\right)}\end{array}\right(modp)$a2p−1​≡⎩⎪⎨⎪⎧​1 (a是模p意义下的二次剩余)−1 (a是模p意义下的非二次剩余)0 (a≡0(modp))​(modp)
所以 $\left(\frac{d}{p}\right)=a^{\frac{p-1}{2}}\left(modp\right)$(pd​)=a2p−1​(modp)
我们设 : $w^2=a^2-n$w2=a2−n,且另w2为模p意义下的非二次剩余
这样我们可以知道 ${w^2}^{\frac{p-1}{2}}\equiv w^{p-1}\equiv -1\left(modp\right)$w22p−1​≡wp−1≡−1(modp)
我们可以设 $W=w^2$W=w2 , $x=(a+w{)}^{\frac{p+1}{2}}$x=(a+w)2p+1​,且x为方程的一个解，这样另一个解为p-x
简单证明：
$\begin{array}{c}{\displaystyle x^2\equiv (a+w{)}^p\ast (a+w)}\\ {\displaystyle x^2\equiv (a^p+w^p)\ast (a+w)}\\ {\displaystyle x^2\equiv (a^{p-1}\ast a+w^{p-1}\ast w)+(a+w)}\\ {\displaystyle x^2\equiv (a-w)\ast (a+w)}\\ {\displaystyle x^2\equiv a^2-w^2}\\ {\displaystyle x^2\equiv a^2-(a^2-n)}\\ {\displaystyle x^2\equiv n}\end{array}$x2≡(a+w)p∗(a+w)x2≡(ap+wp)∗(a+w)x2≡(ap−1∗a+wp−1∗w)+(a+w)x2≡(a−w)∗(a+w)x2≡a2−w2x2≡a2−(a2−n)x2≡n​
这样的话我们可以随机一个a,在[0, p - 1]范围内，然后求出相应的w，判断是否是非二次剩余
对w需要进行复数处理,即将(a + w)处理成(a + b * w)

例题

洛谷p5491

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct plural//复数类 
{
    ll a, b;
    plural(ll _a = 0, ll _b = 0) : a(_a), b(_b) {}
};
ll w;
plural pl_mul(plural x, plural y, ll mod)//复数乘法
{
    plural ans = plural();
    ans.a = ((x.a * y.a % mod + x.b * y.b % mod * w % mod) % mod + mod) % mod;
    ans.b = ((x.a * y.b % mod + x.b * y.a % mod) % mod + mod) % mod;
    return ans;
}
ll RQ_pow(ll a, ll b, ll mod)
{
    ll c = 1;
    while(b)
    {
        if(b & 1)
            c = c * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return c;
}
ll PQ_pow(plural x, ll y, ll mod)
{
    plural ans = plural(1, 0);
    while(y)
    {
        if(y & 1)
            ans = pl_mul(ans, x, mod);
        x = pl_mul(x, x, mod);
        y >>= 1;
    }
    return ans.a % mod;
}
ll solve(ll n, ll p)
{
    n %= p;
    if(p == 2)
        return n;
    if(RQ_pow(n, (p - 1) / 2, p) == p - 1)
        return -1;
    ll a;
    while(true)
    {
        a = rand() % p;
        w = ((a * a % p - n) % p + p) % p;
        if(RQ_pow(w, (p - 1) / 2, p) == p - 1)
            break;
    }
    plural zz = plural(a, 1);
    return PQ_pow(zz, (p + 1) / 2, p);
}
int main()
{
    //freopen("test.in", "r", stdin);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t --)
    {
        ll n, p;
        cin >> n >> p;
        if(!n)
        {
            cout << 0 << endl;
            continue;
        }
        ll d1 = solve(n, p), d2;
        if(d1 == -1)
        {
            cout << "Hola!" << endl;
            continue;
        }
        d2 = p - d1;
        if(d1 > d2)
            swap(d1, d2);
        if(d1 == d2)
        {
            cout << d1 << endl;
            continue;
        }
        cout << d1 << " " << d2 << endl;
    }
}