Integer And The If <sub> 2 </ Sub> On The Polynomial Greatest Common Factor Calculated

Greatest Common Divisor(GCD) is one of the basic subject in computational number theory, it has a wide application in encryption and analysis of cryptography, this thesis has a main study of the problem of GCD computation for integers and polynomials on F2.At first, some basic operations in Z have been considered, including addition subtraction multiplication division exact division modular 2~m inversion modular 2m division Montgomery modular multiplication etc., the software-implement-efficient algorithms for these operations have been proposed. For basic operations in F2[x], only the algorithms for multiplication and division have been proposed. All these algorithms above are the bases for fast implementation of GCD computation.Euclidean Algorithm is the classic algorithm for GCD computation, Extended Euclidean Algorithm(EEA) computes cofactors more than Euclidean Algorithm. After analyzing the process of EEA, some very important properties have been gotten. Based on these properties, a necessary and sufficient condition of quotient sequences matching for high-precision numbers and their most significant digit.It is general for Integer GCD algorithms to use one or several basic transformations which reduce the size of the inputs integers, these transformations are denned as Reduction in this paper. Most-Significant-Digit-first Lehmer class Reduction, Least-Significant-Digit-first K-ary class Reduction have been introduced, the improving of JW Reduction for software implementation is highlighted. For the purpose of Extended GCD computation, the modified Reduction of JW Reduction — M-JW Reduction has been proposed. After analyzing and comparing these Reduction methods, combining JW Reduction with several other Reductions, a GCD algorithm has been gotten, it is more efficient for 512-16384 bits integers then binary GCD and Lehmer GCD Algorithm. Moreover, The applications of GCD algorithm for the modular division and Montgomery modular inversion operations have been considered in this paper.The methods to compute integer GCD can be generalize trivially for the GCD computation on F2M, so only the different method of JW Reduction implementation in F2[X] has been discussed. With the conception of reversal, once computation of division modular x~2w has been reduced and the efficiency of JW Reduction in F2[x] has been improved.