Abstract: 大整数取模运算是密码学应用的一种基本运算，尤其是在基于因子分解假设的公钥密码学中占有极其重要的地位。提出的m位和n位两个大整数快速取模算法，是利用分治法思想，将n位的大整数分解为n个独立十进制整数的组合，通过八次大整数乘法建立一个预处理表，能够有效地将大整数取模的计算复杂度降为[O(n(m-n))]，经大量实验数据验证该算法的合理性和高效性。

Key words: 大整数取模, 密码学, 预处理表, 分治法, 计算复杂度

摘要： 大整数取模运算是密码学应用的一种基本运算，尤其是在基于因子分解假设的公钥密码学中占有极其重要的地位。提出的m位和n位两个大整数快速取模算法，是利用分治法思想，将n位的大整数分解为n个独立十进制整数的组合，通过八次大整数乘法建立一个预处理表，能够有效地将大整数取模的计算复杂度降为[O(n(m-n))]，经大量实验数据验证该算法的合理性和高效性。

关键词: 大整数取模, 密码学, 预处理表, 分治法, 计算复杂度