### Mathematics Euclidean algorithm in blockchain

blocksight 2021-04-23 02:53:35 阅读数:16

mathematics euclidean algorithm blockchain

## Introduce

As mentioned earlier, cryptography is the cornerstone of blockchain , No cryptography , Blockchain is a castle in the air , It's hard to exist . So what is the cornerstone of cryptography ？ The answer is math . Starting from this one , We will introduce some common mathematical knowledge in cryptography from simple to deep . This section focuses on Euclidean algorithm and its extended algorithm . Its application will be reflected in later articles （ Of course , If you have a friend who has studied, you should know ）.

## Euclid algorithm

Euclidean algorithm means ： For any nonnegative integer 𝑎 And positive integers 𝑏, Find the greatest common factor of these two numbers , Write it down as gcd(a,b) The algorithm of , among gcd representative greatest common division The first letter . The problem of the greatest common factor is very basic , It's easy to understand . There are many ways to achieve , Euclidean algorithm takes advantage of the following properties ：gcd(a,b)=gcd(b, a mod b)mod It's modular operation , That is, the operation of finding the remainder . The algorithm itself is relatively simple , Easy to implement , This is mainly about why it can be calculated like this ? Prove the following ： hypothesis a>b, a It can be expressed as a = kb + r（a,b,k,r All are positive integers , And r<b）, be r = a mod b hypothesis d yes a,b A common divisor of , Write it down as d|a,d|b, namely a and b You can divide them all d. and r = a - kb, Divide both sides at the same time d,r/d=a/d-kb/d=m, From the right side of the equation m Integers , therefore d|r therefore d It's also b,a mod b The common divisor hypothesis of d yes b,a mod b The common factor of , be d|b,d|(a-k*b),k It's an integer . , in turn, d|a. therefore d It's also a,b The common factor of therefore (a,b) and (b,a mod b) The common divisor of is the same , Its greatest common divisor must also be equal , Obtain evidence . Specific implementation can refer to the following ：

``// Iterative implementation of Euclidean algorithm public long gcd(long a, long b) { if (b == 0) { return a; } return gcd(b, a % b); }``

## extended euclidean algorithm

What can the extended Euclidean algorithm do ？ Let's look at the following linear equation , The integer solving process of the linear equation is closely related to the greatest common divisor .

For linear equations （𝑎,𝑏,𝑐 Constant ）：

𝑎𝑥+𝑏𝑦=𝑐 It's a common and familiar equation . We talk about special situations ：𝑐=𝑔𝑐𝑑(𝑎,𝑏), It's a linear equation like this ：

𝑎𝑥+𝑏𝑦=𝑔𝑐𝑑(𝑎,𝑏)

More special circumstances , If a,b Coprime , be gcd(a,b)=1, The equation is reduced to ax+by=1 . Such a linear equation must have integer solutions , Euclidean expansion algorithm uses the Euclidean algorithm mentioned above to solve the middle quotient and remainder in the process of greatest common divisor , Do the expansion operation , In seeking 𝑔𝑐𝑑(𝑎,𝑏) In the process of , At the same time, we can get the integer solution of the linear equation (𝑥,𝑦). The sample code is as follows ：

``// extended euclidean algorithm :ax+by=g=gcd(a,b) => // tuplex+tupley=gcd(a,b) public long[] gcdExt(long a, long b) { long ans; long[] tuple = new long; if (b == 0) { tuple = a; tuple = 1; tuple = 0; return tuple; } long[] temp = gcdExt(b, a % b); ans = temp; tuple = ans; tuple = temp; tuple = temp - (a / b) * temp; return tuple; }``

tuple The three numbers in represent the equation 𝑎𝑥+𝑏𝑦=𝑔𝑐𝑑(𝑎,𝑏) The solution in x,y,gcd(a,b)

All right, that's it , If you like , Please pay attention to the official account of the block chain ！！ If you have any questions, please leave a message