原根
前置知识
欧拉函数
若正整数m,a，满足\((a,m)=1\)，则\(a^{\phi(m)}\equiv 1(mod\: m)\)
阶
若正整数m,a，满足\((a,m)=1\)，则使得\(a^n\equiv 1(mod \: m)\)的最小正整数n称为a模m的阶，记为\(\delta_m(a)\)
阶的性质
假设\((a,m)=1\)，\(\delta=\delta_m(a)\)，则
- \(a^0,a^1,···,a^{\delta-1}\)在模m意义下两两不同
- \(a^{\gamma}\equiv a^{\gamma'}(mod\: m)\Leftarrow\Rightarrow \gamma\equiv \gamma' (mod \: \delta)\)
- \(\delta | \phi(m)\)
原根
若\(\delta_m(a)=\phi(m)\)，则称a为m的一个原根
原根的存在定理
只有模\(2,4,p^a,2p^a\)存在原根（p是奇质数）
原根的判定定理
设\(m>1\)，g为正整数且\((g,m)=1\)。则g是m的原根当且仅当对于任意\(\phi(m)\)的质因子\(q_i\)，\(g^{\frac{\phi(m)}{q_i}}\not\equiv 1(mod \: m)\)
具体实现求原根
首先找到n的最小原根g,则n 的所有原根可以表示为\(g^k\:mod\: n 且gcd(k,\phi(n))=1\)。
我们在得到n的最小原根g后便可在\(O(\phi(n)log\phi(n))\)的时间复杂度内得到n的所有原根。
点击查看代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 指标
对于质数p，假设g是p的一个原根，则\(g^0,g^1,····,g^{p-2}\)在模p意义下是1，2，···，p-1的一个排列。
假设对于\(1\leq x\leq p-1 有 g^c\equiv x (mod \: p)\)，则称x的指标为c，记作\(ind(x)=c\)
性质
\(\forall 1\leq x,y
\(ind(x^c)\equiv c\cdot ind(x) (mod\: \phi(p))\)
类似于log
求指标--baby step giant step (BSGS)
求\(g^c\equiv x(mod\: p)\)
设\(c=aB-b,当B=\lfloor \sqrt p \rfloor时最优\)
\(g^{aB-b}\equiv x(mod\:p),(0\leq a,b
\((g^B)^a\equiv x\cdot g^b (mod \: p)\)
我们可以分别求出当b=0,1,2,····,B-1时的\(x\cdot g^b\)用map存起来
这样分别对于a=0,1,2,···,B-1，直接查找是否存在右边的值等于左边，记录答案即可
例题