本文提出了一种基于SIMD-LA 模型的大整数乘法的算法,将分治策略与Karatsuba-Offman 算法相结合改进了已有的算法。当使用p 台处理器,大整数长度n <= 256p 时,其时间复杂度为O( p );大整数长度n > 256p 时,其时间复杂度为O( p 1.58⎥⎥⎤⎢⎢⎡pn + p )。其时间复杂度比传统算法有了进一步的提高。

关键词: 大整数乘法, SIMD-LA, 分治策略, Karatsuba-Offman 算法

文档内容节选

SIMDLA模型上的大整数乘法 赵鹏 张丹丹 田振夫 宁夏大学 数学与计算机学院宁夏 银川 750021 摘要本文提出了一种基于SIMDLA模型的大整数乘法的算法将分治策略与Karatsuba Offman算法相结合改进了已有的算法当使用p台处理器大整数长度n 256p时其时间复杂度为O p 大整数长度n 256p时其时间复杂度为O ppic p 其时间复杂度比传统算法有了进一步的提高 关键词 大整数乘法 SIMDLA 分治策略 KaratsubaOffman算法 中图分类号：TP 313 文献标识码：A 1引言 在公钥密码系统RSA中大整数乘法是一种基本的操作为了增强加密的效果RSA密钥 至少为500位一般推荐为1024位然而传统的平易算法和朴素的递归算法的时间复杂度 都为On21因此 提高大整数乘法的速度具有很实际的意义1962年Karatsuba和Offman对朴素的递归方 法做出了改进将大整数乘法的复杂度降为On1581显然大整数乘法具有天然的 可并行性文献2给出了一种在一维线性Systolic上的......