Page 387 - 《软件学报》2026年第4期

1828 软件学报 2026 年第 37 卷第 4 期

g 1 (a i ) = b i , i ∈ [1,n] (8)
然后应用扩展的欧几里得算法来实现 g 0 (x) 和 g 1 (x). 当剩余部分, 如 g(x) 为 deg ⩽ (n+k)/2 时停止. 假设现在有:


g(x) = u(x)g 0 (x)+v(x)g 1 (x)
 (9)

 g(x) = v(x) f(x)
多项式 v(x) 实际上是误差定位器多项式, 它的根包含了发生错误的所有位置 .
a i
u(x)g o (x) = v(x)( f(x)−g 1 (x)) (10)
因此令 v(x)( f(x)−g 1 (x)) = 0, 即 f(x)−g 1 (x) = 0. 用 g(x) 除以 v(x) 得到:

g(x) u(x)g 0 (x)
= +g 1 (x) (11)
v(x) v(x)
变换形式得到:


g(x) = f(x)v(x)+r(x)

(12)

 degr(x) < degv(x)
如果 r(x) = 0 并且 f(x) 满足 deg < k, 输出 f(x). 否则解码失败, 此时意味着错误超过了 (d −1)/2.
快速傅里叶变换 (fast Fourier transform, FFT): Reed-Solomon Codes 解码需要高效的算法来实现多项式的乘法、
插值等, 这些操作都可以通过快速傅里叶变换来实现.
 ∑ n−1 
 i 
 f(x) = 


 a i x 
 i=0 
  2
例如多项式  的乘积可以通过 O(n ) 的复杂度计算这个乘积的每一项的系数, 但 FFT 可以
 ∑
 n−1 
 
 g(x) = b i x 
 i 


i=0
将多项式系数表示形式变换成点值表示形式, 以 O(nlogn) 的时间复杂度来计算这个乘积.
f(x) 的
对于 n 次多项式可以代入 n 个不同的点 {x 0 ,..., x n−1 }, 得到 n 个值 {f(x 0 ),..., f(x n−1 )}. 令 f p (x) 为多项式
点值表示形式, 其点值形式表示为 {(x 0 , f(x 0 )),...,(x n−1 , f(x n−1 ))}.

fg p (x) = {(x i , f(x i )·g(x i )), i ∈ [0,n−1]} (13)
O(n ) 的复杂度计算, 如果能够在较低的时间复杂度内将系数表示法
2
于是多项式的乘法在点值表示法下可以
转化为点值表示法, 再将点值表示法转回系数表示法, 就能以较低的时间复杂度计算多项式的乘法. 证毕.
引理 2. 对于任意整数 s ⩾ 1, 存在一个足够大的常数 a, 插入所有元素项后存储的大小 S 满足 Pr(S ⩾ s) = O(n ).
−s
,
证明: 对于分布 D, 设 G(m,m,D) 表示双向图上的分布, 其中 m = (1+ε)n ε 是一个常数, 每个双向图上有 m 个
节点用 v i , i ∈ [1,m] 表示. 设 T(G) 表示 G 至少有一个循环的连接分量的数量, f(G) 为 G 中坏边的总数. Po 表示满
v
足泊松分布, 将 B(u) 定义为连接 u 到距离 i−1 的节点的边数, 假设此时包含 的连通分量的大小最多为 k. 意味着
存在一个常数 c ⩾ 1, 对于足够大的 n, 满足以下概率, 如公式 (14) 所示.

Pr( f(G(m,m,Po(λ)))−T(G(m,m,Po(λ))) ⩾ s)
 2m 
∑  ∑ ∏ ∑ ∏
  ′ ′   −j i −1
⩽ Pr   B ⩾ s+|{i : B ⩾ 1}|  ⩽ Pr(B ⩾ j i +1) = cn

 i i 
i=1
j 1 ,..., j 2m i 1 ,...,i 2m j 1 ,..., j 2m i 1 ,...,i 2m
∑ 2m ∑ 2m
i=1 j i = s j i ⩾ 1 i=1 j i = s j i ⩾ 1
2m ( ) 2m ( ) k 2m ( ) k
∑ ∑ 2m ∑ 2(1+ε)ne ∑ 2(1+ε)e
−s
−s s
s s −s−k
s
s s −s−k
⩽ c n ⩽ k c n ⩽ k c n = n c k = O(n ) (14)
s −s−|{i:j i ⩾1}|
k k k
k=1 k=1 k=1
j 1 ,..., j 2m
∑ 2m
i=1 j i = s
布谷鸟哈希表的初始化, 本文引用了 Pinkas 等人 [14] 中的实验结果, 更加详细地证明请参考 Kirsch 等人 [37] 发
stash 的大小, 随着哈希函数的数量增多, 数据元素
表的论文. 哈希表的长度取决于哈希函数的数量 k 以及暂存区
在哈希表的插入过程中可插入位置就增多, 所以哈希表的长度 b 就减小, 另一方面, 暂存区 stash 的空间越大, 可以
容纳的冲突元素就越多. 证毕.
定理 1. Π N,n,t 在半诚实场景下是安全的.
TMP-PSI