构造性算法用于确定模n的原始根集合

阅读量：

索引

符号
- 引理1: 假设 $d$ 表示 ${{x}_{0}}$ 相对于模 $m$ 的指数, 那么对于所有整数 $x$ 满足 $x\equiv {{x}_{0}}\text{ }\bmod m$ , $x$ 相对于模 $m$ 的指数同样为 $d$ . 此时可以将集合 $\left\{ x\in \mathbb{Z}:x\equiv {{x}_{0}}\text{ }\bmod m \right\}$ 定义为模 $m$ 的一个指数集合. 特别地, 当 $d=\varphi \left( m \right)$ 时, 此集合则被称为模 $m$ 的一个原根集合.
- 引理2: 若 $p$ 是一个奇素数, 则存在模 $p$ 的原根.
- 引理3: 假设 $p$ 是素数, 若 $d$ 整除 $p-1$ , 则必然存在非空集合 $X\left( d \right)$ .
- 引理4: 设 $p$ 为素数, 若 $d$ 整除 $p-1$ , 则有 $\left| X\left( d \right) \right|=\varphi \left( d \right)$ .
- 推论5: 假设 $p$ 是素数且 $d|p-1$ , 则有集合表达式为: $X\left( d \right)=\left\{ \left( {{a}^{k}}\bmod p \right):\text{ }\gcd \left( d,k \right)=1 \right\}.$

全部评论 (0)

还没有任何评论哟~