离散对数的理论基础

索引

• 传送门
  • 定理1 设m\in {{\mathbb{Z}}_{>1}}存在原根r, 则1,r,{{r}^{2}},\cdots ,{{r}^{\varphi \left( m \right)-1}}构成模m的一个既约剩余系.
  • 定理2 若m\in {{\mathbb{Z}}_{>1}}存在原根r, 对任意整数a, 当\gcd \left( a,m \right)>1时, 方程{{r}^{x}}\equiv a\text{ }\bmod m无解（注意未知数x位于指数位置）.
  • 定理3 若m\in {{\mathbb{Z}}_{>1}}存在原根r, 对任意整数a, 当\gcd \left( a,m \right)=1时, 方程{{r}^{x}}\equiv a\text{ }\bmod m有唯一解（注意未知数x位于指数位置）.
  • 定义4 若m\in {{\mathbb{Z}}_{>1}}存在原根r, 并且\gcd \left( a,m \right)=1, 根据定理3, 方程{{r}^{x}}\equiv a\text{ }\bmod m具有唯一解, 记作$x\equiv in{{d}_{r}}a\text{ }\bmod \varphi \left( m \r