2019年杏盛學術前沿講座（17）
主 講 人：韓永祥 教授 東莞理工學院
主題名稱：A Novel Polynomial basis and Fast Fourier Transform for Finite Fields
簡要內容👧🏻：Finding an n-point Fast Fourier Transform (FFT) algorithm over an arbitrary finite field with additive and multiplicative complexity O(n log(n)) has been a long standing open problem in the coding area. It has been known for a long time that a better FFT algorithm can improve the encoding and decoding complexity of Reed-Solomon (RS) codes, one of the most popular codes in the world. Even though an FFT algorithm over a complexity field with additive and multiplicative complexity O(n log(n)) was invented decades ago, it remains unknown whether such an algorithm exists over finite fields. In this talk, we present the first FFT algorithm over finite fields with additive and multiplicative complexity O(n log(n)). A new basis of polynomial over finite fields is invented and then apply it to the FFT over finite fields. The proposed polynomial basis allows that n-point FFT can be computed in O(n log(n)) finite field operations with extremely small leading constant. Based on this novel FFT algorithm, we then develop the encoding algorithms for the (n=2r,k) Reed-Solomon codes. Thanks to the efficiency of transform based on the polynomial basis, the encoding can be completed in O(n log2(k)) or O(n log2(n-k) finite field operations. As the complexity of leading factor is small, the algorithms are advantageous in practical applications such as encoding/decoding of Reed-Solomon codes and polynomial multiplications in cryptography.
時間地點：
主辦學院：信息工程學院
杏盛娱乐
2019.4.24