2024-05-09

从小质数到二进制数

计算机通过将较大的数字表示为0和1的序列来进行算术运算，并在这些bit之上构建“电路”来计算加法和乘法等运算。计算机特别针对16位、32位和64位整数进行了优化。例如，2的64次方-2的32次方+1和2的31次方-1，选择它们不仅是因为它们符合这些界限，还因为它们与这些界限很吻合：可以通过执行常规的 32 位乘法来执行乘法取模 2的64次方-2的32次方+1，并在几个地方按位移位和复制输出；这个文章很好地解释了一些技巧。

然而，更好的方法是直接用二进制进行计算。如果加法可以“只是”异或，而无需担心“携带”从一个位添加1 + 1到下一个位的溢出？如果乘法可以以同样的方式更加并行化呢？这些优点都是基于能够用一个bit表示真/假值。

获取直接进行二进制计算的这些优点正是Binius试图做的。Binius团队在zkSummit的演讲中展示了效率提升：

尽管“大小”大致相同，但32位二进制字段操作比31位Mersenne字段操作所需的计算资源少5倍。