首页 > 代码库 > 恶补数论(二) Baby-Step-Giant-Step 大步小步求离散模对数
恶补数论(二) Baby-Step-Giant-Step 大步小步求离散模对数
知识概述
好吧，我承认这是我初三寒假就听过的知识，然而我现在早就高一了（又是寒假，只不过我已经在省选了．．．）
额，这是求离散模对数的一种算法
也就是求满足方程a^x≡b(mod p)的最小的ｘ（其中ｐ为质数）
考虑将ｘ分块？，根据欧拉定理，只需检查ｘ=0,1,2...p-1是否是解即可，因为a^(p-1)≡1(mod p)当ｘ超过p-1时就开始循环了哦
假设块的大小为m
先检查前ｍ项，a^0,a^1,a^2...a^(m-1)是否满足要求，把ai mod p存在ｈａｓｈ表ｅi里，求出a^m的逆a^(-m)
再考虑下面的ｍ项，a^m,a^(m+1),a^(m+2),...,a^(2m-1)，若存在解，则相当于存在ｉ使ｅi＊a^m≡b(mod n)，两边左乘ａ^(-m)得ｅi≡b ‘ (mod n) (b ‘ =a^(-m)*b(mod p))．这样，只需检查是否存在ei=b ‘ 即可
模板
做个ｈａｓｈ表吧
未测试模板１．０
//orz PoPoQQQ#include <math.h>#define dmin(a,b) ((a)<(b)?(a):(b))int p;//p is a prime.struct Pep{ int first,second; Pep(int _=0,int __=0) : first(_),second(__) {} bool operator < (const Pep &other) const { return first < other.first; }}namespace Hash_Table{#define inf ~0U>>1#define MaxN 10010 struct Linker{ int hash,val; Linker *next; Linker(int _,Linker *__) : hash(_),val(inf),next(__) {} }*fir[MaxN]; inline int &Hash(int x){ int pos=x%MaxN; for(Linker *iter=fir[pos];iter;iter=iter->next) if(iter->hash==x) return iter->val; return (fir[pos]=new Linker(x,fir[pos]))->val; }}inline Pep exgcd(int a,int b){ if(!b)return Pep(1,0); Pep temp=exgcd(b,a%b); return Pep(temp.second,temp.first-x/y*temp.second);}inline int Baby_Step_Giant_Step(int A,int B){ int i,m=ceil(sqrt(p)),temp=1,D=1; for(i=0;i<=m;i++,(temp*=A)%=p){ int &val=Hash_Table::Hash(temp); val=dmin(val,i); D=temp; } for(temp=1,i=0;i<=m;i++,(temp*=D)%=p){ int x=((exgcd(temp,p).first%p)+p)%p; int &val=Hash_Table::Hash(x*B%p); if(val!=inf)return i*m+val; } return -1;}
恶补数论(二) Baby-Step-Giant-Step 大步小步求离散模对数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。