Euclid algorithm, also called division by turns, is used to calculate the greatest common divisor of two positive integers A and B, which is an important method in number theory and algebra. From the division of integers, we know that for any two integers A and b0, there must be two integers Q and R, which makes a=qb+r, 0≤rb, Q and R unique. This is a basic theorem of number theory.

A series of important properties of integers can be obtained from this. If we use this basic theorem repeatedly, we can get an equation with zero remainder, that is, rn+ 1=0, because b is a finite positive integer in every division. The above method is called Euclidean algorithm.

Theorem: gcd(a, b)=gcd(b, amodb). It is proved that a can be expressed as a=kb+r, then r=amodb. Suppose d is the common divisor of a and B, and there are da, d b, r=a-kb, so d r, so d is (b, amodb).

Stan version of Euclid algorithm;

Euclid algorithm is a traditional algorithm to calculate the greatest common divisor of two numbers, which is very good in theory and efficiency. But he has a fatal flaw, which only appears when the prime number is very large. Considering the current hardware platform, the general integer is 64 bits at most. For such an integer, it is very simple to calculate the modulus between two numbers.

For a platform with a word length of 32 bits, it only takes one instruction cycle to calculate the modules of two integers not exceeding 32 bits, while it only takes several cycles to calculate the modules of integers below 64 bits. But for larger prime numbers, in order to calculate the modulus of two integers exceeding 64 bits, such a calculation process must be designed by the user.

Users may have to adopt a trial and error method similar to manual calculation of multi-digit division, which is not only complicated, but also consumes a lot of CPU time. For modern cryptographic algorithms, it is very common to calculate prime numbers above 128, so it is urgent to abandon division and modulo when designing such programs.