《密码技术与物联网安全：mbedtls开发实战》 —3.8　费马小定理

3.8　费马小定理

费马小定理在公钥密码学和素性检测中有着广泛应用。

定理3-4

设p是一个素数，则对任意整数a，有ap≡a(mod p)

当a和p互素时，此定理也可以表示为a?p-1≡1(mod p)。从上述公式中可以看出，费马小定理是欧拉定理的一个特例。

例3-16

当p=11，a=2时，211-1≡210≡1024≡1(mod 11)

费马小定理还可以用于约简指数。

例3-17　求4103 mod 11

因为整数15和4互为素数，根据费马小定理可知，410≡1 mod 11。

4103≡(410)10(43)≡43≡9 mod 11，所以4103≡9 mod 11。

可见，通过费马小定理可以约简指数，而不用直接计算4103。