报告题目：

Fast Fourier Transform for Finite Fields and Its Applications to Reed-Solomon Codes

报告时间：2026年4月23日 10：00

报告地点：大连理工大学开发区校区综合楼第二会议室

报告人：Yunghsiang Sam Han （韩永祥）

报告内容（摘要）：

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 longstanding open problem in the coding area. It has long been known that a more efficient FFT algorithm can reduce the encoding and decoding complexity of Reed-Solomon (RS) codes, one of the most widely used 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 polynomials over finite fields is invented and then applied to the FFT over finite fields. The proposed polynomial basis allows that an n-point FFT can be computed in O(n log(n)) finite field operations with extremely small leading constants. Based on this novel FFT algorithm, we then develop 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 log2(k)) or O(n log2(n − k) finite field operations. For the erasure decoding, O(n log2(n)) algorithm has been designed; for error decoding, O((n−k)log2 (n−k)) or O((n−k)^2) algorithm has been developed. Because the complexity of the leading factor is low, these algorithms are advantageous in practical applications, such as Reed-Solomon code encoding/decoding and polynomial multiplication in cryptography. The Reed-Solomon code encoding and erasure-decoding algorithms have been implemented in many products by Google and Huawei.

报告人简介：

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

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

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

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