Winter数学

此crate包含STARK证明生成和验证所需的数学运算模块。

有限域

有限域模块实现了STARK友好型有限域中的算术运算。运算包括

• 基本算术运算：加法、乘法、减法、除法、求逆。
• 从域中抽取随机和伪随机元素。
• 计算给定阶的单位根。

目前，有限域有三种实现方式

• 一个128位的域，模数为2¹²⁸ - 45 * 2⁴⁰ + 1。这个域没有考虑到性能，并且大多数运算的实现效率较低。在这个域中生成的证明可以支持约100位的安全性级别。如果需要更高的安全性，必须在域的二次扩展中生成证明。
• 一个62位的域，模数为2⁶² - 111 * 2³⁹ + 1。这个域支持非常快的模运算，包括无分支的乘法和加法。为了达到足够的安全性（即约100位），必须在域的二次扩展中生成证明。对于更高的安全性级别，应使用立方扩展域。
• 一个64位的域，模数为2⁶⁴ - 2³² + 1。这个域支持非常快的模运算（与上面描述的62位域相当），提供完全常量时间的实现，并具有其他一些吸引人的特性。为了达到足够的安全性（即约100位），必须在域的二次扩展中生成证明。对于更高的安全性级别，应使用立方扩展域。

扩展域

目前，该库提供了一种通用的方法来创建支持STARK域的二次和立方扩展。这可以通过实现'ExtensibleField' trait来实现，度为2和3。

二次扩展域使用以下不可约多项式定义

• 对于 f62 域，多项式是 x² - x - 1。
• 对于 f64 域，多项式是 x² - x + 2。
• 对于 f128 域，多项式是 x² - x - 1。

三次扩展域使用以下不可约多项式定义

• 对于 f62 域，多项式是 x³ + 2x + 2。
• 对于 f64 域，多项式是 x³ - x - 1。
• 对于 f128 域，不支持三次扩展。

多项式

多项式 模块实现了基本的代数运算，如

• 在单个点对多项式进行求值。
• 从一组点对多项式进行插值（使用 Lagrange 插值）。
• 多项式的加法、乘法、减法和除法。
• 综合多项式除法（使用 Ruffini 方法）。

快速傅里叶变换

FFT 模块包含计算素数域（也称为 数论变换）中的快速傅里叶变换的操作。只要多项式的域是大小为2的幂的乘子群，就可以在 O(n log n) 时间内用于插值和求值多项式。

包功能

此包可以编译以下功能

• std - 默认启用，并依赖于 Rust 标准库。
• concurrent - 意味着 std，并使某些包函数启用多线程执行。
• no_std - 不依赖于 Rust 的标准库，并使编译到 WebAssembly 成为可能。

要使用 no_std 编译，请使用 --no-default-features 标志禁用默认功能。

并发执行

当启用 concurrent 功能进行编译时，以下操作将在多个线程中执行

• fft 模块
  • evaluate_poly()
  • evaluate_poly_with_offset()
  • interpolate_poly()
  • interpolate_poly_with_offset()
  • get_twiddles()
  • get_inv_twiddles()
• utils 模块
  • get_power_series()
  • get_power_series_with_offset()
  • add_in_place()
  • mul_acc()
  • batch_inversion()

可以通过 RAYON_NUM_THREADS 环境变量配置线程数，通常默认为机器上的逻辑核心数。

许可证

此项目是 MIT 许可。