大步小步算法（求解离散对数）

本文主要是介绍大步小步算法（求解离散对数），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

baby step giant step简称为大步小步算法，是一个用来求解离散对数的方法，设a的b次对m取模得b，a与m互质时我们令x=At-B,a的At次等于b*a的B次，之后先对右边的数进行存储，，哈希map速度快一点，之后再从左边找，有则返回值，这是一种类似于meet In the middle 的算法，不难验证我们取t为sqrt（fi（m））则可以搜索到所有数值，为了避免算欧拉函数我们令t=sqrt（m），

扩展大步小步算法，当a与m不互质时，我们把式子写成a*a的x-1次+mn=b，同除d若b%d==0则有解，如d=1则互质BSGS求出，若不是继续递归，这里需要一些特判，如我们一般认为0的0次等于，所以log0 0=1；

下面是代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#include<string.h>
#include<vector>
#include<map> 
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll qpow(ll a,ll b,ll p){
	ll ans=1;
	while(b){
		if(b&1)ans=ans*a %p;
		a=a*a %p;
		b>>=1;
	}
	return ans%p;
} 
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
ll oula(ll n ){
	ll res=n;
	for(int i=1;i*i<=n;i++){
		if(n%i==0)res=res/i*(i-1);
		while(n%i==0)n/=i;
	}
	if(n>1)res=res/n*(n-1);
	return res;
}
ll exoula(ll a,ll b,ll m){
	return qpow(a,b%oula(m)+oula(m),m);
}
ll BSGS(ll a,ll b,ll m,ll ,k=1){
	unordered_map<ll ,ll>hs;
	int t=sqrt(m)+1,cur=b*a%m;
	for(int B=1;B<=t;B++){
		hs[cur]=B;
		(cur*=a)%=m;
	}
	ll at=qpow(a,t,m),now=at;
	for(int A=1;A<=t;A++){
		if(hs[now])return At-hs[now];
		(now*=a)%=m;
	}
	return -100;/*负数要小一点防止不断加一溢出*/ 
}
ll exBSGS(ll a,ll b,ll m,ll k%m){
	if(a==0&&b==0)return 1;
	if(b==1)return 0;
	int d=gcd(a,m);
	if(b%d)return -100;
	else if(d==1)return BSGS(a,b,m,k%m);
	else return exBSGS(a,b/d,m/d,k*a/d%m)+1;
}
ll phim=oula(m);
ll ans=exBSGS(a%m,b%m,m);
if(ans>phim)ans=ans%phim+phim;
else cout<<"No Solution"<<endl;

这篇关于大步小步算法（求解离散对数）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！