Karatsuba算法的应用研究

文章从Karatsuba提出的乘法算法入手,经过逻辑推导,得出一个易于实现的逻辑代数式,根据这个逻辑式设计了一个具有流水线结构的乘法器。并对吞吐率、加速比和效率等性能指标做了详细的分析,用这个算法设计的乘法器结构简单、易于实现流水化,适合于数据量大的定点数的计算。

采用Karatsuba算法在FPGA上实现双精度浮点乘法

双精度浮点运算广泛应用于数值计算和信号处理中,在IEEE754标准中实现两个双精度浮点乘法需要一个53 bit×53 bit的尾数乘法器,这样的一个乘法器若采用FPGA实现需要大量的硬件资源。将Karatsuba算法应用于浮点运算器中,采用FPGA实现了一个浮点乘法器,与传统方法相比该乘法器占用硬件资源较少。

基于Karatsuba和Vedic算法的快速单精度浮点乘法器

针对现有的单精度浮点乘法器存在运算速度慢的问题,该文设计了一种融合Karatsuba算法和Vedic算法两者优点的快速单精度浮点乘法器。该文利用Karatsuba算法减少单精度浮点乘法器的乘法运算次数,将24 bit尾数的乘法运算分解为少位数乘法运算,获得基于3 bit和4 bit的尾数乘法架构;进一步地,利用Vedic算法对单精度浮点乘法器的尾数乘法架构进行优化,利用复杂度低、速度快的加法器实现了Karatsuba算法分解后的3 bit和4 bit的两个基本乘法运算,提高了运算速度。仿真及FPGA验证结果表明,该文设计的单精度浮点乘法器相对于基于传统的Karatsuba算法的单精度浮点乘法器、基于Vedic算法的单精度浮点乘法器,其最大运行时钟频率分别提高了约5倍和2倍。

一种快速乘法算法——Karatsuba乘法算法

分析了一种快速乘法算法即Karatsuba算法的原理 ,比较了它对传统算法所具有的优越性 ,提出并论证了关于该算法的一些定理 。

一种基于多层Karatsuba算法的高效全字模乘器设计

模乘作为许多密码系统的核心算法,是典型的计算密集型任务,往往是加密系统的性能瓶颈.为此,人们提出了各种面向模乘的专用加速电路.为了进一步提高电路性能,基于大数乘法的多层Karatsuba算法原理提出了一种全字Montgomery模乘器结构,有效提高了高基算法中大数运算的效率.提出的多层Karatsuba乘法器结构有效降低了乘法运算粒度,在连续执行大数乘法时使硬件利用率达到最高,同时利用按数据位宽分段运算的方法有效提高了电路的工作频率.基于Virtex7 FPGA器件的综合结果显示,电路时钟频率达到250 MHz,33个周期完成了256位Montgomery模乘运算,延时132 ns.依据我们所知,全字模乘器的综合性能要优于当前最好的工作.提出的设计方法对于如何利用多层Karatsuba算法减小硬件乘法器的面积和关键路径长度提供了切实可行的参考.

大整数Comba和Karatsuba乘法的多核并行化研究

大整数运算广泛地应用于公钥加密算法、大规模科学计算中高精度浮点数运算类以及构建大特征值等领域,然而其大部分算法空间和时间开销都很大,尤其对于核心运算之一的大整数乘法,当数据达到一定规模时,超长的串行计算时间已成为制约算法应用的巨大瓶颈.近几年来,伴随着多核、众核芯片的迅猛发展,通过充分挖掘算法本身的并行度以利用并行处理器的强大计算能力,进而高效地提升算法性能,成为一种研究趋势.本文基于通用多核并行计算平台,研究了大整数乘法Comba及Karatsuba快速算法的并行化,提出了高效的多核并行算法.在算法实现及性能优化上,采用了Open MP+SIMD的多级并行技术,使性能获得巨大提升.在性能测试上,我们使用优化的并行算法与原始串行算法进行对比试验,结果显示,8线程并行Comba算法和Karatsuba算法相比串行对应算法分别实现了5.85倍以及6.14倍的性能加速比提升.

面向Saber算法的并行乘法器

随着量子计算的发展,现有密码系统的安全性将受到严重威胁.Saber算法是抵御量子计算攻击的后量子密码方案之一,但存在多项式商环上模乘占据运算开销过大的问题.鉴此,本文通过对Karatsuba算法和Schoolbook相乘方式的剖析,提出一种面向Saber算法的并行乘法器设计方案.该方案首先利用Karatsuba算法分解模乘运算的关键路径,结合乘法复用和加法替换的策略减少硬件开销,然后采用并行运算电路压缩关键运算路径时长,最后在TSMC 65 nm工艺下,利用Modelsim和DC软件仿真验证.结果表明:该方案运算时长为137个时钟周期,与传统方式相比速度提升46.50%,功耗为87.83 m W,面积为927.32×10^(3)μm^(2).

SIMD-LA模型上的大整数乘法

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

基于改进KOA方法的模2域多项式乘法器的实现

有限域上的多项式乘法器是实现ECC底层运算的关键模块。本文基于Karatsuba-Offman提出的分治思想来简化两个多精度操作数的模乘。通过反复调用一个乘法器进行模乘并将结果逐次累加,减少了单精度操作数乘法的次数,从而降低了运算的复杂度。实验结果显示,这种方法在增加一定路径延时的代价下获得更小的芯片面积和功耗。设计原型改进后适用于无线局域网等要求低功耗、小面积的安全设备中。