有限域上大整数乘法(模乘)实现过程
HMulAssign
分两轮做模乘加
bi==0:
a*bi + carry,c=a*bibi=[1~7]:
a * bi + c + carry,c=a*bi + c
利用模逆数做模约减
a*b mod N
取模
DMulAssign
按b的奇偶位进行
分两轮做模乘加
bi==0:
a*bi + carry,c=a*bibi=[1~7]:
a * bi + c + carry,c=a*bi + c
利用模逆数做模约减
a*b mod N
合并奇偶位计算结果: 按顺序累加
取模
有限域上大整数除法(模逆元)实现过程
除法 实现过程:
- 除数求倒数后,再和被除数相乘
- 求倒数过程: 通过扩展欧几里得算法(BEA), 计算大整数的模逆元.(过程中使用右移操作代替除以2)
背景知识
二进制扩展欧几里得算法(BEA)
该函数采用的是 二进制扩展欧几里得算法 (Binary Extended Euclidean Algorithm, BEA)。BEA 算法是专门为模素数域中的逆元计算而优化的一种算法。它通过反复地将两个数同时除以 2，并进行减法操作，最终得到逆元。
模运算性质:在模运算中，有些特殊的性质可以利用。例如，如果 a 和 b 都是偶数，那么 gcd(a, b) = 2 * gcd(a/2, b/2)。利用这个性质，我们可以通过同时将 a 和 b 除以 2 来加速算法的收敛。
辗转相减:辗转相减是求最大公约数的一种方法，大数减小数，然后把差赋值给大数, 重复, 直到两数相等时，即为最大公约数。
蒙哥马利模约简: 简化和加速后续的运算, 数字
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系列
