基础算法优化——Fast Modular Multiplication

1. 引言

Yuval Domb 2022年论文《Fast Modular Multiplication》

模乘可以说是任何密码系统中计算量最大的算术原语。本文提出了一种高效、硬件友好的算法，据作者所知，该算法优于迄今为止的算法。

标准的modulo-prime multiplication problem in F s \mathbb{F}_s Fs​表示为： r = a ⋅ b m o d    s \begin{equation} r=a\cdot b \mod s \end{equation} r=a⋅bmods​​ 其中 a , b , s ∈ F s a,b,s\in\mathbb{F}_s a,b,s∈Fs​， s s s为素数，并利用标准 Z \mathbb{Z} Z-algebra。 等价为： a ⋅ b = l ⋅ s + r \begin{equation} a\cdot b = l\cdot s +r \end{equation} a⋅b=l⋅s+r​​ 其中， l ∈ Z l\in \mathbb{Z} l∈Z，使得 0 ≤ r < s 0\leq r < s 0≤r