《密码技术与物联网安全：mbedtls开发实战》 —3.9.2　模算术–对数

3.9.2　模算术–对数

对于正实数而言，指数函数的逆函数为对数函数，模运算中也有类似于对数的概念。对于正实数而言，以x为底y的对数可以表示为y=xlogx(y)，对于本原根为a的素数p，对a进行模p的幂运算可以产生1到p-1个整数，因此对于任何整数b和素数p的本原根a，都存在唯一的指数i，使得b≡ai mod p成立，其中0≤i≤(p-1)，指数i称为模p下以a为底b的离散对数，记为d loga,p(b)。一些密码学图书也把指数i称为指标，记为inda,p(b)。以3为底模17的整数幂如表3-18所示。

表3-18　以3为底模17的整数幂

有了指数表和对数表，我们可以通过查表法快速计算逆元。以3为底模17的离散对数如表3-19所示。

表3-19　以3为底模17的离散对数

例3-18　计算7关于模17的乘法逆元

通过对数表可知log3,17(7)=11，也就是311≡7 mod 17。

因为316≡311·35≡1 mod 17，所以311关于模17的逆元为35 mod 17。

查阅指数表可得35≡5 mod 17，所以7关于模17的乘法逆元为5，也就是5·7≡1 mod 17。