阶与原根学习笔记

2019-04-14 17:37发布

1.阶的定义: (a,m)=1,则最小的正整数r使得a^r=1(mod m) 为a模m的阶。(这玩意a好像可是负的。。) 2.阶的性质: r | φ(m) 。(可用反证法,假设不整除,则……) 3.求阶:(虽然我还不知道这玩意有啥用) 给定互质的a,m,求a模m的阶:

4.原根定义:    若a模m的原根为φ(m),则a为m的一个原根。 5.原根性质: 特别注意:只有m=2,4,p^a,2·p^a时m才有原根(p为奇素数,a≥1)   证明:(太弱了,努力学习中。。) 6.求原根: 首先需要判断一下m是否存在原根(程序中略去,且m仍为奇素数); 然后从2开始枚举每一个与m互质的数,看他模m的阶是否等于φ(m)。 充要条件是:对于正在枚举的i,和φ(m)的每一个不同的质因子p:都有 i^( φ(m)/p )mod m≠1,则i就是m的一个原根! (m的质因数需要预处理出来) 一般原根都会很小,时间复杂度可以理解为O(√m+k·log(m)^2),√m为预处理,k为检验的次数 经测试:10000000以内的数只有: 6252122 101
6497402 115
6933362 113
7871018 101
这四个数的原根大于了100。。 程序中vis[ ]是线性筛素数的bool数组,vis[i]=1表示i非素数。 int pow(int x,int y,int p) { int ret=1,now=x; for(;y;y>>=1,now=1ll*now*now%p) if(y&1)ret=1ll*ret*now%p; return ret; } int Find_Root(int m,int phi_m)//if m has no root,then return 0 { if(vis[m]&&(m%2==1||vis[m/2]))return 0; int cnt=0,lim=int(sqrt(phi_m)),now=phi_m; for(int i=2;i<=lim;i++) if(now%i==0) { tempri[++cnt]=i; while(!(now%i))now/=i; } if(now>1)tempri[++cnt]=now; for(int i=1;;i++) { bool flag=1; for(int j=1;j<=cnt;j++) if(pow(i,phi_m/tempri[j],m)<=1){flag=0;break;} if(flag&&pow(i,phi_m,m)==1)return i; } return 0; }