ZK-ALU-在有限域上实现乘法和除法-深圳市維司達科技有限公司

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

`HMulAssign`

分两轮做模乘加
- bi==0:a*bi + carry,c=a*bi
- bi=[1~7]:a * bi + c + carry,c=a*bi + c
利用模逆数做模约减
- a*b mod N
取模

`DMulAssign`

按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
合并奇偶位计算结果: 按顺序累加
取模

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

除法实现过程:

除数求倒数后,再和被除数相乘
求倒数过程: 通过扩展欧几里得算法(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。