报告题目：再论序列的极小有理分式表达的算法问题

报告时间：2021年12月21日2:00-3:00pm

报告地点：淦昌苑D座320会议室

摘要：Given a binary sequence with a bit length of n, determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream cipher. In Crypto’95, Klapper and Goresky firstly introduced this problem and presented an adaptive rational approximation algorithm with a time complexity of O(n2 log n loglog n). In this talk, we will revisit the currently efficient algorithms for this problem and introduce our recently new advances. Firstly, we find a general and precise recursive relationship between the minimal bases for two adjacent lattices generated by successive truncation sequences. This enables us to improve the currently fastest adaptive algorithm proposed by Li et al. in DCC 2019. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we obtain a non-adaptive yet practically faster MRFR solving algorithm named global Euclidean algorithm. Thirdly, we identify theoretical flaws on some non-adaptive methods proposed in IEEE TIT 2004 and IEEE TIT 2008 by counter-examples and correct the problems by designing modified Euclidean algorithm named partial Euclidean algorithm. Meanwhile, we further reduce the time complexity from O(n2) to O(n log2n loglog n).  Also, we will show our comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis.

报告人简介：田呈亮，博士，青岛大学计算机科学技术学院副教授、校青年卓越人才。目前主要从事格密码学以及云/边缘/智能计算中隐私保护问题研究，主持国家自然科学青年基金、 “十三五”国家密码发展基金、山东省自然科学基金青年项目等科研项目多项，以第一（通讯）作者在IEEE TIT，IEEE TSC，Information Sciences, Science China:Information Sciences等国内外高水平计算机科学期刊发表论文十余篇。

邀请人：许光午

审核人：王美琴