论文部分内容阅读
（安徽理工大学计算机科学与技术学院，安徽淮南232001）
摘要： 在RSA、DiffieHellman密码系统的算法中都要用到大整数乘法算术。介绍了Knu th经典乘法、Karatsuba乘法以及它们的计算时间复杂性，在此基础上提出了一个新的大整 数乘法技巧，并且在理论上和实践上被证明是有效的。实验结果也显示改进的大整数乘法算 法在实现大整数乘法运算时具有更高的效率。
关键词：Knuth乘法；Karatsuba乘法；大整数乘法；分治法
中图分类号：TP301.6文献标识 码：A[WT]文章编号：16721098(2008)02006703
Research on Large Integer Multiplication Based on Knuth and
Karatsuba Multiplication
HAN Meng,FANG Xianjin,GUO Yuxiu,LI Tao
(School of Computer Science and Engineering,Anhui University of Science and Tec hnology,Huainan Anhui 232001,China) Abstract:Algorithms in cryptosystem such as RSA and DiffieHellman require larg e integer multiplication. In the paper Knuth classical multiplication, Karatsubamultiplication and their time complexity were presented, on the basis of whicha new large integer multiplication trick was put forward and proved available intheory and practice. The experiment showed that the improved multiplication alg orithm is more efficient in implementation of large integer multiplication.
Key words:Knuth multiplication；Karatsuba multiplication；large integer multipl ication；divide and conquer
对大多数的数论问题并且包括象RSA、ECC等公钥密码系统的算法中，大整数乘法是其中的基 本操作。 关于大整数乘法算术的文献有很多， 例如有Karatsuba乘法、 Toom乘法，快速傅 立 叶变换技巧，Scho[DD(-*2/3]..nhageStrassen技巧，经典的Knuth 乘法等［17］。
大多数乘法运算的技巧都是利用“分治法”工具：将一个大的乘法问题减小为一组较小的乘 法问题，但是一直用同一个单一的方法进行递归到小问题的做法被认为是一个错误的选择。 因为：① 虽然有很多乘法运算的技巧，但是没有一种技巧适用于所有的情况， 在操作数长 度不同的情况下， 不同的乘法技巧所产生的效率是不一样的， 所以应根据乘法运算中的 操 作数长度的不同选择不同的算法； ② 通常情况下，最佳的乘法运算算法应能在递归的不同 层次使用不同的方法。
文章的主要目标是对Karatsuba算法进行改进，试图找出这样一个条件并加以证明，当满足 这个条件时基于分治法的Karatsuba乘法被反复递归地调用，当不满足这个条件时，使用经 典的Knuth乘法进行运算。
1标记
文中所有的大整数都以b进制表示， 基本的算术运算包括两个以b进制表示的单精度整 数的加、 减、 乘、 除。 用b进制表示一个正整数p通常写成 p=(u1u2…un)，其中的单精度整数ui (1≤i≤n)称为数字，并且0≤ui≤b-1 。例如，如果b=232=0x100000000，那么0≤ui≤0xffffffff(1≤i≤n )，则整数(ffffffffffffffff)b有两位数字。
2经典的Knuth乘法及计算时间
若p,q是b进制表示的非负整数，p=(u1u2…un)b, q=(v1v2…vm)b，它们的乘积w可表示成w=p•q=(w1w2…wm+n)b，用经典Knuth乘法［8］ 计算w的算法可表示如下
step1：w1,w2,…,wm+n←0,j←m;
4对大整数乘法的改进
优化大整数乘法的方法是，首先利用分治法递归地调用Karatsuba乘法去减小乘法的规模， 当乘数的长度达到某一个级别时，使用经典的Knuth乘法进行剩下的乘法运算。
定理1存在这样的n，使得经典的Knuth乘法的计算时间 小于Karatsuba乘法。
证明：设T1(n)，T2(n)分别表示经典的Knuth乘法和Karatsuba乘法的计算时间，根 据前面的分析可以得到
T1(n)=n T2(n)=9•nlog23-10n
肯定存在这样的n满足T1(n)≤T2(n)，也就是n2≤9•nlog23-10n ＜9•n
也就是说当n<256时，经典的Knuth乘法的效率要高于Karatsuba乘法。
定理2根据以下策略大整数乘法的效率是最高的：如果n> 16(n=2k)，递归地调用Karatsuba乘法，当n=16时递归调用返回（递归出口）， 调用经典的Knuth乘法计算两个较小整数的乘积。
证明：设T(n)表示Karatsuba乘法的计算时间，假设如果n>m时Karatsuba乘法被递 归地调用，否则经典的Knuth乘法被调用。因此有
T(n)=[JB(｛]m n=m3T(n/2)+5n,n＞m[JB)]令n=2k,h(k)=T(n)=T(2k) ，那么T(n)能写成如下形式
h(k)=3h(k-1)+5•2k=3(3h(k-2)+5•2k-1)+5•2k=…=3k-ih(i)+ 5•3k-(i-1)•2i-1+…+5.30•2k
令 m=2i
h(k)=[SX(]4i+10•2i[]3i[SX)]•nlog23-10n
再令f(i)=[SX(]4i+10•2i[]3i[SX)], 函数f(i) 有最小值，当i=[JB(［][S X(]log2(10log2[SX(]2[]3[SX)])-log2(log2[SX(]4[]3[SX)])[]log22-log2 3[SX)][JB)］]=4时，也就是当i=4时，m=2i=16，T(n)最小，最小值为
Tmin(n)=[SX(]416[]81[SX)]nlog23-10n=O(nlog23 )
5实验结果和结论
目前大多数计算机的字长是32并且大多数C语言的编译器都支持对INTEL MASM指令的调用， 因此本文中一个单精度整数是用232进制表示的。 如果想要计算两个32 bit正整数的乘积， 可以调用下列的汇编代码， 以加快运算速率， 这些代码可以被认为 是一个基本操作，其时间复杂度为O(1)［10］。
//Computes p = (p1p0) = x * y.…
--asm{
mov eax, x
xor edx, edx
muly
; Product in edx:eax
mov ebx, p
mov dword ptr ［ebx］, eax
mov dword ptr ［ebx+4］, edx
}
将经典的Knuth乘法、Karatsuba乘法以及改进的大整数乘法的计算时间进行比较(见表1)， 其中Digits是以232进制表示的乘数的长度，测试环境是AMD Athlon CPU 1.1GHz, 25 6M RAM, Windows XP OS, MS Visual C++ 6.0编译器。
表1三种乘法的计算时间比较s
Digits(232进制)[]Knuth[]Karatsuba[]改进的乘法2560.030.030.015120.040.110.011 0240.170.3810.052 0480.7210.9610.134 0962.7342.8740.3818 19210.9668.3221.141
表1显示Karatsuba乘法的效率在实际中比经典的Knuth乘法要低，这与理论上是不一致的， 原因是Karatsuba乘法涉及到大量的递归调用，在此过程中要花费大量的时间进行内存的请 求与释放。改进的乘法利用了Karatsuba乘法和经典的Knuth乘法的优点：如果用232 进制表示的乘数的长度大于16时，Karatsuba乘法被不断地递归调用，而当长度是16时经典 的Knuth乘法被调用用于计算两个较小整数的乘积。从表1也可看出，改进的大整数乘法算法 比Knuth乘法和Karatsuba乘法明显地减少了计算时间。
参考文献：
［1］R L RIVEST, A SHAMIR, L ADLEMAN. A Method for Obtaining Digit al Signatures and PublicKey Cryptosystems［J］.Communications of the ACM,1978 .21(2) ：120126.
［2］MICHAEL ROSING.Implementing Elliptic Curve Cr yptography［M］. Greenwich: Manning Publications Co,1999：314320.
［3］ANATOLY A,KARATSUBA,Y OFMAN.Multiplication of Multidigi t Numbers on Automata［J］.Soviet Physics Doklady,1963：595596.
［4］DAN ZURAS.On Squaring and Multiplying Large Integers［M］. AR ITH-11: IEEE Symposium on Computer Arithmetic, 1993：260271.
［5］E ORAN BRIGHAM.The fast Fourier Transform and its Applicati ons［M］. New Jersey :Prentice-Hall, Englewood Cliffs, 1988：232242.
［6］A SCHO[DD(-*1/3]..NHAGE,V STRASSEN.Sch nelle Multiplikation Groβer Zahlen［J］.Computing 7, 1971:281292.
［7］DONALD E KNUTH.The Art of Computer Programming,Vol 2 Seminume rical Algorithms［M］.second edition. Massachusetts: Addison-Wesley,1981：7537 61.
［8］A MENEZES,P VAN,OORSCHOT.Handbook of AppliedCryptography［M］.CRC Press Inc., 1996：347351. ［9］TOM ST DENIS.BigNum Math Implementing Cryptographic MultiplePrecision Arithmetic［M］.SYNGRESS Publishing,2003：116126.
［10］THOMAS H CORMEN,CHARLES E LEISERSON,RONALD L. Rivest, Cli fford St ein, 算法导论［M］.第2版.潘金贵,顾铁成,李成法,等译. Massachusetts: The MIT Pr ess, 2001：652658.
(责任编辑：李丽)
摘要： 在RSA、DiffieHellman密码系统的算法中都要用到大整数乘法算术。介绍了Knu th经典乘法、Karatsuba乘法以及它们的计算时间复杂性，在此基础上提出了一个新的大整 数乘法技巧，并且在理论上和实践上被证明是有效的。实验结果也显示改进的大整数乘法算 法在实现大整数乘法运算时具有更高的效率。
关键词：Knuth乘法；Karatsuba乘法；大整数乘法；分治法
中图分类号：TP301.6文献标识 码：A[WT]文章编号：16721098(2008)02006703
Research on Large Integer Multiplication Based on Knuth and
Karatsuba Multiplication
HAN Meng,FANG Xianjin,GUO Yuxiu,LI Tao
(School of Computer Science and Engineering,Anhui University of Science and Tec hnology,Huainan Anhui 232001,China) Abstract:Algorithms in cryptosystem such as RSA and DiffieHellman require larg e integer multiplication. In the paper Knuth classical multiplication, Karatsubamultiplication and their time complexity were presented, on the basis of whicha new large integer multiplication trick was put forward and proved available intheory and practice. The experiment showed that the improved multiplication alg orithm is more efficient in implementation of large integer multiplication.
Key words:Knuth multiplication；Karatsuba multiplication；large integer multipl ication；divide and conquer
对大多数的数论问题并且包括象RSA、ECC等公钥密码系统的算法中，大整数乘法是其中的基 本操作。 关于大整数乘法算术的文献有很多， 例如有Karatsuba乘法、 Toom乘法，快速傅 立 叶变换技巧，Scho[DD(-*2/3]..nhageStrassen技巧，经典的Knuth 乘法等［17］。
大多数乘法运算的技巧都是利用“分治法”工具：将一个大的乘法问题减小为一组较小的乘 法问题，但是一直用同一个单一的方法进行递归到小问题的做法被认为是一个错误的选择。 因为：① 虽然有很多乘法运算的技巧，但是没有一种技巧适用于所有的情况， 在操作数长 度不同的情况下， 不同的乘法技巧所产生的效率是不一样的， 所以应根据乘法运算中的 操 作数长度的不同选择不同的算法； ② 通常情况下，最佳的乘法运算算法应能在递归的不同 层次使用不同的方法。
文章的主要目标是对Karatsuba算法进行改进，试图找出这样一个条件并加以证明，当满足 这个条件时基于分治法的Karatsuba乘法被反复递归地调用，当不满足这个条件时，使用经 典的Knuth乘法进行运算。
1标记
文中所有的大整数都以b进制表示， 基本的算术运算包括两个以b进制表示的单精度整 数的加、 减、 乘、 除。 用b进制表示一个正整数p通常写成 p=(u1u2…un)，其中的单精度整数ui (1≤i≤n)称为数字，并且0≤ui≤b-1 。例如，如果b=232=0x100000000，那么0≤ui≤0xffffffff(1≤i≤n )，则整数(ffffffffffffffff)b有两位数字。
2经典的Knuth乘法及计算时间
若p,q是b进制表示的非负整数，p=(u1u2…un)b, q=(v1v2…vm)b，它们的乘积w可表示成w=p•q=(w1w2…wm+n)b，用经典Knuth乘法［8］ 计算w的算法可表示如下
step1：w1,w2,…,wm+n←0,j←m;
4对大整数乘法的改进
优化大整数乘法的方法是，首先利用分治法递归地调用Karatsuba乘法去减小乘法的规模， 当乘数的长度达到某一个级别时，使用经典的Knuth乘法进行剩下的乘法运算。
定理1存在这样的n，使得经典的Knuth乘法的计算时间 小于Karatsuba乘法。
证明：设T1(n)，T2(n)分别表示经典的Knuth乘法和Karatsuba乘法的计算时间，根 据前面的分析可以得到
T1(n)=n T2(n)=9•nlog23-10n
肯定存在这样的n满足T1(n)≤T2(n)，也就是n2≤9•nlog23-10n ＜9•n
也就是说当n<256时，经典的Knuth乘法的效率要高于Karatsuba乘法。
定理2根据以下策略大整数乘法的效率是最高的：如果n> 16(n=2k)，递归地调用Karatsuba乘法，当n=16时递归调用返回（递归出口）， 调用经典的Knuth乘法计算两个较小整数的乘积。
证明：设T(n)表示Karatsuba乘法的计算时间，假设如果n>m时Karatsuba乘法被递 归地调用，否则经典的Knuth乘法被调用。因此有
T(n)=[JB(｛]m n=m3T(n/2)+5n,n＞m[JB)]令n=2k,h(k)=T(n)=T(2k) ，那么T(n)能写成如下形式
h(k)=3h(k-1)+5•2k=3(3h(k-2)+5•2k-1)+5•2k=…=3k-ih(i)+ 5•3k-(i-1)•2i-1+…+5.30•2k
令 m=2i
h(k)=[SX(]4i+10•2i[]3i[SX)]•nlog23-10n
再令f(i)=[SX(]4i+10•2i[]3i[SX)], 函数f(i) 有最小值，当i=[JB(［][S X(]log2(10log2[SX(]2[]3[SX)])-log2(log2[SX(]4[]3[SX)])[]log22-log2 3[SX)][JB)］]=4时，也就是当i=4时，m=2i=16，T(n)最小，最小值为
Tmin(n)=[SX(]416[]81[SX)]nlog23-10n=O(nlog23 )
5实验结果和结论
目前大多数计算机的字长是32并且大多数C语言的编译器都支持对INTEL MASM指令的调用， 因此本文中一个单精度整数是用232进制表示的。 如果想要计算两个32 bit正整数的乘积， 可以调用下列的汇编代码， 以加快运算速率， 这些代码可以被认为 是一个基本操作，其时间复杂度为O(1)［10］。
//Computes p = (p1p0) = x * y.…
--asm{
mov eax, x
xor edx, edx
muly
; Product in edx:eax
mov ebx, p
mov dword ptr ［ebx］, eax
mov dword ptr ［ebx+4］, edx
}
将经典的Knuth乘法、Karatsuba乘法以及改进的大整数乘法的计算时间进行比较(见表1)， 其中Digits是以232进制表示的乘数的长度，测试环境是AMD Athlon CPU 1.1GHz, 25 6M RAM, Windows XP OS, MS Visual C++ 6.0编译器。
表1三种乘法的计算时间比较s
Digits(232进制)[]Knuth[]Karatsuba[]改进的乘法2560.030.030.015120.040.110.011 0240.170.3810.052 0480.7210.9610.134 0962.7342.8740.3818 19210.9668.3221.141
表1显示Karatsuba乘法的效率在实际中比经典的Knuth乘法要低，这与理论上是不一致的， 原因是Karatsuba乘法涉及到大量的递归调用，在此过程中要花费大量的时间进行内存的请 求与释放。改进的乘法利用了Karatsuba乘法和经典的Knuth乘法的优点：如果用232 进制表示的乘数的长度大于16时，Karatsuba乘法被不断地递归调用，而当长度是16时经典 的Knuth乘法被调用用于计算两个较小整数的乘积。从表1也可看出，改进的大整数乘法算法 比Knuth乘法和Karatsuba乘法明显地减少了计算时间。
参考文献：
［1］R L RIVEST, A SHAMIR, L ADLEMAN. A Method for Obtaining Digit al Signatures and PublicKey Cryptosystems［J］.Communications of the ACM,1978 .21(2) ：120126.
［2］MICHAEL ROSING.Implementing Elliptic Curve Cr yptography［M］. Greenwich: Manning Publications Co,1999：314320.
［3］ANATOLY A,KARATSUBA,Y OFMAN.Multiplication of Multidigi t Numbers on Automata［J］.Soviet Physics Doklady,1963：595596.
［4］DAN ZURAS.On Squaring and Multiplying Large Integers［M］. AR ITH-11: IEEE Symposium on Computer Arithmetic, 1993：260271.
［5］E ORAN BRIGHAM.The fast Fourier Transform and its Applicati ons［M］. New Jersey :Prentice-Hall, Englewood Cliffs, 1988：232242.
［6］A SCHO[DD(-*1/3]..NHAGE,V STRASSEN.Sch nelle Multiplikation Groβer Zahlen［J］.Computing 7, 1971:281292.
［7］DONALD E KNUTH.The Art of Computer Programming,Vol 2 Seminume rical Algorithms［M］.second edition. Massachusetts: Addison-Wesley,1981：7537 61.
［8］A MENEZES,P VAN,OORSCHOT.Handbook of AppliedCryptography［M］.CRC Press Inc., 1996：347351. ［9］TOM ST DENIS.BigNum Math Implementing Cryptographic MultiplePrecision Arithmetic［M］.SYNGRESS Publishing,2003：116126.
［10］THOMAS H CORMEN,CHARLES E LEISERSON,RONALD L. Rivest, Cli fford St ein, 算法导论［M］.第2版.潘金贵,顾铁成,李成法,等译. Massachusetts: The MIT Pr ess, 2001：652658.
(责任编辑：李丽)