知识点简单总结——二次剩余

知识点简单总结——二次剩余

二次剩余

给定 $ n,p $ ，求 $ a,0 \le a < p,a^{2} \equiv n (mod \ p) $ ，其中 $ p $ 为奇素数。

欧拉准则

判断二次剩余的存在性。

众所周知根据费马小定理有 $ n^{p-1} \equiv 1 (mod \ p) $ 。

那么就有 $ ( n ^ { \frac{ p-1 }{ 2 } } ) ^ {2} - 1 \equiv 0 (mod \ p) $ 。

很明显 $ n ^ { \frac{ p-1 }{ 2 } } $ 只可能是 $ 1 $ 或 $ -1 $ 。

性感理解可以证明只有上式结果为 $ 1 $ 时有二次剩余（被打）

利用原根容易证明上式为 $ 1 $ 是存在二次剩余的充要条件。

Cipolla算法

随机找到一个 $ a , a^{2} - n $ 非二次剩余，期望大约 $ 2 $ 次找到符合条件的 $ a $ 。

设 $ i ,i ^ {2} \equiv a ^ {2} - n $ 。

定义成类似虚部的东西。

有 $ (a+i) ^ {p+1} \equiv n $ ，证明：

引理1: $ i^{p}\equiv - i $ ，证明： $ i^{p} = i( a^{ 2 } - n )^{ \frac{p-1}{2} } \equiv - i $ 。

引理2: $ (A+B)^{p} \equiv A^{p} + B^{p} $ ，证明略。

于是有 $ (a+i)^{p+1} \equiv ( a^{p} + i^{p} )(a+i) \equiv (a-i)(a+i) \equiv n $ 。

只需要求出 $ (a+i)^{ \frac{p+1}{2} } $ 即可。

至于为什么结果不含虚部，参见https://kewth.github.io/2019/10/21/二次剩余/

注意二次剩余可能有两个，互为相反数。

#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
template<typename TP>inline void read(TP &tar)
{
    TP ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=ret*10+(ch-'0');ch=getchar();}
    tar=ret*f;
}
struct pat{lint x,y;pat(lint x=1,lint y=0):x(x),y(y){}};
pat mul(pat a,pat b,lint w,lint p){return pat((a.x*b.x%p+a.y*b.y%p*w%p)%p,(a.x*b.y%p+a.y*b.x%p)%p);}
namespace RKK
{
lint fpow(lint a,lint b,lint p){lint ret=1;while(b){if(b&1ll)ret=ret*a%p;a=a*a%p,b>>=1;}return ret;}
lint fpow(pat a,lint b,lint w,lint p){pat ret;while(b){if(b&1ll)ret=mul(ret,a,w,p);a=mul(a,a,w,p),b>>=1;}return ret.x;}
lint fuck(lint n,lint p)
{
    if(p==2) return n%p;
    n%=p;if(fpow(n,p-1>>1,p)==p-1) return -1;
    lint a,w;
    while(1)
    {
        a=rand(),w=(a*a%p-n+p)%p;
        if(fpow(w,p-1>>1,p)==p-1) break;
    }
    return fpow(pat(a,1),p+1>>1,w,p);
}
int main()
{
    srand(time(NULL));
    int TAT;read(TAT);while(TAT--)
    {
        lint n,p;read(n),read(p);if(!n){puts("0");continue;}
        lint ans=fuck(n,p);if(ans==-1){puts("Hola!");continue;}
        if(p-ans<ans) ans=p-ans;
        printf("%lld ",ans);if(p-ans!=ans) printf("%lld",p-ans);putchar('\n');
    }
    return 0;
}
}
int main(){return RKK::main();}

应用

不知道（？）