[笔记] 求质数的原根
2022/7/8 23:23:37
本文主要是介绍[笔记] 求质数的原根,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
素数的原根的定义:若\(g^0,g^1 \cdots g^{p-1}\)在mod p意义下各不相同,则g是p的一个原根。质数的最小的原根通常很小,所以从2开始枚举每一个正整数,判断其是否为p的原根。
判断的方法:如果g不是p的原根,则存在\(0\leq i < j \leq p-1\)满足\(g^i≡g^j\)(mod p),也就是存在d(\(0<d \leq p-1\)),使得\(g^d≡1\)(mod p)。
(接下来的内容请感性理解,不做说明。这种东西把实现方法背下来就行了)
\(g^{p-1}≡1\),所以\(d|p-1\)。最后的做法是,令\(P_1 \cdots P_n\)表示p-1的质因数集合,对于每一个\(P_i\),判断\(g^{\frac{p-1}{P_i}}\)是否与1同余,如果是,则g不合法。如果没有导致不合法的\(P_i\),则g合法。
代码如下:
点击查看代码
LL getG() { vector <LL> ps; LL lft=p-1; for(LL i=2;i*i<=lft;++i) if(lft%i==0) { ps.pb(i); while(lft%i==0) lft/=i; } if(lft>1) ps.pb(lft); rep(i,ps.size()) ps[i]=(p-1)/ps[i]; for(LL i=2;;++i) { bool ok=true; rep(j,ps.size()) if(qpow(i,ps[j],p)==1) { ok=false; break; } if(ok) return i; } }
这篇关于[笔记] 求质数的原根的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-20测试人员都是画画大神,让我看看谁还不会用代码图?
- 2024-05-20年薪百万的程序员都在用的摸鱼方式……
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了