一个改进的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