Microsoft SEAL中dwthandler.h解析

提供了一个接口，用于执行快速离散加权变换 (DWT) 及其逆变换，这些变换用于加速多项式乘法，将多个消息批量处理成一个明文多项式。这个类模板专门用于整数商环上DWT的整数模算法，并用于多项式乘法和BatchEncoder。在复数域上的 DWT 使用双精度复数运算进行专门化，这在 CKKSEncoder 中使用。

离散加权变换 (DWT) 是离散傅里叶变换 (DFT) 在任意环上的一种变体，它在变换输入之前，通过与一个权重向量进行逐元素相乘来加权输入，然后再用另一个向量加权输出。DWT 可用于执行负循环卷积，就像 DFT 可用于执行循环卷积一样。大小为 n 的 DFT 需要一个原始 n 次单位根，而用于负循环卷积的 DWT 需要一个原始 2n 次单位根 ψ。在正向 DWT 中，输入与 ψ 的递增幂逐元素相乘，正向 DFT 变换使用 2n 次原始单位根 ψ²，输出则不加权。在反向 DWT 中，输入不加权，反向 DFT 变换使用 2n 次原始单位根 ψ⁻²，输出与 ψ⁻¹ 的递增幂逐元素相乘。

快速傅里叶变换是一种计算 DFT 或其逆变换的算法。Cooley-Tukey FFT 将 DFT 的复杂度从 O(n²) 降低到 O(n log n)。DFT 可以解释为在原始 n 次单位根的递增幂处评估一个 (n-1) 次多项式，这可以通过 FFT 算法加速。DWT 评估原始 2n 次单位根的递增奇数幂，也可以通过本类实现的类似 FFT 的算法加速。

本类中实现的算法基于 Patrick Longa 和 Michael Naehrig 的论文 (https://eprint.iacr.org/2016/504.pdf) 中的算法 1 和 2，并进行了三处修改。首先，我们在本类中将算法推广到任意环上的 DWT。其次，IDWT 使用的 ψ⁻¹ 的幂以一种乱序方式存储（与论文中的位反转顺序相对），以实现内存访问的合并。第三，IDWT 中的 1/n 乘法被合并到最后一轮迭代中，节省了 n/2 次乘法。最后，我们展开循环以实现对输入和输出向量的内存访问合并。在早期版本的 SEAL 中，1/n 的乘法通过在所有迭代中合并 1/2 的乘法来完成，这在 CPU 上比当前方法慢，但在某些硬件架构上更高效。

IDWT 使用的 ψ⁻¹ 的幂的存储顺序不自然但高效：第 i 个槽存储 ψ⁻¹ 的 (reverse_bits(i - 1, log_n) + 1) 次幂。

transform_to_rev

执行原地快速乘以 DWT 矩阵的操作。 对单位根幂的访问是合并的。 如果不展开循环，对值的访问则不会合并。

@param[values] 正常顺序的输入，输出为位反转顺序

@param[log_n] DWT 大小的以 2 为底的对数

@param[roots] 位反转顺序的单位根幂

@param[scalar] 一个可选的标量，将乘以所有输出值

transform_from_rev

执行原地快速乘以 DWT 矩阵的操作。 对单位根幂的访问是合并的。 如果不展开循环，对值的访问则不会合并。

@param[values] 位反转顺序的输入，正常顺序的输出

@param[roots] 乱序的单位根幂

@param[scalar] 一个可选的标量，将乘以所有输出值