【模板】【数论】二次剩余Cipolla算法，离散对数BSGS 算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【模板】【数论】二次剩余Cipolla算法，离散对数BSGS 算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1488字，纯文字阅读大概需要3分钟。

内容图文

Cipolla

LL ksm(LL k,LL n)
{
    LL s=1;
    for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo;
    return s;
}

namespace number
{
    LL D;
    struct Z
    {
        LL x,y;
        Z(LL _x=0,LL _y=0){x=_x,y=_y;}
    };
    Z operator +(const Z &x,const Z &y) {return Z((x.x+y.x)%mo,(x.y+y.y)%mo);}
    Z operator -(const Z &x,const Z &y) {return Z((x.x-y.x+mo)%mo,(x.y-y.y+mo)%mo);}
    Z operator *(const Z &x,const Z &y) {return Z((x.x*y.x%mo+D*x.y%mo*y.y%mo+mo)%mo,(x.y*y.x%mo+x.x*y.y%mo)%mo);}
    Z opt(const Z &x) {return Z(mo-x.x,mo-x.y);}
    Z pwr(Z k,LL n)
    {
        Z s=Z(1,0);
        for(;n;n>>=1,k=k*k) if(n&1) s=s*k;
        return s;
    }
}
using namespace number;//其实这部分像减法，相反数什么的都没什么用...

pair<LL,LL> cipolla(LL k)
{
    k%=mo;
    if(ksm(k,(mo-1)/2)==mo-1) return make_pair(-1,-1);
    if(k==0) return make_pair(0,0);
    LL a=rand()%mo;
    while(ksm((a*a%mo-k+mo)%mo,(mo-1)/2)<=1) a=rand()%mo;
    D=(a*a%mo-k+mo)%mo; 
    LL v=(pwr(Z(a,1),(mo+1)/2)).x;
    return make_pair(v,mo-v);
}

BSGS

LL ds[N];
int ud[N];
#define mo1 10000007
vector<LL> h[mo1];
LL hp[mo1];
int hs(LL v)
{
    int k=v%mo1;
    while(hp[k]!=-1&&hp[k]!=v) k=(k==mo1-1)?k:k+1;
    return k;
}
void BSGS(LL x,LL a)
{
    static LL ds2[N];
    ds2[0]=ds[0]=0;
    LL q=sqrt(mo);
    ud[0]=0;
    LL v=a;
    fo(i,0,q-1) 
    {
        int w=hs(v);
        if(hp[w]==-1) ud[++ud[0]]=w,hp[w]=v;
        h[w].push_back(i);
        v=v*x%mo;
    }
    LL v2=1,vq=ksm(x,q);
    for(int i=0;i-q<=mo;i+=q)
    {
        int w=hs(v2);
        if(hp[w]!=-1)
        {
            int r=h[w].size();
            fo(j,0,r-1) ds2[++ds2[0]]=(i-h[w][j]+mo-1)%(mo-1);
        }
        v2=v2*vq%mo;
    }
    sort(ds2+1,ds2+ds2[0]+1);
    fo(i,1,ds2[0]) if(i==1||ds2[i]!=ds2[i-1]) ds[++ds[0]]=ds2[i];
    fo(i,1,ud[0]) h[ud[i]].clear(),hp[ud[i]]=-1;
}

内容总结

以上是互联网集市为您收集整理的【模板】【数论】二次剩余Cipolla算法，离散对数BSGS 算法全部内容，希望文章能够帮你解决【模板】【数论】二次剩余Cipolla算法，离散对数BSGS 算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---