原根

定理

• 模$p$原根

  • $p$为奇素数$\Longrightarrow$模$p$的原根存在，且有$\varphi{\left(p-1\right)}$个

  • $g$是模$p$的原根$\Longleftrightarrow g^{p-1}\not\equiv1\left(\mod p^2\right)$或${\left(g+p\right)}^{p-1}\not\equiv1\left(\mod p^2\right)$

• 模$p^{\alpha}$原根

  • 若$p$为奇素数，则$g$为模$p$原根$,g^{p^{k-2}\left(p-1\right)}=1+u_{k-2}\cdot p^{k-1},\left(u_{k-2},p\right)=1\Longrightarrow g$为模$p^k$原根

  • $g$为模$p$原根$\Longrightarrow g$或$g+p$为模$p^2$原根

  • $g$为模$p^2$原根$\Longrightarrow g$为模$p^{\alpha}$原根

  • $g$为模$p^{\alpha}$原根$\Longrightarrow g$与$g+p^{\alpha}$中的奇数为模$2p^{\alpha}$原根

求奇素数$p$原根

• STEP1: 求一个原根$g$

  求出$p-1$的所有素因数$q_1,\cdots,q_s$，则$g$是模$p$的原根$\Longleftrightarrow \forall i,g^{\frac{p-1}{q_i}}\not\equiv1\left(\mod p\right)$

• STEP2: 求所有原根

  对于$\left(d,\varphi\left(m\right)\right)=1$，$g^d$为原根

求$p^{\alpha}$原根

• STEP1: 求$p$的一个原根$g$

• STEP2: 求$p^{\alpha}$的原根

  • 若$g^{p-1}\not\equiv1\left(\mod p^2\right)$，则$g$为原根

  • 若${\left(g+p\right)}^{p-1}\not\equiv1\left(\mod p^2\right)$，则$g+p$为原根

求$2p^{\alpha}$原根

• STEP1: 求$p^{\alpha}$的一个原根$g$

• STEP2: 求$2p^{\alpha}$的原根

  $g$与$g+p^{\alpha}$中的奇数为原根

• 模$m$存在原根$\Longleftrightarrow m=2,4,p^{\alpha},2p^{\alpha}$