资源描述：
《大整数基本运算的研究与实现分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、大整数乘法的实现与分析摘要随着计算机信息安全要求的不断提高，密码学被大量应用到生活中。RSA、ElGamal、DSA、ECC等公钥密码算法和数字签名算法都建立在大整数运算的基础上，比较耗时的大整数乘法、除法、模乘、幂运算、幂乘等运算却被上述算法大量使用，它们的运算速度对这些算法的高效实现起着重要的作用，如何快速实现上述几种运算是公钥密码领域普遍关注的热点问题。本文基于32位的系统，首先采用模块化的思想建立大整数运算库的基础框架，在实现一些辅助函数后在此框架上讨论并实现多精度大整数的基本加法、减法、乘
2、法、除法、平方算法、缩减、模乘、模幂乘等算法。所用程序均采用C/C++语言编写，所采用的优化也均建立在C/C++语言这一层面上，在保证算法有足够高的效率的同时力求代码清晰易懂，函数接口简单明了，具有可移植性和稳定性。关键词：多精度大整数，Comba，Montgomery，二分查找，笔算注：本设计（论文）题目来源于企业项目。IVAbstractNowadays,ascomputerinformationsecurityrequirementsimprovecontinuously,thecryptol
3、ogyhasbeenwidelyappliedtolife.PublickeycryptographicalgorithmsanddigitalsignaturealgorithmssuchasRSA,ElGamal,DSA,ECCareallbaseonmultipleprecisionarithmetic.Multipleprecisionmultiplication,Division,modularmultiplication,exponen-tiation,modularexponentia
4、tionwhichneedmoreworkingtimeisusedbypublickeycryptographicalgorithmswidely,theirspeedisveryimportanttotheimplementationsofthosealgorithms.Howtofastimplementthosearithmeticaboveisthehottopicinthepublickeycryptographicfield.Thispaperisbasedonthe32bitsyst
5、em.Firstofall,wefoundthemodularfoundationofmultipleprecisionarithmeticlibrary;Aftersomeauxiliaryfunctionisformed,wediscussandimplementthemultipleprecisionintegerbasicaddition,Subtraction,multiplication,,kindsofsquarealgorithms,division,reduction,andsom
6、erelationalfunction.AllthealgorithmdiscussinthispaperisimplemententirelyinportableISOC/C++andtheoptimizationofthosealgorithmsimplementationsisbuiltontheC/C++languagelevel.thealgorithmhashighenoughtoensuretheefficiencyofthecodeatthesametimestrivetoclear
7、lyunderstand,simpleinterfacefunctionwithportabilityandstability.Keywords:MultiplePrecisionInteger,Comba,Montgomery,Binarysearch,WrittencalculationIV目录1绪论11.1题目的背景11.2国内外研究状况11.3本文研究内容22大整数的结构32.1大整数的存取结构32.1.1大整数结构分析32.1.2大整数结构42.2预定义的变量52.3大整数基本函数定义52
8、.3.1大整数初始化操作52.3.2大整数的销毁操作62.3.3大整数的扩展62.3.4大整数的输入和输出函数62.4大整数的移位函数72.4.1字移位运算72.4.2比特移位运算93大整数加法和减法实现133.1符号相同的加法运算133.2符号不相同的加法运算164大整数乘法实现194.1笔算乘法194.2使用Comba方法的快速乘法224.3平方算法244.3.1笔算平方算法254.3.2Comba思想的平方算法27IV5大整数模缩减实现305.1模2的幂305.
