用于线性化多项式快速处理的傅里叶变换实现方法

  • 国民经济行业:信息传输、软件和信息技术服务业/互联网和相关服务/其他互联网服务
  • 学科类别:信息科学与系统科学/信息科学与系统科学基础学科/信息科学与系统科学基础学科其他学科
  • 权利人:上海交通大学

知识产权简介

本发明针对现有技术中线性化多项式在有限域上的批量求值与系数恢复效率有限的问题,提出了一种面向线性化多项式的快速傅里叶变换与逆变换方法。通过该方法,批量求值与系数恢复的计算复杂度可降低至O(nlogn)量级,显著优于传统方法的复杂度上限,提升了运算效率与可扩展性。

转化前景

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

基本信息

权利人 上海交通大学
知识产权类型 专利
意向合作模式
预估金额
联系合作