大整数取模的快速运算  

Fast algorithm for modular operation

作　　者：许鑫[1] 李顺东[1] 

机构地区：[1]陕西师范大学计算机科学学院,西安710062

出　　处：《计算机工程与应用》2014年第22期136-140,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61070189;No.61272435)

摘　　要：大整数取模运算是密码学应用的一种基本运算,尤其是在基于因子分解假设的公钥密码学中占有极其重要的地位。提出的m位和n位两个大整数快速取模算法,是利用分治法思想,将n位的大整数分解为n个独立十进制整数的组合,通过八次大整数乘法建立一个预处理表,能够有效地将大整数取模的计算复杂度降为O(n(m-n)),经大量实验数据验证该算法的合理性和高效性。Modular operation is a basic operation in modern cryptography. It plays an important role in public key cryp-tography based on factorization assumption. This paper proposes a fast modular operation algorithm for the m-bit and n-bit integers. This algorithm, utilizing divide and conquer thought, transfers modular operation into subtractions, and then establishes a preprocessing table to further reduce the computational complexity to O（n（m-n）） . Experiments show that this algorithm outperforms existing algorithms.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]