一种运用游程编码的大数模乘算法

doi:10.3778/j.issn.1002-8331.2010.30.022

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (30): 75-77.DOI: 10.3778/j.issn.1002-8331.2010.30.022

一种运用游程编码的大数模乘算法

梁小英，黄铮

北京邮电大学理学院，北京 100876

收稿日期:2009-07-13 修回日期:2009-08-25 出版日期:2010-10-21 发布日期:2010-10-21
通讯作者: 梁小英

Run-length coding-based modular multiplication algorithm

LIANG Xiao-ying，HUANG Zheng

School of Science，Beijing University of Posts and Telecommunications，Beijing 100876，China

Received:2009-07-13 Revised:2009-08-25 Online:2010-10-21 Published:2010-10-21
Contact: LIANG Xiao-ying

摘要/Abstract

摘要： 为了优化提高大整数模乘的运算效率，基于以空间换时间的思想，在改进滑动窗口编码的基础上，提出了一种新颖的游程编码，并在此基础上，设计了一种快速大数模乘的实现算法，分析了该算法的时间复杂度和空间复杂度。分析结果表明，与基于最佳滑动窗口编码的大数模乘算法相比，所设计的算法在保持空间复杂度数量级的同时，时间效率上得到了很大的提高。在同等硬件软件环境下测试，新算法平均运算速度比前者约提高41%。此外，新算法的预处理过程也更加简单。

关键词: 公钥密码, 大数模乘, 滑动窗口编码, 游程编码

Abstract: To optimize the modular multiplication of large integer，based on the idea of winning time at the cost of space.A novel run-length coding method is proposed by modifying sliding window coding.And then a fast modular multiplication algorithm is designed，and its time complexity and space complexity are analyzed.Finally，the algorithm’s efficiency is compared to which based on the optimal sliding window coding.The newly designed algorithm greatly exceed the latter one in the time complexity while remain the same level in the space complexity.Tested under the same environment，the former algorithm’s efficiency increases 41%.

Key words: public-key cryptosystem, modular multiplication, sliding window coding, run-length coding

中图分类号:

TP309.7

梁小英，黄铮. 一种运用游程编码的大数模乘算法[J]. 计算机工程与应用, 2010, 46(30): 75-77.

LIANG Xiao-ying，HUANG Zheng. Run-length coding-based modular multiplication algorithm[J]. Computer Engineering and Applications, 2010, 46(30): 75-77.

[1]	李臣意1，张玉磊1，张永洁2，王彩芬1. 高效的TPKC→IDPKC的异构签密方案[J]. 计算机工程与应用, 2018, 54(2): 125-130.
[2]	张建中，杨丽. 无证书代理盲签名方案的密码学分析与改进[J]. 计算机工程与应用, 2014, 50(4): 90-93.
[3]	郝欣，杨频，李坤. 基于NTRU的RFID三方认证协议研究[J]. 计算机工程与应用, 2014, 50(3): 63-66.
[4]	贾宗璞，李贺，宋成，张霄宏. 一种高效的无证书三方密钥协商协议[J]. 计算机工程与应用, 2014, 50(10): 105-107.
[5]	孙小雁1，张茂胜2，3，朱晓姝1，李硕明4. 多变量分支混沌签名体制[J]. 计算机工程与应用, 2013, 49(2): 97-99.
[6]	董学东1，张妍2. 二次整数环上的ElGamal密码体制和签名方案[J]. 计算机工程与应用, 2013, 49(19): 73-74.
[7]	吴涛1，黄莉静2. 一种改进的系统间隐私保持协同过滤推荐算法[J]. 计算机工程与应用, 2013, 49(15): 80-83.
[8]	张善文，周争光，王宝仓. 基于改进的RSA公钥密码算法的电子公文加密方案[J]. 计算机工程与应用, 2012, 48(28): 127-129.
[9]	刘奇琦，龚晓峰. 一种二值图像连通区域标记的新方法[J]. 计算机工程与应用, 2012, 48(11): 178-180.
[10]	邹惠，王建东. 不同权限下自证实的多秘密共享方案[J]. 计算机工程与应用, 2011, 47(7): 93-95.
[11]	魏萍¹，陈海滨¹，杨晓元^1，2. 一个安全无证书的盲签名方案[J]. 计算机工程与应用, 2011, 47(5): 96-97.
[12]	魏俊懿1，杨晓元1，2，3，余丹1. 一种前向安全的无证书代理盲签名方案[J]. 计算机工程与应用, 2011, 47(34): 95-97.
[13]	魏春艳，蔡晓秋. 安全的无证书签密方案[J]. 计算机工程与应用, 2011, 47(29): 90-92.
[14]	卢明龙，徐开勇. 军事网格中资源发现认证模型研究[J]. 计算机工程与应用, 2011, 47(18): 103-105.
[15]	余丹1，杨晓元1，2，陈海滨1. 无证书的代理盲签名方案[J]. 计算机工程与应用, 2011, 47(13): 110-112.

一种运用游程编码的大数模乘算法

Run-length coding-based modular multiplication algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics