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

区块链技术 14 4 月 22, 2024 0 区块链315

本节主要讲欧几里得算法及其扩展算法。

## 介绍前面说过密码学是区块链的基石，没有密码学技术，区块链就是空中楼阁，也难以存在。那么密码学的基石是什么？答案是数学。从这一篇起始，将会由浅入深的介绍一些密码学中常用的数学知识。本节主要讲欧几里得算法及其扩展算法。其应用会在之后文章中体现（当然，如果已经有研究过的朋友应该已经知晓）。 ## 欧几里得算法欧几里得算法是指：对于任意的非负整数?和正整数?，求这两个数的最大公因数，记为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) 欢迎关注公众号：blocksight

介绍

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

欧几里得算法

欧几里得算法是指：对于任意的非负整数?和正整数?，求这两个数的最大公因数，记为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)

欢迎关注公众号：blocksight

区块链技术网。