随着计算机在网络会议、商业贸易等方面的应用，人们的安全保密意识不断加强。密码学的发展与应用，在解决信息交换和保障数据信息安全方面，起着不可忽视的作用［1］。在诸如 RSA［2］、ElGamal［3］、ECC［4］等公钥加密算法［5］以及数字签名［6］算法中，大数乘法是必不可少的运算单元之一，它的运算性能极大地影响着这些算法的效率。如何提高大数乘法效率，是公钥密码学领域的热点问题，也是信息时代的需求。

目前，常用的大数乘法算法有：模拟手算算法［7］、快速傅里叶变换算法［8］以及中国余数定理［9］等。模拟手算乘法是较经典的大数乘法算法，该算法思路简单，但效率低下。近年来，大数乘法取得了一些新的进展：Booth算法［10］用相加和相减的操作计算补码数据的乘积；运用并行计算对乘法算法优化；基于GPU实现大数乘法的加速等。

为了实现快速的大数乘法，本文基于BCD码设计了大数乘法算法，并将其扩充到有限实数，实现在计算机上准确表示的实数乘法运算。

1 大数乘法的快速算法设计

本节描述算法，介绍算法所处理的数据形式及其数据的存储结构。

1.1 大数的BCD码表示

大数往往超出整型数据的范围，又由于二进制数不能准确地表示实数，故大数乘法中的乘数与积无法用高级语言中提供的数据类型表示。因此，所设计的算法中的数据均采用BCD码形式，以期得到准确的计算结果。

BCD码是一种采用四位二进制数表示一位十进制数的编码形式，它与十进制数0～9的对应关系如表1所示。

表1 十进制数0～9与BCD码对应表十进制数 BCD码0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001

BCD码分为压缩型BCD码和非压缩型BCD码。一个字节存放两位BCD码的形式称作压缩型BCD码；非压缩型BCD码则是一个字节存放一位BCD码，它在低四位表示十进制数，高四位填0。为了清楚描述算法，且便于处理键入的ASCII码到BCD形式的转换，本文首先采用非压缩BCD码。这样，只需对键入的每一位的ASCII码减去30 H，就能方便地得到对应的BCD码。在完成非压缩BCD码编程计算的实验后，也给出了压缩BCD码计算的参数，以便于性能比较。

1.2 大数的存储结构

设大数乘法算法将计算C=A×B。这里

其中，0≤ai≤9，0≤i≤m-1；0≤bj≤9，0≤j≤n-1；0≤ck≤9，0≤k≤m+n-1；i，j，k，m，n∈N；n≤m。

显然，采用非压缩BCD码存储A需要m个字节，存储B需要n个字节；存储C需要m+n个字节。

1.3 算法的设计与分析

算法的基本思想如下：采用加法操作和移位操作替代乘法，并基于位数较多的被乘数A，预先算出2A，3A，…，9A，以备后续计算之用。因此，需要为上述的每一个数建立m+1位的存储空间。

为了实现快速，采用指针实现移位操作。基于式（1）、式（2）和式（3），移位加法算法如下：

Shift_Add算法中，j值取自两个乘数中的较小值的位数；b为预先算出的A的bj倍为）的第i位。该算法中的移位后的逐位相加有效避免了乘法运算，实现了两个大数相乘。

例1 设A=1 234，B=9 420，C=A×B，求C的值。

分析：A为4位整数，B为4位整数，则C的最大值应为8位整数。

执行Shift_Add的过程如下：当j=0，即B的第0位时，

继续，当j=1，即B的第1位时，

继续，当j=2时，

继续，当j=3时，

最后得到：C=。

2 算法的实现与结果分析

2.1 算法的汇编语言编程实现

基于式（1）、式（2）和式（3），采用 Intel汇编语言在实模式［11］下实现的Shift_Add算法的程序由数据段和代码段组成。程序中以n×n为例进行大数乘法计算，这里n≤5 460。数据段如下：

在数据段中，数据存放方式如下：数据的低位存放于低地址空间数据，高位存放于高地址空间，且有序存放。为了便于编程实现加法运算，A也占用n+1个字节，且最高位填0。

代码段的主要过程SHIFT_ADD如下：

该程序中A的倍数预先算好且分别存放于A2至A9。

2.2 实验及其结果分析

从上述的汇编源程序可以看出：若乘数B中的某位为0，则无须进行加法运算，所以用时较少；若乘数B中的某位非0，则须进行多位加法运算，但无论是何数（0除外），运算时间是相同的。在B中各位均非0的情形下，花费时间最多的地方在过程SHIFT_ADD的第16行至第23行。设这8行中的每条指令的时钟周期位为ICi，则进行一次两个乘数的位数均为n运算所花费的时钟周期为：

文章来源：《大数据》 网址: http://www.dsjzz.cn/qikandaodu/2021/0326/1833.html