原根&离散对数

1.原根

1.定义:

定义$Ord_m(a)$为使得$a^d\equiv1\;(mod\;m)$成立的最小的d(其中a和m互质)

由欧拉定理可知:

$Ord\le\Phi(m)$

当$Ord_m(a)=\Phi(m)时，称a是模m意义下m的一个原根$(记住原根是a，不是d!)

2.原根的性质:

1.具有原根的数字仅有以下几种形式:$2,4,p^n,2·p^n$(p是奇质数)

2.一个数的最小原根的大小不超过 $m^{\frac14}$

3.若g是m的一个原根，那么$g^d$是m的原根的充分必要条件是$gcd(d,\Phi(m))=1$,

由此可推知一个数的原根个数为$\Phi(\Phi(m))$个

3.求解原根的基本步骤:

判断一个数是否有原根。(通过性质1,枚举质数即可)
求得最小原根。(通过性质2,依次枚举$2～m^{\frac14}$判断即可)
求出所有原根。(通过性质3,枚举次数d即可)

代码实现:

1.筛出质数并进行第一步(顺便把欧拉函数也筛出来):

void get_prime()

{

	is_pri[1]=1;

	for(register int i=2;i<N;i++){

		if(!is_pri[i]) Prime[++tot]=i,phi[i]=i-1;

		for(register int j=1;j<=tot;j++){

			if(1ll*i*Prime[j]>=N) break;

			register int res=i*Prime[j];

			is_pri[res]=1;

			if(i%Prime[j]==0){

				phi[res]=phi[i]*Prime[j];

				break;

			}

			phi[res]=phi[i]*phi[Prime[j]];

		}

	}

}

bool judge(int m)//判断原根有无

{

	if(m==1) return 0;

	if(m==2||m==4) return 1;

	if((m&1)==0) m>>=1;if((m&1)==0) return 0;

	for(int i=2;i<=tot&&(1ll*Prime[i]*Prime[i]<=m);i++)

	{

		if(m%Prime[i]!=0) continue;

		while(m%Prime[i]==0) m/=Prime[i];

		if(m==1) return 1;

		return 0;

	}

	return m;

//这里要return m, 由于Prime[i]*Prime[i]>m即退出的影响

}

2.找出最小原根:

    for(int i=2;1ll*i*i<=phi[m];i++){

	//筛出phi的约数,用于check

		if(phi[m]%i==0){

			st[++top]=i;

			if(i*i!=phi[m]) st[++top]=phi[m]/i;

		}

	}

    int g;

	for(g=2;g<=100;g++)//枚举最小原根

	{

		if(check(g,m)) break;

	}

bool check(int x,int m)

{

	if(Pow(x,phi[m],m)!=1) return 0;

	for(int i=1;i<=top;i++)if(Pow(x,st[i],m)==1) return 0;

	return 1;

}

int Pow(int x,int n,int mod)

{

	int ans=1;

	while(n){

		if(n&1) ans=(1ll*ans*x)%mod;

		x=(1ll*x*x)%mod;

		n>>=1;

	}

	return ans;

}

3.找出所有原根

    int cnt=0;

	register int res=1;

	for(register int i=1;i<=phi[m];i++)

	//由欧拉定理,只用枚举到g^phi[m]

	{

		if(cnt==phi[phi[m]]) break;//个数限制

		res=(1ll*res*g)%m;

		if(gcd(i,phi[m])!=1) continue;

		ans[++cnt]=res;

	}

	sort(ans+1,ans+1+cnt);//由于取了模,要sort

	for(register int i=1;i<=cnt;i++)

	{

		if(i>1) putchar(' ');

		printf("%d",ans[i]);

	}

	puts("");

2.离散对数

1.定义

普通对数:

若$$a^x=b$$则称$x$是$b$以$a$为底的对数,记做$x=log_ab$

离散对数就是把这个放在了模意义下,即求解方程:

\[a^x \equiv b (mod\ p)
\]

2.求解方法

方法1-暴力法: 猜测这东西有循环节,直接暴力枚举x,哈希什么的判循环,循环则无解

方法2-带有数学知识的暴力:

由欧拉定理:$a^{\phi (p)} \equiv 1\ (mod\ p)$

于是我们只需要把$x$从$0$枚举到$\phi(p)-1$就可以了

方法3-正解

BSGS 大步小步算法

这是一种Meet in the middle思想的应用,普通的BSGS只适用于a,p互质的情况,所以我们先讨论a,b互质的情况

BSGS:

我们既然是枚举,那么就有折半枚举这种思想,这里也类似,对于方程:

\[a^x \equiv b\ (mod\ p)
\]

我们可以把$x$表示为$t*u-v$ 的形式,保证$0<v<u$,然后把左边的负的乘过去,就是:

\[a^{ t*u } \equiv a^v*b\ (mod\ p)
\]

相当于是把一个数给除了过去,所以只能用于a,p互质

于是我们发现如果先算出一系列的v取什么值的时候右边的值存入哈希表,然后枚举左边的t,就可以在哈希表中直接查询出解了,并且第一个找到的一定是最小的

所以显然u取$\sqrt {p-1}$的时候比较优秀

时间复杂度$O(\sqrt{p})$,如果手写哈希的话,用map就多一个log

代码:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<cstdlib>

#include<queue>

using namespace std;

const int N=1e5+1;

const int mod=1e6+3;

typedef long long ll;

struct hashlist{

	int key[N],next[N],head[mod<<1];

	int cnt;int vb[N];

	inline void insert(int x,int b){

		register int ret=x%mod,p;

		for(p=head[ret];p;p=next[p]){

			if(key[p]==x) return void(vb[p]=max(vb[p],b));

		}

		++cnt;vb[cnt]=b;key[cnt]=x;next[cnt]=head[ret];head[ret]=cnt;

		return;

	}

	inline int find(int x){

		register int ret=x%mod,p;

		for(p=head[ret];p;p=next[p]) if(key[p]==x) return vb[p];

		return -1;

	}

}Hash;

int p,a,b,sz;

inline int fpow(int x,int k){

	register int res=1;

	while(k){

		if(k&1) res=1ll*res*x%p;

		x=1ll*x*x%p;

		k>>=1;

	}

	return res;

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("BSGS.in","r",stdin);

	freopen("BSGS.out","w",stdout);

#endif

	scanf("%d %d %d",&p,&a,&b);//a^x=b (mod p)

	sz=ceil(sqrt(p-1));//向上取整,保证不会漏解

	register int ans=-1;

	if(b==1) return puts("0"),0;

	for(register int i=0;i<sz;++i) Hash.insert(b,i),b=1ll*b*a%p;

	a=fpow(a,sz);

	register int res=a;

	for(register int i=1;i<=sz;++i){

		register int q=Hash.find(res);

		if(q!=-1) {ans=i*sz-q;break;}

		res=1ll*res*a%p;

	}

	if(ans==-1) puts("no solution");

	else printf("%d\n",ans);

	return 0;

}

扩展BSGS:

然后讨论a,p不是质数的情况

唯一的问题是我们不能直接把一个数给除过去,因为a,p不互质的话a是没有逆元的

我们记$gcd(a,p)=d$,根据同余的一个性质:

若 $a*c \equiv b*c \ (mod \ p)$,$gcd(c,p)=d$,则$a\equiv b \ (mod\ \frac{p}{d})$

于是我们可以通过这个性质不断通过提取左边的一个a去把右边的p给弄成a,p是互质的情况,记录一下我们提取了多少个,最后加入答案就行了,如果提取过程中$b$不能被$d$整除就无解

记得如果在提取过程中已经出解了就要判掉

代码:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<cstdlib>

#include<queue>

#define Set(a,b) memset(a,b,sizeof(a))

using namespace std;

const int N=1e5+1;

const int mod=1e6+3;

typedef long long ll;

inline int fpow(int x,int k,int MO){

	register int res=1;

	while(k){

		if(k&1) res=1ll*res*x%MO;

		x=1ll*x*x%MO;

		k>>=1;

	}

	return res;

}

namespace BSGS{

	struct hashlist{

		int key[N],next[N],head[mod];

		int cnt;int vb[N];

		void clear(){Set(key,0);Set(next,0);Set(head,0);Set(vb,0);cnt=0;}

		inline void insert(int x,int b){

			register int ret=x%mod,p;

			for(p=head[ret];p;p=next[p]){

				if(key[p]==x) return void(vb[p]=max(vb[p],b));

			}

			++cnt;vb[cnt]=b;key[cnt]=x;next[cnt]=head[ret];head[ret]=cnt;

			return;

		}

		inline int find(int x){

			register int ret=x%mod,p;

			for(p=head[ret];p;p=next[p]) if(key[p]==x) return vb[p];

			return -1;

		}

	}Hash;

	inline int solve(int p,int a,int b,int d,int k){

		Hash.clear();int sz=ceil(sqrt(p-1));register int ans=-1;

		for(register int i=0;i<sz;++i){Hash.insert(b,i);b=1ll*b*a%p;}

		a=fpow(a,sz,p);

		for(register int i=1;i<=sz;++i){

			d=1ll*d*a%p;

			register int q=Hash.find(d);

			if(q!=-1) {

				ans=i*sz-q+k;break;

			}

		}

		return ans;

	}

}

int gcd(int a,int b){return (b? gcd(b,a%b):a);}

inline void EXBSGS(int p,int a,int b){

	a%=p;b%=p;

	if(b==1) return void(puts("0"));

	register int g=gcd(a,p),d=1,k=0;

	while(((g=gcd(a,p))!=1)){//不互质就继续消

		if(b%g) return void(puts("no solution"));//gcd不整除 b 则无解

		++k;b/=g,p/=g;d=1ll*d*(a/g)%p;//记录提取数量

		if(b==d) return void(printf("%d\n",k));//答案在消的过程中产生的情况

	}

	register int ans=BSGS::solve(p,a,b,d,k);

	if(ans==-1) return void(puts("no solution"));

	printf("%d\n",ans);

	return ;

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("EXBSGS.in","r",stdin);

	freopen("EXBSGS.out","w",stdout);

#endif

	register int p,a,b;

	while(scanf("%d %d %d",&p,&a,&b)!=EOF) EXBSGS(p,a,b);

}

THE END

updated on 2018.8.16

巴特西

原根&离散对数简单总结