二次剩余推导

· · 算法·理论

*本证明使用了类似虚数的思想
\exists x,s.t.x^2\equiv a\pmod p (a+b)^p\equiv \sum_{i=0}^pC_p^ia^ib^{p-i}\equiv a^p+b^p\pmod p

当 i ≠ p 且 i ≠ 0 时，p | C_p^i=\dfrac{p!}{i!(p-i)!}

我们称 a 为 p 的二次剩余

判定方法：

a^{\frac{p-1}{2}}\equiv 1\pmod p a^{p-1}\equiv 1\pmod p a^{\frac{p-1}{2}}\equiv ±1\pmod p (x^2)^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1\pmod p n$ 找 $x^2\equiv n\pmod p 假设 $\exists i ,s.t.i^2\equiv a^2-n\pmod p i^{p}\equiv i\cdot (i^2)^{\frac{p-1}{2}}\equiv i\cdot (a^2-n)^{\frac{p-1}{2}}\equiv-i (a+i)^{p+1}\equiv a^{p+1}+i^{p+1}\equiv a^2-i^2\equiv n\pmod p (a+i)^{\frac{p+1}{2}}\equiv x \pmod p

例题：二次剩余

首先，随机化取 a，重载虚数乘法，然后像上式推导一样去求解，代码如下，自行理解。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x = 0 ,f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch & 15);
        ch = getchar();
    }
    return x * f;
}
int N ,p ,itp ,a ,T;
struct point {
    int xt ,pt;
    point operator *(const point &a)const {
        return point{(((xt * a.xt) % p) + ((((itp * pt) % p) * a.pt) % p)) % p ,(((xt * a.pt) % p) + ((pt * a.xt) % p)) % p };
    }
};
inline point Fast_power(point a ,int b ,int p) {
    // Fast_power(a ,b ,Mod) = a^b Mod p
    point answer = point{1 ,0} ,at = a;
    while(b) {
        if(b & 1) answer = (answer * at);
        at = (at * at);
        b >>= 1;
    }
    return answer;
}
inline int Fpower(int a ,int b ,int p) {
    // Fast_power(a ,b,Mod) = a^b Mod p
    int answer = 1 ,at = a;
    while(b) {
        if(b & 1) answer = (answer * at) % p;
        at = (at * at) % p;
        b >>= 1;
    }
    return answer;
}
int _rand(int l ,int r) {
    return (rand() % (r - l + 1) + l);
}
bool check(int x) {
    return (Fpower(x ,(p - 1) >> 1 ,p) == 1);
}
void sovle() {
    N = read() ,p = read();
    if(N == 0) {
        cout << 0 << '\n';
        return ;
    }
    if(!check(N)) {
        cout << "Hola!" << '\n';
        return ;
    }
    a = _rand(0 ,p - 1);
    while(check((a * a - N + p) % p)) a = _rand(0 ,p - 1);
    itp = (a * a - N + p) % p;
    int x1 ,x2;
    point ptd = Fast_power(point{a ,1} ,(p + 1) / 2 ,p);
    x1 = ptd.xt;
    x2 = (- ptd.xt + p) % p;
    if(x1 == x2) cout << x1 << '\n';
    else cout << min(x1 ,x2) << ' ' << max(x1 ,x2) << '\n';
    return ;
}
signed main() {
    srand(time(NULL));
    T = read();
    while(T --) {
        sovle();
    }
    return 0;
}
让我过吧，求你了管理大大