首页 > 其他分享 >数论--原根(循环群生成元)

数论--原根(循环群生成元)

时间:2023-03-27 13:04:14浏览次数:41  
标签:正整数 原根 -- zc int 循环群 const include

对于素数 p,如果存在一个正整数 1<a<p,使得 a1,a2,…,ap−1 模 p 的值取遍 1,2,…,p−1 的所有整数,称 a 是 p 的一个原根(primitive root),其实就是循环群的生成元。


如 果 a j ≡ a i ( m o d p ) , 则 i ≡ j ( m o d p − 1 ) 。 这 里 有 两 个 例 子 : 如果 aj≡ai(mod p),则 i≡j(mod p−1)。这里有两个例子:如果aj≡ai(modp),则i≡j(modp−1)。这里有两个例子:


5是7的原根,因为5–>3–>1–>6–>4–>2–>0,然后开始循环

2不是7的原根,因为2–>4–>1–>2–>4…,过早的循环了



如果g是P的原根,就是( g P − 1 ) ≡ 1 ( m o d P ) 当且仅当指数为P-1的时候成立.(这里P是素数).

即 设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根。

φ(m):这货是欧拉函数


定理:


定理一:

设p是奇素数,则模p的原根存在;

定理二:

设g是模p的原根,则g或者g+p是模的原根;

定理三:

设p是奇素数,则对任意,模的原根存在;

定理四:

设1,则g是模的一个原根,则g与g+中的奇数是模2的一个原根。


性质:


性质一:

对于任意正整数a,m,如果(a,m) = 1,存在最小的正整数 d 满足a^d≡1(mod m),则有 d 整除 φ(m),因此Ordm(a)整除φ(m)。这里的d被称为a模m的阶,记为Ordm(a)。

 例如:求3模7的阶时,我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。

19的原根有2,2-4-8-16-13-7-14-9-。。。。

19的原根就一定有4, 4-16-7-9-。。。。。

有8,16所以也就是说如果一个数的原根没有k也就不存在k的幂。


性质二:

记δ = Ordm(a),则a1,……a(δ-1)模 m 两两不同余。因此当a是模m的原根时,a0a1,……a(δ-1)构成模 m 的简化剩余系。

性质三:

模m有原根的充要条件是

m = 1 , 2 , 4 , p , 2 ∗ p , p n , 2 ∗ p n 其 中 p 是 奇 质 数 , n 是 任 意 正 整 数 。 m= 1,2,4,p,2*p,p^n,2*p^n其中p是奇质数,n是任意正整数。m=1,2,4,p,2∗p,p^n ,2∗p^n

其中p是奇质数,n是任意正整数。


性质四:

对正整数(a,m) = 1,如果 a 是模 m 的原根,那么 a 是整数模n乘法群(即加法群 Z/mZ的可逆元,也就是所有与 m 互素的正整数构成的等价类构成的乘法群)Zn的一个生成元。由于Zn有 φ(m)个元素,而它的生成元的个数就是它的可逆元个数,即 φ(φ(m))个,因此当模m有原根时,它有φ(φ(m))个原根。

模m有原根的充要条件:


m=2 m=4 m=P^a m=2*P^a


将P-1进行质因数分解

枚举i,并判断对于每个i是否都有(可以应用快速幂)

第一个符合条件的i就是P的最小原根

对 于 合 数 , 只 要 将 2. 中 的 p − 1 替 换 成 φ ( p ) 即 可 . 对于合数,只要将 2. 中的p-1替换成φ(p)即可.对于合数,只要将2.中的p−1替换成φ(p)即可.


#include<cstdio>
#include<cmath>
inline int phi(int n)
{
    int zc=n,all=sqrt(n);
    for(int i=2;i<=all;i++)
	{
  if(n%i!=0)continue;
    	zc=zc/i*(i-1);
    	while(n%i==0)n/=i;
    }
    if(n>1)zc=zc/n*(n-1);
    return zc;
}
inline int pow(int x,const int y,const int mod)
{
	int res=1;
	for(int i=1;i<=y;i<<=1,x=x*x%mod)if(i&y)res=res*x%mod;
	return res;
}
inline int G(const int m)
{
	const int PHI=phi(m);
	for(int g=2;;g++)
	{
  bool fla=1;
  if(pow(g,PHI,m)!=1)continue;
  for(int i=1;i<PHI;i++)
  	if(pow(g,i,m)==1)
  	{
    fla=0;
    break;
  	}
  if(fla)return g;
	}
}
int m,g;
int main()
{
	scanf("%d",&m);
    g=G(m);
    printf("%d",g);
    return 0;
}

在上面的代码中,容易发现,枚举的i并不是每个每个都有用的, 由性质1可得 枚举i只需要枚举φ(m)的因数就好了


#include<cstdio>
#include<cmath>
inline int phi(int n)
{
    int zc=n,all=sqrt(n);
    for(int i=2;i<=all;i++)
	{
  if(n%i!=0)continue;
    	zc=zc/i*(i-1);
    	while(n%i==0)n/=i;
    }
    if(n>1)zc=zc/n*(n-1);
    return zc;
}
inline int pow(int x,const int y,const int mod)
{
	int res=1;
	for(int i=1;i<=y;i<<=1,x=(long long)x*x%mod)if(i&y)res=(long long)res*x%mod;
	return res;
}
int q[200001];
inline int G(const int m)
{
	const int PHI=phi(m);
	q[0]=0;
	for(int i=2;i<PHI;i++)if(PHI%i==0)q[++q[0]]=i;
	for(int g=2;;g++)
	{
  bool fla=1;
  if(pow(g,PHI,m)!=1)continue;
  for(int i=1;i<=q[0];i++)
  	if(pow(g,q[i],m)==1)
  	{
    fla=0;
    break;
  	}
  if(fla)return g;
	}
}
int m,g;
int main()
{
	scanf("%d",&m);
    g=G(m);
    printf("%d",g);
    return 0;
}

最快的代码:


#include<cstdio>
#include<cmath>
inline int phi(int n)
{
    int zc=n,all=sqrt(n);
    for(int i=2;i<=all;i++)
	{
  if(n%i!=0)continue;
    	zc=zc/i*(i-1);
    	while(n%i==0)n/=i;
    }
    if(n>1)zc=zc/n*(n-1);
    return zc;
}
inline int pow(int x,const int y,const int mod)
{
	int res=1;
	for(int i=1;i<=y;i<<=1,x=(long long)x*x%mod)if(i&y)res=(long long)res*x%mod;
	return res;
}
int q[100001];
inline int G(const int m)
{
	const int PHI=phi(m);
	q[0]=0;
	const int limit=sqrt(PHI);int zc=PHI;
	for(int i=2;i<=limit;i++)
  if(zc%i==0)
  {
  	q[++q[0]]=PHI/i;
  	while(zc%i==0)zc/=i;
  }
	if(zc>1)zc=q[++q[0]]=PHI/zc;
	for(int g=2;;g++)
	{
  bool fla=1;
  if(pow(g,PHI,m)!=1)continue;
  for(int i=1;i<=q[0];i++)
  	if(pow(g,q[i],m)==1)
  	{
    fla=0;
    break;
  	}
  if(fla)return g;
	}
}
int m,g;
int main()
{
	scanf("%d",&m);
    g=G(m);
    printf("%d",g);
    return 0;
}


标签:正整数,原根,--,zc,int,循环群,const,include
From: https://blog.51cto.com/u_14682436/6151685

相关文章

  • flink1.16连接hive2.3.9依赖报错
    Causedby:java.lang.ClassNotFoundException:org.apache.flink.table.gateway.api.endpoint.SqlGatewayEndpointFactory原来的导包依赖是:<groupId>org.apache.flink</gr......
  • Windows RT的桌面模式是一个累赘!
    【编者按】TomWarren是著名科技博客TheVerge的编辑,他上个月参加了IFA2012伯林国际消费电子会展,并亲自目睹了WindowsRT操作系统的庐山真面目。他认为微软在打造更好的触......
  • Windows 8新功能:可在Windows 8平台玩Xbox Games
    我们都知道,Xbox是微软一款游戏机的专有名词,因此微软最近推出的XboxGameson Windows服务困扰了不少人。这个服务将会在下个月伴随着Windows8的发布而推出,是一个专门针对......
  • 图论--网络流最大流问题
    问题表述:给定一幅图(n个结点,m条边),每一条边有一个容量,现在需要将一些物品从结点s(称为源点)运送到结点t(称为汇点),可以从其他结点中转,求最大的运送量。在介绍最大流问题的解决方法......
  • HTC将在9月19日召开发布会,可能发布更便宜的Android或Windows Phone 8手机
    八月末到九月这段时间可以说是非常热闹,各大手机厂商扎堆发布新品,一时间百花齐放。之前已经得到消息,摩托罗拉、诺基亚、亚马逊、苹果、RIM等厂商将会先后在接下来的九月里召......
  • Java数据结构 HashMap 哈希表定义使用
    1.HashMapHashMap是一个散列表,它存储的内容是键值(key-value)映射。其中key和value类型可以相同也就而已不同,根据定义。2.HashMap使用1)定义HashMap<Integer,String>hashmap1......
  • 在开源RunnerGo 中体验高效的性能测试解决方案
    性能测试是软件质量保障的关键环节之一,性能测试可以评估应用的可靠性、稳定性和响应时间。然而,性能测试通常需要大量的时间和资源,因此需要使用高效的性能测试工具来减少测试......
  • Office2013:支持云存储和社交功能 不支持Windows XP和Vista
    微软于北京时间今天凌晨在旧金山Metreon娱乐购物中心举行了发布会,发布了新版Office办公软件Office2013(如左图,Office也有了新的Logo),它将支持云存储和社交功能。而最新消息......
  • 微软将在10月26日发布下一代操作系统Windows 8
    在本月的微软全球开发者大会上,微软终于宣布大家期待已久的新一代Windows8这对于微软来说是一个巨大的转折点,WindowsPhone正在走向成熟,而Windows8从某种程度上讲是微软......
  • Windows平板市场份额跌近1%!iPad再创新高
    虽然之前有不少专家预言平板市场会因为全球经济的疲软而放缓增长速度,但是事实并不是这样。据TTS(Tablet&TouchscreenStrategies)最新研究数据,2012年第二季度全球平板的......