摘要
最大公因子(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