大数相乘毕业论文

大数相乘毕业论文大数相乘毕业论文/大数相乘毕业论文摘要大整数乘法运算经常会遇到溢出或精度不够的问题，而在许多领域要求高精度大整数运算。因而，有很多人在这方面作过努力。大整数运算比较通用的方法有叠加法（小学生乘法）和分治法。叠加法与我们笔算乘法一样，用第一个数的每一位去乘第二个数的每一位，然后把运算结果按权值叠加；分治法是把大整数化为可直接运算的小整数，再进行乘法运算，最后把乘得的结果组合为所求结果。本文在总结这两种方法的基础上，提出一种把叠加与分治相结合的方法——叠加分治法。叠加分治法吸收了叠加法和分治算法的优点。该算法基于分治思想，把大整数分解成较小整数（几十位），再用叠加法运算较小整数，最后把运算结果组合为所求的积。一方面，减少较小整数多次分解与组合带来的在时间上和空间上的开销；另一方面，避免大整数叠加运算在时间上与规模成级数增加开销。最后，本文还设计了一个算法演示程序，对分治算法、叠加算法与本文提出的叠加分治法做出定量分析，并就它们的优劣和适用环境做出详尽阐述。关键词大整数、乘法、分治法、叠加法、叠加分治法AbstractMultiplicationoflargeintegersusuallymeetstheproblemofoverflowingornotenoughaccurate.But,inmanyappliedrealms,highlyaccuratecalculationoflargeintegersisrequested.Asaresult,manypeoplehavemadegreateffortsinthisaspect.Now,thegeneralmethodsarethepen-and-pencilmethodandthedivide-and-conquermethod.Thepen-and-pencilmethod,whichissimilartomultiplywithapen,ismultiplyinglargeintegerswitheverydigitofonenumberbyeverydigitoftheotherone.Differently,thedivide-and-conquermethodistodividelargeintegersintoseveralsmallerintegers(generally,theyaretow),andthen,tocarryonthemultiplicationofthesmallerintegers.Thistextspecifiesanotheralgorithm,whichbasesonthosetwomethods.Thisalgorithm,thatcombinesthepen-and-pencilmethodandthedivide-and-conquermethodtogether,iscalledthecombinativealgorithmofpen-and-pencilanddivide-and-conquer.Itisthecombinationofvirtuesofthepen-and-pencilmethodandthedivide-and-conquermethod.Itsthought,basedonthedivide-and-conquer,isfirstlyusingthedivide-and-conquermethodtodividethelargeintegersintosmallerintegers(severaldozendigits),nextusingthepen-and-pencilmethodtocalculatethesmallerintegers,andthencombiningthecalculatinglyresultsintothedesiredproduct.Ontheonehand,itreducesthetimeexpenseondecomposingsmallerintegersandcombiningtheirproduct.Ontheotherhand,itavoidsthefleetlyincrementalexpenseontimethatcomesfromtheincrementaldigitsoflargeintegers.Lastly,thistextanalyzesthepen-and-pencilmethod,thedivide-and-conquermethod,andthecombinationofpen-and-pencilanddivide-and-conquerquantificationally,andthen,elaboratestheirgoodandbad,andtheirappliedenvironments.Keywordslargeintegers,multiplication,pen-and-pencil,divide-and-conquer,combinativealgorithmofpen-and-pencilanddivide-and-conquer目录摘要 IAbstract II第1章绪论 11.1课题背景 11.2发展状况 11.3各章安排 2第2章算法设计 32.1叠加法 32.2分治法 52.2.1分治法思想简介 52.2.2用分治法设计大整数乘法 72.3叠加分治法 9第3章算法演示设计 113.1概要设计 113.2详细设计 123.2.1主调用模块设计 123.2.2叠加法模块设计 133.2.3叠加分治法模块设计 153.3结果与分析 17结论 19参考文献 20附录英译汉 21F1Divide-and-ConquerandMultiplicationofLargeIntegers 21F1.1Divide-and-Conquer 21F1.2MultiplicationofLargeIntegers 23F2分治与大整数乘法 26F2.1分治 26F2.2大整数乘法 28致谢 31绪论课题背景密码学是用来保证信息安全的一种必要的手段，是信息安全的一个核心。密码学要解决的问题也是信息安全的主要任务，就是解决网上信息的机密性、完整性、不可否认性和可用性。机密性就是要传送一个信息，这个信息只有接收者才能读到，其他的人，其他的用户是无法获取这个信息，即使得到加密以后的形式，也无法打开信息内容。机密性就是要对传送的信息加密，保证信息不泄漏给未经授权的人。完整性就是防止信息被未经授权的人篡改，保证信息不被篡改，而且信息的完整性跟不可否认性是紧密相连的东西。不可否认性和完整性这两条实际上都是一种对信息的一些认证，就是对每一条消息，它是可以通过密码算法加密，用像数字签名一类的认证算法进行识别和认证。可用性当然意思比较明确，就是保证信息与信息系统确实为授权使用者所用[10]。密码学必然包括一些直接的数学理论，很多数学理论对密码学都有直接的应用，如椭圆曲线群中的离散对数问题、整数分解问题、丢番图算法。而这些数学理论在计算机中的实现，大都涉与到大整数的运算。这里所谓的大整数指的是至少上百位之间的数字组成的大整数。比如RSA、Rabin、以与EIGamal等加密机制都需要这种大整数的运算。而现有的计算机一般只能处理32位的二进制整数，少数的可以处理64位整数。因此，大整数的运算就必须借助软件才能实现。发展状况任何一个可以用计算机求解的问题所需的计算时间都与其规模n有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可，…。而当n较大时，问题也就不那么容易处理。为了加快大整数乘法运算，人们对大整数乘法的运算与实现进行了很多研究。目前，大整数的运算方法主要有将大整数运算分解成规模较小整数运算的分治算法和整体运算的叠加算法。参考文献[1,2,3]给出了基于小学生乘法的叠加算法。该思想是把大整数按位分解成整数，然后分别相乘，再按权值叠加得到所乘的积。参考文献[4,5,6]给出了基于大整数化为小整数的分治法。它把大整数分解成两个规模较小的、计算机可直接处理的整数，让小整数相乘，然后在把它们的乘积组合起来，得到所需的大整数之积。前者思路简单，易于实现；但时间复杂度高，随着规模增大，时间花费增加很快。后者随着规模增大，时间花消增大比例不如叠加法大；但是当整数规模较小时，用于分解与合并花费的时间占总运算时间的比例很大。所以本文提出一种把叠加与分治相结合的方法。它首先把大整数分解成规模较小的整数，再用叠加法计算较小整数的值，最后把计算结果组合为所求的原整数的解。各章安排第一章：绪论。主要介绍大整数乘法的应用领域和当前发展状况。第二章：详细描述叠加法、分治法和叠加分治算法的设计思想。第三章：基于VB，设计演示程序，演示以上三种算法。算法设计叠加法叠加算法就是通用的笔算算法思想。在两个大整数相乘中，它用第一个数的每一位去乘第二个数的每一位，再把运算结果按权值叠加，进位处理后，得到所求的结果。具体描述如下文所示。将因数和表示如下：，则和可以记为：，因此，大整数乘法的计算公式为：………（2.1）在本文中，为了方便起见，将的结果称为部分积，将、称为部分因子。根据公式（2.1），大整数叠加算法的计算过程如图2.1所示。从图2.1可知，这种算法的思想是：按照部分积的权值从低到高的顺序，每次计算出所有权值为的部分积，同时完成它们之间的累加，然后再计算权值更高的部分积，依次类推，直到计算出所有的部分积。图2.1中，是权值为的部分积的累加之和，其计算方法如公式（2.2）所示：………（2.2）图2.1叠加法大整数乘法算法根据图2.1所描述的算法思想，得到如下伪代码描述的算法：FunctionMult(X,Y){//X和Y是记录两个整数的数组，返回结果为X和Y的乘积XYFor(i=1；i<len(x)；i++)//乘积叠加运算For(j=1；j<len(y)；j++)R(i+j-1)+=X(i)*Y(j)For(i=1；i<len(x)+len(y)；i++)R(i)向R(i+1)进位ReturnR}//Mult算法2.1由公式（2.1）得，叠加算法共做次乘法。由2.1.1节和图2.1知，该算法还需做次加法运算和次进位处理。在计算时间主要由乘法决定的情况下，它的时间复杂度为：………………（2.3） 又根据图2.1，存储和分别花费单元，存储积需要个单元，因此该算法的空间复杂度为：………………（2.4）分治法分治法思想简介分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。1、分治法所能解决的问题一般具有以下几个特征[5]：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉与到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。2、分治法的基本步骤[6]如图2.2所示，分治法在每一层递归上都有三个步骤：解答子问题解答子问题1解答子问题2规模为的问题规模为的子问题1规模为的子问题2合并为原问题的解图2.2分治技术（典型实例）（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。它的一般的算法设计模式如下：Divide-and-Conquer（P）{if|P|≤n0

thenreturn（ADHOC（P））将P分解为较小的子问题P1、P2、…、Pkfori←1tok

{do

yi←Divide-and-Conquer（Pi）//递归解决Pi}T←MERGE（y1，y2，…，yk）//合并子问题Return（T）}算法2.2其中|P|表示问题P的规模；为一阈值，表示当问题P的规模不超过时，问题已容易解出，不必再继续分解。ADHOC（P）是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过时，直接用算法ADHOC（P）求解。算法MERGE（y1，y2，…，yk）是该分治法中的合并子算法，用于将P的子问题P1、P2、…、Pk的相应的解y1、y2、…、yk合并为P的解。根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。用分治法设计大整数乘法明显地，如果用经典的小学生乘法计算两个位数的大整数，将需要做次乘法运算。似乎不可能有一种算法能使乘法运算次数少于，但事实证明并非如此。分治法就是一个明显的例子。设和都是位的进制整数，现在要计算它们的乘积。将和分别分为2段，每段的长为位(为简单起见，假设是2的幂)，如图2.3所示。图2.3大整数和的分段由此，，。这样，和的乘积为：…（2.5）如果按照公式（2.5）计算，则我们必须进行4次位整数的乘法(，，和)，以与3次不超过位的整数加法(分别对应于公式(2.1)中的加号)，此外还要做2次进位处理(分别对应于公式（2.5）中乘和乘)。所有这些加法和进位共用步运算。设是2个n位整数相乘所需的运算总数，由公式（2.5），则有：………（2.6）由此可得。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式:………（2.7）虽然公式(2.7)看起来比公式（2.5）要复杂些，但它仅需做3次位整数的乘法(，和)，6次加、减法和2次进位。由此可得：….………（2.8）用解递归方程的套用公式法，可得其解为：………………（2.9）由此可见，改用分治法做大整数乘法，从理论上讲，效率有明显提高。根据以上描述的思想，得出大整数相乘的伪代码算法MULT，如下所示：FunctionMULT(X，Y，n){//X和Y为2个小于n位的无符号整数，返回结果为X和Y的乘积XYif（n=1）return(X*Y)else{A=X的左边n/2位：B=X的右边n/2位C=Y的左边n/2位：D=Y的右边n/2位ml=MULT(A,C,n/2)m2=MULT(A-B,D-C,n/2)m3=MULT(B,D,n/2)S=S*(m1左移2n位+(m1+m2+m3)左移n位+m3)return(S)}}//MULT算法2.3公式（2.9）已经给出分治算法的时间复杂度，现在只讨论该算法的空间复杂度。由公式（2.7）可以看出，存储、需要个单元格，存储、A、B、C、D需要个单元格，存储和需要个单元格。由此可得，X乘以Y需要存储空间：….……（2.10）用解递归方程的套用公式法，可得其解为：………………（2.11） 于是，用分治法实现大整数相乘的时间复杂度为，空间复杂度为。叠加分治法由2.1节和2.2节对叠加法和分治法的描述与其效率的分析可知，在理论上讲，分治法的时间效率要高于叠加法。但是，在实际上并非如此[6]。当整数位数很小（如位数小于600）时，分治法的效率反而不如叠加法。这是因为分治法在分割和合并过程中要消耗掉大量的时间，规模越小，分割合并所占的时间比例越大。试想，用另一种方法。既可以避免叠加法在运算过程中因规模增大，时间复杂度以增大；又可以避免因分治法分得过细而带来的分割组合时间的大量增加。这就是本文要提出的叠加分治法。叠加分治法是用分治思想，把超大整数分割成较小整数（一般在30位左右），再用叠加法计算较小整数的积，最后合并为超大整数的积。叠加分治法的伪代码描述如下所示：FunctionMULT(X，Y，n){//X和Y为2个n位的无符号整数，返回结果为X和Y的乘积XYif（n<=LL）{//LL为分割上限，当乘数的规模小于LL，不再分割，调用叠加运算ReturnPen-and-Pencil(X,Y)//用叠加法计算X，Y的积}else{A=X的左边n/2位B=X的右边n/2位C=Y的左边n/2位D=Y的右边n/2位ml=MULT(A,C,n/2)m2=MULT(A-B,D-C,n/2)m3=MULT(B,D,n/2)S=(m1左移2n位+(m1+m2+m3)左移n位+m3)return(S)}}算法2.4算法演示设计为证明第二章所提出的叠加分治算法性能的高效性，本章在VB平台下设计了一个演示程序。概要设计为证明本文提出的叠加分治算法性能的高效性，需要用不同的方法对同一对大整数做乘法运算。因此本演示程序需要完成四个方面的功能：分治实现大整数乘法运算、叠加实现大整数乘法运算、叠加分治实现大整数乘法运算以与它们的效率与结果的比较。当用叠加分治法实现且分治上限变为1时，叠加分治法就退化为分治法。因此，该演示程序大致可以分为三个模块：主调用模块、叠加算法模块、叠加分治与分治共用模块，如图3.1所示。演示程序叠加算法模块叠加算法模块主调用模块叠加分治及分治共用模块息图3.1模块关系图现在对这三个的功能模块做概括说明：主调用模块：实现调用叠加算法模块、叠加分治与分治共用模块和比较运算结果的正确性。叠加算法模块：完成对大整数的叠加运算。叠加分治与分治共用模块：完成对大整数的分治运算和叠加分治运算。详细设计主调用模块设计1、设计界面，如图3.2所示：图3.2主调用模块界面2、主界面窗体与其控件属性设置表3.1主界面窗体与其控件的属性对象功能属性设计时属性值说明Form3程序运行主界面Caption大整数乘法器Command1引导叠加法界面Caption叠加法运算器Command2引导叠加分治法界面Caption叠加分治法运算器Command3判断两种算法计算结果是否相等Caption两种算法计算结果相等否3、窗体中主要过程与其代码的文字简述PrivateSubCommand1_Click()Callform.pen-and-pencil‘调用叠加法模块EndSubPrivateSubCommand2_Click()Callform.cent‘调用叠加分治法模块EndSubPrivateSubCommand3_Click()判断两种方法运算的结果是否相等EndSub叠加法模块设计1、叠加算法界面设计，如图3.2所示：图3.2叠加算法模块界面2、叠加运算窗体与其控件属性设置表3.2叠加运算窗体与其控件的属性对象功能属性设计时属性值说明Form4用户界面窗体Caption叠加法用户界面标题Command1调用运算乘积函数Caption做乘积运算命令按钮标题Command2清空输入输出口Caption清空命令按钮标题Text1输入乘数Text空白MultiLineTrue允许多行输入ScrollBars2垂直滚动条Text2输入乘数Text空白MultiLineTrue允许多行输入ScrollBars2垂直滚动条Text3输出积Text空白MultiLineTrue允许多行输入ScrollBars2垂直滚动条LockedTrue不允许输入Label1指示输入位置Caption因数1Label2指示输入位置AutoWrapTrue控件可以自动调整Caption因数2Label3指示输出位置AutoWrapTrue控件可以自动调整Caption积Label4统计因数1的字符长度AutoWrapTrue控件可以自动调整Caption空Label5统计因数2的字符长度AutoWrapTrue控件可以自动调整Caption空Label6统计积的字符长度AutoWrapTrue控件可以自动调整Caption空3、窗体中主要过程与其代码的文字简述PrivateSubCommand1_Click()T=hefa(text1.text,text2.text)‘对输入因数字符串合法性检查，‘如果合法则返回True；否则，返回Falseif(T)thenxCint(text1.text)；yCint(text2.text)‘因数字符串转化为‘整数赋值给数组x、yr叠加运算（x，y）‘叠加运算x、y赋给rtext3.textCchar(r)‘结果数组转化因数字符串赋值文本3输出为Else报错处理EndIfEndSubPrivateSubText1_KeyPress(KeyAsciiAsInteger)控制因数1的输入，只有输入合法才让输入文本接受EndSubPrivateSubText2_KeyPress(KeyAsciiAsInteger)控制因数2的输入，只有输入合法才让输入文本接受EndSub叠加分治法模块设计1、叠加分治法模块界面设计，如图3.3所示：图3.3叠加分治法模块界面2、叠加分治运算窗体与其控件属性设置表3.3叠加分治运算窗体与其控件的属性对象功能属性设计时属性值说明Form1用户界面窗体Caption叠加分治法用户界面标题Command1调用运算乘积函数Caption做乘积运算命令按钮标题Command2清空输入输出口Caption清空命令按钮标题Text1输入乘数Text空白MultiLineTrue允许多行输入ScrollBars2垂直滚动条Text2输入乘数Text空白MultiLineTrue允许多行输入ScrollBars2垂直滚动条Text3输出积Text空白MultiLineTrue允许多行输入ScrollBars2垂直滚动条LockedTrue不允许输入Text4输入分治下限Text25默认下限Label1指示输入位置Caption因数1AutoWrapTrue控件可以自动调整Label2指示输入位置Caption因数2AutoWrapTrue控件可以自动调整Label3指示输出位置Caption积AutoWrapTrue控件可以自动调整Label4统计因数1的字符长度Caption空AutoWrapTrue控件可以自动调整Label5统计因数2的字符长度Caption空AutoWrapTrue控件可以自动调整Label6统计积的字符长度Caption空AutoWrapTrue控件可以自动调整Label7记录程序开始时间Caption空AutoWrapTrue控件可以自动调整Label8记录程序结束时间Caption空AutoWrapTrue控件可以自动调整Label9提示分治下限Caption分治下限3、窗体中主要过程与其代码的文字简述DimTtimeAsInteger‘记录分治下限SubMul(x()AsInteger,y()AsInteger,r()AsInteger)Ifx(0)<TtimeThen‘如果位数小于下限，则调用叠加法CallPensM(x,y,r)ElseA=left(x,len(x)/2):B=right(x,(len(x)+1)/2)C=left(x,len(y)/2):D=right(x,(len(y)+1)/2)E=A-B:F=C-DCallMul(A,C,r1)CallMul(B,D,r3)CallMul(E,F,r2)EndIfEndSubPrivateSubPensM(x()AsInteger,y()AsInteger,r()AsInteger)DimiAsInteger,jAsIntegerFori=x(0)To1Step-1Forj=y(0)To1Step-1r(i+j)=r(i+j)+x(i)*y(j)NextjNextiEndSubPrivateSubCommand1_Click()T=hefa(text1.text,text2.text,Text4.Text)‘输入字符串合法性检查，‘如果合法则返回True；否则，返回Falseif(T)thenTtime=CInt(Text4.Text)xCint(text1.text)；yCint(text2.text)‘因数字符串转化为‘整数赋值给数组x、yr叠加分治运算（x，y）‘叠加运算x、y赋给rtext3.textCchar(r)‘结果数组转化因数字符串从文本3输出为Else报错处理EndIfEndSub结果与分析图3.4~3.6展示了在VB平台上实现上述三种方法对两个大整数（都是8192位9）相乘，在时间效率上的差异。可以看出，用叠加法耗时2秒（图3.4），用分治法耗时8秒（图3.5），叠加分治法耗时不到1秒（图3.6）。通过它们的差异，得出如下结论：用叠加分治法耗时最少。因而，叠加分治法是一种效率很高的大整数乘法运算方法。同时，也必须注意：当两乘数位数相差很大时，叠加分治法的效率反而不如叠加法的效率。所以当两整数位数相差很大时，叠加法的效率可能比叠加分治法的效率更高。图3.4叠加法运算结果图3.5分治法运算结果图3.6叠加分治法运算结果结论本文以大整数相乘在计算机中的表示为题目，主要讨论了三个方面的问题：叠加法实现大整数乘法、分治法实现大整数乘法、叠加分治法实现大整数乘法。大整数叠加运算是传统的经典算法。在这一部分讨论了大整数的表示方法，大整数的表示采用数组的形式，每个数组元素存放一位十进制整数，以与在这种大整数的存储形式下，探讨了在密码学中经常用到的大整数叠加运算方法是如何实现的。分治法是比较著名的算法思想，分治法实现大整数乘法从理论上提高了大整数乘法运算的效率。本部分主要讨论了分治法是如何实现大整数乘法运算的，并对实现效率做出定性分析。在用叠加分治法实现大整数乘这一部分中，通过分析叠加法、分治法的优劣和它们的应用环境，结合它们的特点，提出了把叠加法和分治法相结合的方法——叠加分治法。在最后一章，做了一个演示程序，演示了本文提出算法的正确性和高效性，对三种算法进行了定性分析。下一步工作与有待改进之处：优化算法，进一步提高运算效率。在现有基础之上，实现大整数的除法运算。在大整数四则混合运算基础上，继续进行其他有关模的运算算法的研究。参考文献[1] 原巍，许琪，沈绪榜.大整数乘法器设计.微电子学与计算机，2003，2003增刊：1-3[2] 罗洋.大整数乘法的计算机处理.辽林师专学报，2005，第1期：39-40[3] 吴晓丽，吴锋.计算机中的大整数运算技术.武警工程学院学报，1999，第15卷第2期：35-37[4] M.H.Alsuwaiyel著，吴伟昶等译.算法设计技巧与分析.北京：电子工业出版社，2004.[5] 王晓东.算法设计与分析.北京：清华大学出版社，2003.[6] [美]AnanyLevitin.IntroductiontoTheDesignandAnalysisofAlgorithms.北京：清华工业出版社，2003.[7] 石研，姚晟.大整数算术运算的实现.安庆师范学院学报（自然科学版）.2004，第10卷第2期：75-77[8] 杨剑等.字符化大整数运算系统的构造与实现.扬州大学学报（自然科学版）.2000，第3卷第4期：52-56[9] 凌晨，买磊.基于两种不同存储方式的大整数运算与性能比较.安庆师范学院学报（自然学报）.2003，第9期第2版：86-88[10] 李爱武.密码学中的大整数运算与其应用.[学位论文].广州：中山大学，2002[11]余祥宣等.计算机算法基础（第二版）.武汉：华中科技大学出版社，2004[12]周彬.大整数模运算算法研究与实现.[学位论文].成都：电子科技大学，2001/ruanjiansp/guide/1388.htm附录英译汉F1Divide-and-ConquerandMultiplicationofLargeIntegersF1.1Divide-and-ConquerDivide-and-conquerisprobablythebest-knowgeneralalgorithmdesigntechnique.Thoughitsfamemayhavesomethingtodowithitscatchyname,itiswelldeserved:quiteafewefficientalgorithmsarespecificimplementationsofthisgeneralstrategy.Divide-and-conqueralgorithmsworkaccordingtothefollowinggeneralplan:1.Aproblem’sinstanceisdividedintoseveralsmallerinstanceofthesameproblem,ideallyofaboutthesamesize.2.Thesmallerinstancesaresolved(typicallyrecursively,thoughsometimesadifferentalgorithmisemployedwheninstancesbecomesmallenough).3.Ifnecessary,thesolutionsobtainedforthesmallerinstancesarecombinedtogetasolutiontotheoriginalproblem.Thedivide-and-conquertechniqueisdiagrammedinFigure1,whichdepictsthecaseofdividingaproblemintotowsmallersubproblems,byfarthemostwidelyoccurringcase(atlestfordivide-and-conqueralgorithmsdesignedtobeexecutedonasingle-processorcomputer).SSolutiontotheoriginalproblemProblemofsizenSubproblem1ofsizeSubproblem1ofsizeSolutiontosubproblem2Solutiontosubproblem1Figure1Divide-and-conquertechnique(typicalcase)Asanexample,letusconsidertheproblemofcomputingthesimofnumbers.If,wecandividetheproblemintotowinstancesofthesameproblem:tocomputethesumofthefirstnumbersandtocomputethesumoftheremainingnumbers.(Ofcourse,ifwesimplyreturnastheanswer.)Onceeachofthesetowsumsiscomputed(byapplyingthesamemethod,i.e.,recursively),wecanaddtheirvaluestogetthesuminquestion:Isthisanefficientwaytocomputethesumofnumbers?Amomentofreflection(whycoulditbemoreefficientthanthebrute-forcesummation?),asmallexampleofsumming,say,fournumbersbythisalgorithm,aformalanalysis(whichfollows),andcommonsense(wedonotcomputesumsthisway,dowe?)allleadtoanegativeanswertothisquestion.Thus,noteverydivide-and-conqueralgorithmisnecessarilymoreefficientthanevenabrute-forcesolution.ButoftenourprayerstotheGoddessofAlgorithmicsareanswer,andthetimespentonexecutingthedivide-and-conquerplanturnsouttobesmallerthansolvingaproblembyadifferentmethod.Infact,thedivide-and-conquerapproachyieldssomeofthemostimportantandefficientalgorithmsincomputerscience.Wediscussafewclassicexamplesofsuchalgorithmsinthischapter.Thoughweconsideronlysequentialalgorithmshere,itisworthkeepinginmindthatthedivide-and-conquertechniqueisideallysuitedforparallelcomputations,inwhicheachsubprolemcanbesolvedsimultaneouslybyitsownprocessor.Thesumexampleillustratesthemosttypicalcaseofdivide-and-conquer:aproblem’sinstanceofsize.Moregenerally,aninstanceofsizecanbedividedintoseveralinstancesofsize,withofthemneedingtobesolved.(Here,andareconstants;and.)Assumingthatsizeisapowerof,simplifyouranalysis,wegetthefollowingrecurrencefortherunningtime:………..(1)whereisafunctionthataccountsforthetimespentondividingtheproblemintosmalleronesandoncombiningtheirsolutions.(Forthesummationexample,and.)Recurrence(1)iscalledthegeneraldivide-and-conquerrecurrence.Obviously,theorderofgrowthofitssolutiondependsonthevaluesoftheconstantsandandtheorderofgrowthofthefunction.Theefficiencyanalysisofmanydivide-and-conqueralgorithmsisgreatlysimplifiedbythefollowingtheorem.MASTERTHEOREMIfwhereinrecurrenceequation(1),then….……….(2)(Analogousresultsholdfortheandnotations,too)Forexample,therecurrenceequationforthenumberofadditionsmadebythedivide-and-conquersummationalgorithm(seeabove)oninputsofsizeis……………..………..……..(3)Thus,forthisexample,,,and;hence,since,….………….…….………(4)Notethatwewereabletofindthesolution’sefficiencyclasswithoutgoingthroughthedrudgeryofsolvingtherecurrence.But,ofcourse,thisapproachcanonlyestablishasolution’sorderofgrowthtowithinanunknownmultiplicativeconstantwhilesolvingarecurrenceequationwithaspecificinitialconditionyieldsanexactanswer(atlestfor’sthatarepowerof).F1.2MultiplicationofLargeIntegersSomeapplications,notablymoderncryptology,requiremanipulationofintegersthatareover100decimaldigitslong.Obviously,suchintegersaretoolongtofitinasinglewordofamoderncomputer,andhencetheyrequirespecialtreatment.Thispracticalneedsupportsinvestigationsofalgorithmsforefficientmanipulationoflargeintegers.Inthissection,weoutlineaninterestingalgorithmformultiplyingsuchnumbers.Obviously,ifweusetheclassicpen-and-pencilalgorithmformultiplyingtow-digitintegers,eachofthedigitsofthefirstnumbersismultipliedbyeachofthedigitsofthesecondnumberforthetotalofdigitmultiplications.(Ifoneofthenumbershasfewerdigitsthantheother,wecanpadashorternumberwithleadingzerostoequaltheirlengths.)Thoughitmightappearthatitwouldbeimpossibletodesignanalgorithmwithfewerthandigitmultiplications,itprovesnottobethecase.Themiracleofdivide-and-conquercomestotherescuetoaccomplishthisfeat.Todemonstratethebasicideaofthealgorithm,letusstartwithacaseoftow-digitintegers,23and14.Thesenumberscanberepresentedasfollows:andNowletusmultiplythem:Thelastformulayieldsthecorrectanswerof322,ofcourse,butitusesthesamefourdigitmultiplicationsasthepen-and-pencilalgorithm.Fortunately,wecancomputethemiddletermwithjustonedigitmultiplicationbytakingadvantageoftheproducts()andthatneedtobecomputedanyway:Ofcourse,thereisnothingspecialaboutthenumberswejustmultiplied.Foranypairoftow-digitnumbersand,theirproductcanbecomputedbytheformulawhereistheproductoftheirfirstdigitsistheproductoftheirseconddigitsistheproductofthesumofthe’sdigitsandthesumofthe’sdigitsminusthesumofand.Nowweapplythistricktomultiplyingtow-digitintegersandwhereisapositiveevennumber.Letusdividebothnumbersinthemiddle—afterall,wepromisedtotakeadvantageofthedivide-and-conquertechnique.Wedenotethefirsthalfofthe’sdigitsbyandthesecondhalfby;for,thenotionsareand,respectively.Inthesenotions,impliesthatandimpliesthat.Therefore,takingadvantageofthesametrickweusedfortow-digitnumbers,wegetwhereistheproductoftheirfirsthalvesistheproductoftheirsecondhalvesistheproductofthesumofthe’shalvesandthesumofthe’shalvesminusthesumofand.Ifiseven,wecanapplythesamemethodforcomputingtheproducts,and.Thus,ifisapowerof2,wehavearecursivealgorithmforcomputingtheproductoftow-digitintegers.Initspureform,therecursionisstoppedwhenbecomesone.Itcanalsobestoppedwhenwedeemsmallenoughtomultiplythenumbersone.Itcanalsobestoppedwhenwedeemsmallenoughtomultiplythenumbersofthatsizedirectly.Howmanydigitmultiplicationsdoesthisalgorithmmake?Sincemultiplicationof-digitnumbersrequiresthreemultiplicationsof-digitnumbers,therecurrenceforthenumberofmultiplicationswillbeSolvingitbybackwardsubstitutionsforyieldsSince(Onthelaststep,wetakeadvantageofthefollowingpropertyoflogarithms:)Youshouldkeepinmindthatformoderatelylargeintegersthisalgorithmwillprobablyrunlongertheclassicone.BrassardandBratley([BB96],pp.70-71)reportthatintheirexperimentsthedivide-and-conqueralgorithmstartedtooutperformthepen-and-pencilmethodonintegersover600digitslong.Ifyouprograminanobject-orientedlanguagesuchasJava,C++,orSma