用于线性化多项式快速处理的傅里叶变换实现方法
知识产权简介
本发明针对现有技术中线性化多项式在有限域上的批量求值与系数恢复效率有限的问题,提出了一种面向线性化多项式的快速傅里叶变换与逆变换方法。通过该方法,批量求值与系数恢复的计算复杂度可降低至O(nlogn)量级,显著优于传统方法的复杂度上限,提升了运算效率与可扩展性。
转化前景
本发明针对现有技术中线性化多项式在有限域上的批量求值与系数恢复效率有限的问题,提出了一种面向线性化多项式的快速傅里叶变换与逆变换方法。具该方法通过构造类快速傅里叶变换与类逆快速傅里叶变换的递归规约结构,实现了对q-线性化多项式在有限域上的批量求值与系数恢复的高效计算。该方法适用于一类具有特殊结构的取值点集合,可将q-度数为n的问题逐步规约为规模更小的子问题,并最终完成整体运算。通过该方法,批量求值与系数恢复的计算复杂度可降低至O(n logn )量级,显著优于传统方法的复杂度上限,提升了运算效率与可扩展性。