43、有限域算法与确定性素性测试

有限域算法与确定性素性测试

1. 多项式因式分解相关内容

在有限域上进行多项式因式分解是一个重要的研究领域，涉及到多个算法和相关练习，以提升分解效率。

1.1 分离集与多项式因式分解

给定特定条件，集合 $S := {rep(\alpha_i) : 0 \leq i \leq k - 1}$ 是多项式 $g$ 在域 $F$ 上的分离集，可通过确定性方法计算，在域 $E$ 中需 $O(k^2 + k len(q))$ 次运算，在域 $F$ 中需 $O(k^2\ell^2 + k\ell^2 len(q))$ 次运算。

相关练习包括：
-练习 21.17：将之前的方法与算法 DDF 结合，设计一个在有限域 $F$ 上因式分解多项式的确定性算法，其运行时间最多为输入长度的多项式乘以 $p$，并仔细估算该算法的运行时间。
-练习 21.18：当素数 $p$ 为奇数时，利用特定性质（对于所有整数 $a, b$，若 $a \not\equiv b (\bmod p)$，则存在非负整数 $i \leq p^{1/2} \log_2 p$ 使得 $(a + i | p) \neq (b + i | p)$），设计并分析一个在有限域 $F$ 上因式分解多项式的确定性算法，其运行时间最多为输入长度的多项式乘以 $p^{1/2}$。
-练习 21.19：若 $S = {\lambda_1, \ldots, \lambda_s}$ 是多项式 $g$ 在 $\mathbb{Z}_p$ 上的分离集，$\varphi_u \in F