有限域的Fast Multiplication和Modular Reduction算法实现

1. 引言

关于有限域的基础知识，可参考：

RISC Zero团队2022年11月视频 Intro to Finite Fields: RISC Zero Study Club

有限域几乎是密码学中所有数学的基础。
ZKP证明系统中的所有运算都是基于有限域的：

使用布尔运算的数字电路：如AND、OR、NOT。
使用有限域运算的算术电路：如addition、multiplication、negation。

但是，真实的计算机没有有限域电路装置，只有：

ADD rax, rbx
MUL rax
SHR rax, CL
等等

因此，需基于以上运算来构建有限域运算。
有限域运算的速度很关键，原因在于：

影响ZKP可用性的最大障碍在于证明开销。
几乎所有的证明时间都用于有限域运算了。为提升ZKP证明速度：
- 减少有限域运算次数（如，更高效的NTT或MSM算法）
- 让有限域运算更高效（如，使用优化的有限域表示）

本文主要关注内容有：

BigInts
BigInts经典加法运算
BigInts经典乘法运算
Modular reduction（Barrett算法）：当无法更改数字表示时，最有用。
Montgomery form
Multiplication and reduction（Montgomery算法）：最常用算法。
其它multiplication算法

并对大整数乘法运算的经典算法、Barrett算法、Montgomery算法进行了对比：
在这里插入图片描述

2. 大整数及其加法和乘法运算

大整数，又名BigInt或Multiprecision Integers。
真实计算机的运算符是基于word的：

几乎所有的现代计算机都使用64-bit words
但32-bit words并未完全过时。比如在IoT世界。

对于更大（如256位）的域，会将其切分为words来表示：

如，通常以4个64-bit word来表示256-bit数字。
如十进制的8位数字，可以4个2-digit word来表示。

如以100进制的digit来表示大整数27311837，对应为：
$27\ 31\ 18\ 37)_{100}$ 。

2.1 大整数经典加法运算

对应的大整数加法运算，如 $27\ 31\ 18\ 37)_{100} + (88\ 68\ 97\ 89)_{100}$ ，计算规则为：
在这里插入图片描述
具体见Handbook of Elliptic and Hyperelliptic Curve Cryptography书本中的Algorithm 10.3算法：

2.2 大整数经典乘法运算

以 $54\ 12)_{100}*(36\ 29)_{100}$ 大整数乘法运算为例，具体见Handbook of Elliptic and Hyperelliptic Curve Cryptography书本中的Algorithm 10.8算法：
在这里插入图片描述
对应各个step的计算数据为：

3. Modular Reduction

需注意，以上加法和乘法运算结果均为更大的值，需将这些大的结果值reduce为相应的canonical表示，如：
在这里插入图片描述
常见的Modular Reduction算法有：

1）Barret reduction算法：当无法更改数字表示时，最有用。
2）Montgomery multiplication and reduction算法：最常用算法。

3.1 Barret reduction算法

做reduction最明显的方式是做除法，但除法运算昂贵，且可能不是constant time的。以single-word除法运算 $b=1，R=2^k$ 为例：

func reduce(a uint) uint {
    q:= a / n  // Division implicitly returns the floor of the result.
    return a - q * n
}

非constant time会存在timing attack攻击问题。
Barrett reduction为将 $1/ n$ 近似为 $m/2^k$ ，因为 $m/2^k$ 中的除法实际是右移运算，要便宜得多。【可近似计算 $m$ 值为 $m=\left \lfloor 2^k/n\right \rfloor$ 】

func reduce(a uint) uint {
    q := (a * m) >> k // ">> k" denotes bitshift by k.
    return a - q * n
}

不过这样reduce之后的结果在 $[0, 2 n)$ ，而不是 $[0, n)$ ，因此需进一步reduce：

func reduce(a uint) uint {
    q := (a * m) >> k
    a -= q * n
    if a >= n {
        a -= n
    }
    return a
}

Handbook of Elliptic and Hyperelliptic Curve Cryptography书本中的Algorithm 10.17算法，将其扩展为了multi-word Barrett Reduction算法，且在以上最后一步reduce之前的结果不再是 $[0, 2 n)$ 而是可能更大的范围值，因此在Algorithm 10.17算法中第4步采用的是while：
在这里插入图片描述

3.2 Montgomery multiplication and reduction算法

Montgomery Form为另一种有限域表示，其支持快速combined multiplication and reduction算法。

之前将有限域元素表示为：
$x\in [0,N-1]$

而Montgomery Form表示定义为：
$[x]=(xR)\mod N$

Montgomery Reduction算法计算的是：
$REDC(u)=(uR^{-1})\mod N$
而不是之前Barrett Reduction计算的 $u\mod N$ 。

$RE D C$ 是一个非常多功能的公式：

1）将经典转换为Montgomery： $x]=REDC((xR^2)\mod N)$
2）将Montgomery转换为经典： $RE D C ([x]) = x$
3）对Montgomery Form表示的乘法运算： $xR\mod p)*(yR\mod p)*R^{-1}\mod p)=(xyR)\mod p$ ，对应在Handbook of Elliptic and Hyperelliptic Curve Cryptography书本中的Algorithm 11.3算法中做了相应实现：