稀疏形式下的区块式快速指数运算算法  

Algorithm for modular exponentiation by block method in sparse form

作　　者：李繁[1] 刘继[2] 严星[1] 

机构地区：[1]新疆财经大学网络与实验教学中心,乌鲁木齐830012 [2]新疆财经大学统计与信息学院,乌鲁木齐830012

出　　处：《计算机应用研究》2015年第5期1503-1507,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(71261025)

摘　　要：针对在许多类El Gamal公钥密码体制中计算AXmod n与AXBXmod n复杂度高等问题,提出了稀松形式下的区块式快速指数运算算法来改善其模指数运算。使用转换状态图来分析其效能,同时将其概念加以延伸,加强其实用性。分析表明,此算法在预先计算量小的时候有较好的效能,因此也特别适用于像智能卡这类存储空间受限的装置。Computation of the AXmod n or AXBYmod n is complex in many El Gamal-like public-key cryptosystems. This paper used the block method in sparse form to improve the performance of modular exponentiation and analyzed the computational cost using state transition diagram. This method also extended the concept of block method and improved its applicability.Analysis results show that its effective with only limited pre-calculation,thus is suitable for some devices with limited storage space,such as smart card.

关 键 词：公钥密码体制 模指数 稀疏形式 区块算法 

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