一个改进的Euclid算法
摘要
最大公因子(GCD)计算是计算数论的基础课题之1，它在密码算法和密码分析中有着非常广泛的应用。本文主要研究正整数的GCD计算问题。 本文首先介绍了算法的相关概念和当前现有的GCD算法，然后列出了最大公因子的几个基本性质。在描述了经典Euclid算法及其扩展、2进制GCD算法及其求模逆算法并对它们分析之后，提出了1个在这些算法基础上改进而来的Euclid改进算法。它与Euclid算法相比，在计算过程中不需要处理符号，减少了要赋值的次数。之后，用数学方法证明算法的正确性。用C语言将算法实现，并与之前列举的经典Euclid算法等几个算法比较运算时间的长短，得出结论。对非负数值运算而言，经过改进的Euclid求乘法逆算法比原来的相应算法在计算大整数乘法逆时速度要快得多，而且这个速度上的差距与运行环境的机器配置高低成反比，与所给出的大整数的规模大小成正比。文章最后将新算法实现的C语言代码列出，以供参考。
关键词:公钥密码体制；最大公因子；Euclid算法；时间复杂度。
Abstract
Greatest Common Divisor (GCD) is one of the basic subjects in computational number theory, it has a wide application in encryption and analysis of cryptography. This thesis has mainly study of the problem of GCD calculation for the positive integers. Firstly, this thesis introduce the related concepts of the algorithm and some GCD algorithms that current existing, then list a few basic properties of Greatest Common Divisor. Describe the classic Euclid algorithm and its extended, the binary GCD algorithm and its inverse module algorithm, and analyze to them after. Based on these algorithms, we put forward a modified Euclid algorithm and its inverse module algorithm. Compared with the Euclid algorithm, it does not need to handle sign during the period of computing, reduce the times of the assignment. After this, prove it with mathematics method. Carry out the algorithm with the C language, and compare its runtime with the classic Euclid algorithm enumerated before, get a conclusion. In the cryptographic system for the nonnegative integers, the modified inverse module Euclid algorithm is faster than the original algorithm when compute the inverse of multiplication, and the difference of the speed is directly proportional to the stand or fall of running environment and is inversely proportional to the magnitude of the integer that we gave. At the end of the thesis, we list the C language code that the new algorithm carry out, and provide a reference.
Keyword:Public key Cryptography; Greatest Common Divisor (GCD); Euclid Algorithm; Time Complexity
本文档为【一个改进的Euclid算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483