> For the complete documentation index, see [llms.txt](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/yuan-gen-yu-zhi-biao/yuan-gen.md).

# 原根

## **定理**

* 模$$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}$$