《密码技术与物联网安全：mbedtls开发实战》 —3.9　离散对数

3.9　离散对数

离散对数是部分公钥算法的理论基础，这些公钥算法包括DH密钥交换算法与数字签名算法等。

3.9.1　模算术–指数

定义3-13

设m是大于1的整数，a是与m互素的正整数，则使am≡1 mod n成立的最小正整数m叫作a对模n的指数，记作ordm(a)。

如果a对模n的指数是φ(n)，则称a为模n的本原根。本原根的重要之处在于其模n的幂运算结果各不相同，并且均与n互素。表3-17为所有小于17的正整数a模17的整数幂，从该表的结果可以看出，每行的计算结果都有周期性，其中3，5，6，7，10，11，12，14为本原根，使得a16≡1 mod 17。

表3-17　模17的整数幂