兴安盟网站建设_网站建设公司_Angular_seo优化

有限域上大整数乘法(模乘)实现过程

HMulAssign

1. 分两轮做模乘加

   • bi==0:a*bi + carry,c=a*bi

   • bi=[1~7]:a * bi + c + carry,c=a*bi + c

2. 利用模逆数做模约减

   • a*b mod N

3. 取模

DMulAssign

1. 按b的奇偶位进行

   1. 分两轮做模乘加

      • bi==0:a*bi + carry,c=a*bi

      • bi=[1~7]:a * bi + c + carry,c=a*bi + c

   2. 利用模逆数做模约减

      • a*b mod N

2. 合并奇偶位计算结果: 按顺序累加

3. 取模

有限域上大整数除法(模逆元)实现过程

除法 实现过程:

1. 除数求倒数后,再和被除数相乘
2. 求倒数过程: 通过扩展欧几里得算法(BEA), 计算大整数的模逆元.(过程中使用右移操作代替除以2)

背景知识

1. 二进制扩展欧几里得算法(BEA)

   该函数采用的是 二进制扩展欧几里得算法 (Binary Extended Euclidean Algorithm, BEA)。BEA 算法是专门为模素数域中的逆元计算而优化的一种算法。它通过反复地将两个数同时除以 2，并进行减法操作，最终得到逆元。

2. 模运算性质:在模运算中，有些特殊的性质可以利用。例如，如果 a 和 b 都是偶数，那么 gcd(a, b) = 2 * gcd(a/2, b/2)。利用这个性质，我们可以通过同时将 a 和 b 除以 2 来加速算法的收敛。

3. 辗转相减:辗转相减是求最大公约数的一种方法，大数减小数，然后把差赋值给大数, 重复, 直到两数相等时，即为最大公约数。

4. 蒙哥马利模约简: 简化和加速后续的运算, 数字x被表示为M o n t ( x ) = x ⋅ R ( mod M O D U L U S ) {Mont}(x) = x \cdot R \ (\text{mod} \ MODULUS)Mont(x)=x⋅R(modMODULUS)，其中R = 2 n R = 2^{n}R=2n，且n nn通常被选为比MODULUS大的最小的 2 的幂。

   蒙哥马利模约简是一种高效的模运算方法，特别适用于大型整数的乘法和求逆操作。它通过将数字映射到一个所谓的“蒙哥马利域”（Montgomery domain）来避免直接的模除操作，从而提高计算效率。

算法原理

• 扩展欧几里得算法： 函数的核心部分是扩展欧几里得算法。该算法用于求解不定方程 ax + by = gcd(a, b)，其中 a 和 b 是整数，x 和 y 是待求的整数。在有限域中，gcd(a, b) 通常为 1，因此方程变为 ax + by = 1。求得的 x 或 y 即为 a 或 b 的模 b 或 a 的逆元。
• 迭代求解： 函数通过不断迭代，逐步逼近逆元。在每次迭代中，将较大的数减去较小的数，并相应地调整系数。
• 结果判断： 当 u 或 v 等于 1 时，迭代结束，此时 b 或 c 即为所求的逆元。

BEA 循环

只要 u 和 v 都不是 1，就一直循环：
处理偶数:
如果 u 是偶数，则 u 和 b 都除以 2。
如果 v 是偶数，则 v 和 c 都除以 2。
在除以 2 的过程中，如果 b 或 c 变为负数，则加上模数 P.MODULUS。
比较大小并相减:
如果 v 小于 u，则 u 减去 v，b 减去 c。
否则，v 减去 u，c 减去 b。

返回结果

循环结束后，如果 u 为 1，则 b 就是 self 的模逆元。否则，c 是逆元。

往期精彩回顾:

区块链知识系列

密码学系列

零知识证明系列

共识系列

公链调研系列

BTC系列

以太坊系列

EOS系列

Filecoin系列

联盟链系列

Fabric系列

智能合约系列

Token系列