大整数取模的快速运算

计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (22): 136-140.

大整数取模的快速运算

许鑫，李顺东

陕西师范大学计算机科学学院，西安 710062

出版日期:2014-11-15 发布日期:2014-11-13

Fast algorithm for modular operation

XU Xin, LI Shundong

School of Computer Science, Shaanxi Normal University, Xi’an 710062, China

Online:2014-11-15 Published:2014-11-13

摘要/Abstract

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

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

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

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

许鑫，李顺东. 大整数取模的快速运算[J]. 计算机工程与应用, 2014, 50(22): 136-140.

XU Xin, LI Shundong. Fast algorithm for modular operation[J]. Computer Engineering and Applications, 2014, 50(22): 136-140.

[1]	牛淑芬，杨喜艳，李振彬，王彩芬. 基于异构密码系统的混合签密方案[J]. 计算机工程与应用, 2019, 55(3): 61-67.
[2]	王霏，陈明. 标准模型下基于身份的多代理多签名方案[J]. 计算机工程与应用, 2019, 55(18): 67-74.
[3]	王驰，冯桂. 3D-HEVC深度图帧内快速模式决策算法[J]. 计算机工程与应用, 2017, 53(11): 206-210.
[4]	邹昌芝. 无双线性对的基于身份多代理签名方案[J]. 计算机工程与应用, 2016, 52(9): 96-101.
[5]	李明. 新的适用于WSN网络的双方认证密钥协商协议[J]. 计算机工程与应用, 2016, 52(3): 100-102.
[6]	周慧，陈熙，刘增力. 双向二维局部保持鉴别投影应用于人脸识别[J]. 计算机工程与应用, 2015, 51(22): 163-167.
[7]	杨明，陈玲玲. OMP信号稀疏分解的改进ACFOA实现[J]. 计算机工程与应用, 2015, 51(20): 208-212.
[8]	陈　　明. 标准模型下基于身份代理盲签名方案[J]. 计算机工程与应用, 2015, 51(19): 103-109.
[9]	温雅敏1，黎凤霞2，龚征3，唐韶华2. 低功耗AVR微处理器上Quark哈希算法优化实现[J]. 计算机工程与应用, 2014, 50(23): 104-107.
[10]	周庆，王宏. Hadoop平台下全局扩散性分组排列算法研究与实现[J]. 计算机工程与应用, 2014, 50(20): 91-95.
[11]	毛庆，李顺东. 快速傅里叶变换乘法的性能研究[J]. 计算机工程与应用, 2014, 50(19): 16-19.
[12]	汪贵冬，陈跃东，陈孟元. 比例最小偏度单行采样的平方根UKF-SLAM算法[J]. 计算机工程与应用, 2014, 50(17): 63-67.
[13]	张龙翔. 三叉树结构下的群认证密钥协商协议[J]. 计算机工程与应用, 2013, 49(24): 83-87.
[14]	王峰. 新的可恢复消息的指定验证者签名[J]. 计算机工程与应用, 2013, 49(24): 97-99.
[15]	张龙翔. 基于三角矩阵的密钥协商协议的密码学分析[J]. 计算机工程与应用, 2013, 49(20): 68-70.