第3章

数论基础知识

3.1　本章主要内容

数论在密码学中有着非常广泛的应用。为了更好地理解密码学基础知识，本章将讲解与本书相关的数论基础知识。若读者已经熟练掌握了这些数论基础知识，可略过本章内容。表3-1罗列了本书所涉及的相关数论基础知识及相应的简要描述。

表3-1　数论基础知识及简要描述

欧拉定理    m是大于1的整数，如果a和m互素，则aφ(m)≡1(mod m)

费马小定理       p是一个素数，则对任意整数a，有ap≡a(mod p)

费马小定理是欧拉定理的一个特例，可用于证明数字签名方案

离散对数    离散对数是密码学的重要基础，尤其是在公钥密码算法中。DH密钥交换算法和数字签名算法等很多公钥算法均基于离散对数数学难题进行构建