一、背景

公钥密码学（Public-Key Cryptography, PKC）由Diffie与Hellman于1970年代提出，在现代信息社会中得到了广泛应用。此后基于各种数学困难问题，越来越多的公钥密码算法被设计出来，比如RSA、ElGamal、椭圆曲线ECC算法等。在RSA算法中，模幂（modular exponentiation）是最核心的计算，而模乘（modular multiplication）算法则是模幂计算的基础。在ECC算法中，模乘计算也是必不可少的计算操作之一。以下重点介绍两个快速模乘算法：蒙哥马利（Montgomery）模乘与Barrett模乘。

一个$n$比特大整数 A A