标题： 具有复乘的德林模块，哈塞不变量和有限域上多项式的因式分解 显示英文标题

标题： Drinfeld Modules with Complex Multiplication, Hasse Invariants and Factoring Polynomials over Finite Fields

摘要： 我们提出一种新颖的随机算法，使用具有复乘的秩$2$德林模块，在奇特征有限域$\F_q$上对多项式进行因式分解。 主要思想是相对于一个具有复乘的随机德林模块$\phi$，计算关于待分解多项式$f \in \F_q[x]$的哈塞不变量的提升。 在$\phi$处具有超奇异约化的素理想上支持的$f$的因子具有零哈塞不变量，可以与其他因子分离。 结合德林模块的德尔涅同余类比，我们设计了一个计算哈塞不变量提升的算法，这被证明是我们的算法的关键。 $n^{3/2+\varepsilon} (\log q)^{1+o(1)}+n^{1+\varepsilon} (\log q)^{2+o(1)}$的预期运行时间用于在$\F_q$上对次数为$n$的多项式进行因式分解，与已知最快的算法 Kedlaya-Umans 实现的 Kaltofen-Shoup 算法相匹配。 显示英文摘要

摘要： We present a novel randomized algorithm to factor polynomials over a finite field $\F_q$ of odd characteristic using rank $2$ Drinfeld modules with complex multiplication. The main idea is to compute a lift of the Hasse invariant (modulo the polynomial $f \in \F_q[x]$ to be factored) with respect to a random Drinfeld module $\phi$ with complex multiplication. Factors of $f$ supported on prime ideals with supersingular reduction at $\phi$ have vanishing Hasse invariant and can be separated from the rest. Incorporating a Drinfeld module analogue of Deligne's congruence, we devise an algorithm to compute the Hasse invariant lift, which turns out to be the crux of our algorithm. The resulting expected runtime of $n^{3/2+\varepsilon} (\log q)^{1+o(1)}+n^{1+\varepsilon} (\log q)^{2+o(1)}$ to factor polynomials of degree $n$ over $\F_q$ matches the fastest previously known algorithm, the Kedlaya-Umans implementation of the Kaltofen-Shoup algorithm.