区块链中的数学 - 欧几里得算法

密码学是区块链的基石，没有密码学技术，区块链就是空中楼阁，也难以存在。那么密码学的基石是什么？答案是数学。

前面说过密码学是区块链的基石，没有密码学技术，区块链就是空中楼阁，也难以存在。那么密码学的基石是什么？答案是数学。
从这一篇起始，将会由浅入深的介绍一些密码学中常用的数学知识。本节主要讲欧几里得算法及其扩展算法。其应用会在之后文章中体现（当然，如果已经有研究过的朋友应该已经知晓）。

欧几里得算法

欧几里得算法是指：对于任意的非负整数𝑎和正整数𝑏，求这两个数的最大公因数，记为gcd(a,b)的算法, 其中gcd代表greatest common division首字母。
最大公因数的问题很基础，也很好理解。有多种方法实现，欧几里得算法利用以下性质：
gcd(a,b)=gcd(b, a mod b)
mod是模运算，即求余数运算。算法本身比较简单，很容易实现，这里主要说下为什么可以这么算?
证明如下：
假设a>b, a可以表示成a = kb + r（a，b，k，r皆为正整数，且r<b），则r = a mod b 假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以整除d。
而r = a - kb，两边同时除以d，r/d=a/d-kb/d=m，由等式右边可知m为整数， 因此d|r 因此d也是b,a mod b的公约数
假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数。进而d|a.因此d也是a,b的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。具体实现可参考如下：

//欧几里德算法迭代实现
    public long gcd(long a, long b) {
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
  }

扩展欧几里得算法

扩展欧几里德算法可以用来干什么呢？ 我们来看下面一个线性方程，该线性方程的整数求解过程与最大公约数有密切关系。

对于线性方程（𝑎,𝑏,𝑐为常数）：

𝑎𝑥+𝑏𝑦=𝑐 是普通且熟悉的方程。我们讨论特殊情况：𝑐=𝑔𝑐𝑑(𝑎,𝑏)，也即是这样的线性方程：

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

更特殊的情况，如果a,b互质，则gcd(a,b)=1, 方程简化为 ax+by=1 。
这样的线性方程必然有整数解，欧几里得扩展算法利用上面提到的欧几里德算法求解最大公约数过程中的中间商和余数，进行扩展运算，在求𝑔𝑐𝑑(𝑎,𝑏)的过程中，同时也就求得线性方程的整数解(𝑥,𝑦)。示例代码如下：

//扩展欧几里得算法:ax+by=g=gcd(a,b)  =>
  // tuple[1]x+tuple[2]y=gcd(a,b)
  public long[] gcdExt(long a, long b) {
    long ans;
    long[] tuple = new long[3];
    if (b == 0) {
      tuple[0] = a;
      tuple[1] = 1;
      tuple[2] = 0;
      return tuple;
    }
    long[] temp = gcdExt(b, a % b);
    ans = temp[0];
    tuple[0] = ans;
    tuple[1] = temp[2];
    tuple[2] = temp[1] - (a / b) * temp[2];
    return tuple;
  }

tuple中三个数分别代表方程𝑎𝑥+𝑏𝑦=𝑔𝑐𝑑(𝑎,𝑏) 中的解x,y,gcd(a,b)

好了就到这里， 如果喜欢，敬请关注区块链公众号！！疑问请留言

• 发表于 13小时前
• 阅读 ( 33 )
• 学分 ( 0 )
• 分类：以太坊