区块链中的数学（一）

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

// 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)
好了就到这里，如果喜欢，敬请关注区块链公众号！！疑问请留言