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. For inputing B and C, an algorithm based on right-shift k-ary reduction proposed by Sorenson was presented for finding the integers x and y which satisfy the least significant bits of Bx-Cy were 0,i.e., Bx-Cy=0(mod2^e) where positive integer e was a constant. It could do a lot of right shifts and reduce a large number of cycles with taking advantage of the algorithm for finding the integers x and y. A fast GCD algorithm was proposed combined with modulus algorithm. When the size of the input was n bits, the worst complexity of the fast GCD algorithm was still O(n²).In the best case, the complexity of the proposed algorithm could achieve O(nlog² nlog logn). The experimental data show that actual implementations given input about more than 200000 bits, the fast GCD algorithm is faster than the Binary GCD algorithm, and the fast GCD algorithm is twice as fast as the Binary GCD algorithm for 1 million bits of input.

According to the unbalanced distribution of the complexity of chosen-prefix collisions under the practical requirement, an improved algorithm of chosen-prefix collisions for MD5 was designed. Combined with Non-Adjacent Form (NAF), the probability related to the complexity of birthday search was deduced under certain conditions, and the relation between the balance parameter and the complexity of birthday search was established. Then based on the above results, the improved algorithm was designed through improving the form of birthday collision by introducing new message block differences. Under the practical requirement for parameters, the complexity of the improved algorithm can reduce one bit on average. The results show that, compared with the original MD5, the improved algorithm defuses imbalance of complexity distribution, reduces the complexity, and is more suitable for practical applications.