联系我们 - 广告服务 - 联系电话:
您的当前位置: > 综合 > > 正文

【报资讯】a是模p的二次非剩余?二次剩余定理详情介绍

来源:CSDN 时间:2023-02-14 09:41:02


(资料图片)

在数论中,特别在同余理论里,一个整数X对另一个整数p的二次剩余(英语:Quadratic residue)指X的平方除以p得到的余数。 当存在某个X,式子 x 2 ≡ a m o d    p x^2\equiv a\mod p x2≡amodp 成立时,称“a是模p的二次剩余” 当对任意不成立时,称“ a是模 p的二次非剩余”。 对于质数2来说,每个整数都是它的二次剩余。 所以讨论的都是奇素数。 通过欧拉判别条件…。 其余知识点来源: click click click 带上一道例题click 题意:裸题二次剩余,给定a,n,求x属于[1,p)。Cipolla解法。

#include#include#include#include#include#include#include#include#include#include#include#include#include#define inf 0x3f3f3f3f#define llinf 0x3f3f3f3f3f3f3f3f#define MAX_len 50100*4using namespace std;typedef long long ll;const int mod=1e9+7;struct A{ll x,y;};ll w;A mul_two(A a,A b,ll p){A ans;    ans.x=(a.x*b.x%p+a.y*b.y%p*w%p)%p;    ans.y=(a.x*b.y%p+a.y*b.x%p)%p;    return ans;}A qpow_two(A a,ll n,ll p){A ans;    ans.x=1;    ans.y=0;    while(n)    {if(n&1)        {ans=mul_two(ans,a,p);        }        n>>=1;        a=mul_two(a,a,p);    }    return ans;}ll quickpow(ll a,ll n, ll p){ll res=1;    while(n)    {if(n&1)        {res=(res*a)%p;        }        a=(a*a)%p;        n>>=1;    }    return res;}ll Legendre(ll a,ll p){return quickpow(a,(p-1)/2,p);}ll solve(ll n,ll p){if(p==2)        return 1;    if(Legendre(n,p)-p==-1)    {return -1;    }    ll a,temp;    while(1)    {a=rand()%p;        temp=a*a-n;        w=(temp%p+p)%p;        if(Legendre(w,p)-p==-1)            break;    }    A tmp;    tmp.x=a;    tmp.y=1;    A ans=qpow_two(tmp,(p+1)/2,p);    return ans.x;}int main(){int T;    scanf("%d",&T);    ll a,p,w;    while(T--)    {scanf("%lld %lld",&a,&p);        ll temp=solve(a,p);        if(temp==-1)        {printf("No root\n");            continue;        }        ll f=abs(temp-p);         if(temp>f)        {swap(temp,f);        }        if(f==temp)        {printf("%lld\n",temp);        }        else            printf("%lld %lld\n",temp,f);    }    return 0;}

责任编辑:

标签:

相关推荐:

精彩放送:

新闻聚焦
Top