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

本文一共[544]字，预计阅读时长:1分钟~

mathematics
euclidean
algorithm
blockchain

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 ）.

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); }`

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) => // 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 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

版权声明：本文为[blocksight]所创，转载请带上原文链接，感谢。 https://netfreeman.com/2021/04/20210423025020377o.html

- In depth analysis of the basic components of the defi loan agreement
- 美SEC指控区块链信贷公司非法出售超3000万美元证券
- 深度 | 巴菲特在数字资产的估值中错过了什么？
- The US SEC accused blockchain credit companies of illegally selling securities exceeding US $30 million
- What did Buffett miss in the valuation of digital assets?
- Solana上的跨链生态
- 广东省税务局区块链出口退税业务成功上线
- 区块链50收评 | 成分股涨跌不一 两极分化明显
- 新闻周刊 | 以太坊主网完成伦敦升级
- Cross chain ecology on Solana
- Guangdong provincial taxation bureau successfully launched the blockchain export tax rebate business
- Blockchain 50 closing comments | component stocks did not rise or fall significantly
- Newsweek - Ethereum main network upgraded in London
- 区块链大有前途，数字货币不会消失
- Blockchain has great prospects, and digital currency will not disappear
- 区块链中很重要的10个项目
- 解析去中心化衍生品三大流派：能否撼动中心化交易所地位？
- 技术周刊｜伦敦升级后以太坊平均每分钟燃烧2.36ETH
- 数字人民币本质上不也是人民币吗，为什么说能挑战美元霸权？
- 10 important projects in the blockchain
- Analyzing the three schools of decentralized derivatives: can we shake the status of centralized exchanges?
- Techweek London upgraded Ethereum burns an average of 2.36 eth per minute
- Isn't digital RMB also RMB in essence? Why can it challenge the hegemony of the US dollar?
- Blockchain practice (II) realization of pow workload proof | 15th day of settlement
- 外媒：美国新的比特币税收计划可能扼杀更环保的区块链技术
- Foreign media: the new bitcoin tax plan in the United States may stifle more environmentally friendly blockchain technology
- 【geth】Go调用智能合约 | 一起来学区块链
- 【geth】Go语言调用以太坊 | 一起来学区块链
- [get] go invokes the smart contract | together with the school district block chain
- [get] go language calls Ethereum | together with the school district block chain
- EIP-1559实施后 Gas为什么没有剧烈下降
- Why didn't gas drop sharply after the implementation of eip-1559
- 以太坊伦敦升级已完成 矿工有哪些注意事项?
- Ethereum London upgrade has been completed. What should miners pay attention to?
- 项目周刊｜以太坊在两天内销毁了新币发行量的36%
- Project weekly Ethereum destroyed 36% of the circulation of new coins in two days
- 加密企业如何通过区块链认证绿色能源？
- How can encryption enterprises certify green energy through blockchain?
- 从SEC主席最新演讲谈数字货币行业风控
- On risk control of digital currency industry from the latest speech of SEC Chairman
- DeFi 龙头的再进化之旅：纵览 Uniswap V3 生态全景
- The re evolution journey of defi leader: an overview of uniswap V3 ecology
- 英国拍卖行佳士得拍卖 Cryptopunks、Meebits、Bored Apes NFT
- 卡尔达诺报告：在 Wave Financial Group 的支持下实现完全中心化和全球金融普惠
- NFT，开启“元宇宙”的钥匙
- 以太坊燃烧第一个24小时：中文社区在关心什么
- British auction house Christie's auctions cryptopunks, meebits, bored apes NFT
- Caldano report: complete centralization and global financial inclusion with the support of wave financial group
- NFT, the key to the "meta universe"
- Ethereum burning for the first 24 hours: what does the Chinese community care about
- 趣币早报 |美国阻止财政部挑选加密货币的赢家和输家
- Qu coin morning post | the United States prevents the treasury from selecting the winners and losers of cryptocurrency
- 区块链 公钥 私钥 生成地址 关系
- Address relationship generated by blockchain public key and private key
- 如何实现去中心化跨链消息传递和资产转移？
- 以太坊伦敦升级：随之生效的以太坊EIP-1559是什么
- Tokemak能否支配更多DeFi流动性
- How to achieve decentralized cross chain messaging and asset transfer?
- Ethereum London upgrade: what is Ethereum eip-1559 in effect
- Can tokemak dominate more defi liquidity