有理g-轮换阵之性质及g-轮换阵求逆的计算复杂性(英文)

摘要

本文利用本原多项式在有理数域上的不可约性及n次本原根的性质。证明了若(g,n)=1,则n阶有理g-轮换阵为可对角化矩阵。进一步利用快速富里叶变换(FFT)给出了g-轮换阵之求逆算法。算法的主要运算为FFT的计算,因此时间复杂性为O(n log n)。其中(g,n)表示整数,g,n,的最大公约数。