Computer Engineering and Applications ›› 2014, Vol. 50 ›› Issue (22): 136-140.

Previous Articles     Next Articles

Fast algorithm for modular operation

XU Xin, LI Shundong   

  1. School of Computer Science, Shaanxi Normal University, Xi’an 710062, China
  • Online:2014-11-15 Published:2014-11-13

大整数取模的快速运算

许  鑫,李顺东   

  1. 陕西师范大学 计算机科学学院,西安 710062

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

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

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

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