fft - 使用 FFT 为 Shamir Secret Share 加速 Berlekamp Welch 算法

Question

我相信只要 $t<n/3$ 就可以使用 Berlekamp Welch 算法使用 Shamir Secret Share 正确构造秘密。我们如何使用快速傅里叶变换加速 BW 算法的实现？

score 1 · Accepted Answer

Berlekamp Welch 用于纠正 Reed Solomon 码的原始编码方案的错误，其中存在编码器和解码器已知的一组固定数据点，以及解码器未知的基于要传输的消息的多项式。这种方法主要被切换到 BCH 类型代码所取代，其中使用编码器和解码器都知道的固定多项式。

Berlekamp Welch 对时间复杂度为 O(n^3) 的矩阵求逆。高对此进行了改进，基于扩展欧几里得算法将时间复杂度降低到 O(n^2)。请注意，R[-1] 产品系列是基于固定的数据点集预先计算的，以实现 O(n^2) 时间复杂度。链接到“原始视图”解码器的 Wiki 部分。

Discreet Fourier 本质上与编码过程相同，只是对用于编码的固定数据点有一个约束（它们需要是场基元的连续幂）才能使逆变换起作用。逆变换仅在接收到的数据没有错误时才起作用。拉格朗日插值对数据点没有约束，也不需要接收到的数据无误。Wiki 对此也有一个部分：

1 回答 1