讲座题目：A Novel Polynomial basis and Fast Fourier Transform for Finite Fields

讲座人：韩永祥 教授

讲座时间：2019年5月23（周四） 13:00-14:30

讲座地点：信息楼246

讲座内容简介：

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=2^r,k) Reed-Solomon codes. Thanks to the efficiency of transform based on the polynomial basis, the encoding can be completed in O(n log₂(k)) or O(n log₂(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.

讲座人简介：

韩永祥博士1984年毕业于台湾清华大学电机工程学系并于1986年于同系取得硕士学位。1993年韩博士于纽约州雪城大学获得计算机与信息科学博士。他曾于华梵人文科技学院，暨南国际大学，以及台北大学任教。从2010年8月起，他任教于台湾科技大学电机工程系并于2011年6月起荣任学校讲座教授。台湾科技大学退休后，目前他是东莞理工学院杰出人才特聘教授。

韩博士的研究兴趣主要是在纠错码，无线网络和信息安全。韩博士已从事最先进的纠错码译码研究超过29年。29年前他首先开发了基于A *算法的连续型译码算法。当时，该算法吸引了大量的关注，因为它是对二进制线性分组码最有效的最大似然软判决译码算法。此译码算法已被收录于纠错码的经典教科书中。

韩博士还成功地应用编码理论于无线传感器网络的研究领域。他已出版几个关于无线传感器网络研究的高被引用着作。其中一篇关于随机密钥预分配方案着作被引用超过两千次。他还担任多个国际学术刊物的编辑。

韩博士是1994年雪城大学博士论文奖得主，同时也是IEEE院士。2013年他的一个论文赢得了久负盛名的ACM CCS Test of Time奖。此奖项为  ACM 信息安全领域的年度最有影响力论文奖。

欢迎广大师生参加！