大整数基本运算研究报告与实现分析.docx

大整数基本运算研究报告与实现分析 大整数基本运算研究报告与实现分析 大整数基本运算研究报告与实现分析 个人资料整理 仅限学习使用 大整数乘法的实现与剖析 个人资料整理 仅限学习使用 摘 要 跟着计算机信息安全要求的不停提升，密码学被大批应用到生活中。 RSA 、 ElGamal、 DSA、 ECC 等公钥密码算法和数字署名算法都成立在大整数运算的基础上， 比较耗时的大整数乘法、除法、模乘、幂运算、幂乘等运算却被上述算法大批使用， 它们的运算速度对这些算法的高效实现起侧重要的作用，怎样快速实现上述几种运算 是公钥密码领域广泛关注的热门问题。 本文鉴于 32 位的系统，第一采纳模块化的思想成立大整数运算库的基础框架，在 实现一些协助函数后在此框架上议论并实现多精度大整数的基本加法、减法、乘法、 除法、平方算法、减少、模乘、模幂乘等算法。所用程序均采纳 C/C++语言编写，所 采纳的优化也均成立在 C/C++语言这一层面上，在保证算法有足够高的效率的同时力 求代码清楚易懂，函数接口简单了然，拥有可移植性和稳固性。 重点词： 多精度大整数， Comba，Montgomery，二分查找，笔算 注：本设计 论文）题目根源于公司工程。 个人资料整理 仅限学习使用 Abstract Nowadays, as computer information security requirements improve continuously, the cryptology has been widely applied to life. Public key cryptographic algorithms and digital signature algorithms such as RSA, ElGamal, DSA, ECC are all base on multiple precision arithmetic. Multiple precision multiplication, Division, modular multiplication ,exponen- tiation, modular exponentiation which need more working time is used by public key cryptographic algorithms widely, their speed is very important to the implementations of those algorithms. How to fast implement those arithmetic above is the hot topic in the public key cryptographic field. This paper is based on the 32 bit system. First of all,we found the modular foundation of multiple precision arithmetic library 。 After some auxiliary function is formed, we discuss and implement the multiple precision integer basic addition,Subtraction, multiplication,, kinds of square algorithms,division, reduction, and some relational function. All the algorithm discuss in this paper is implement entirely in portable ISO C/C++and the optimization of those algorithms implementations is built on the C/C++ language level. the algorithm has high enough to ensure the efficiency of the code at the same time strive to clearly understand, simple interface function with portability and stability. Key words:Multiple Precision Integer,Comba,Montgomery,Binary search, Written calculation 个人资料整理 仅限学习使用 目录 个人资料整