学术报告：Factor Base Discrete Logarithms in Kummer Extensions

题目：Factor Base Discrete Logarithms in Kummer Extensions

报告人：Prof. Qi Cheng (University of Oklahoma)

时间：2015年6月23日（星期二）, 上午10:00-11:00

地点：中国科学院信息工程研究所3号楼3224室

Abstract:

The discrete logarithm over finite fields of small characteristic can be solved much more efficiently than previously thought. This algorithmic breakthrough is based on heuristic polynomial time algorithms to compute the factor base discrete logarithm, invented by Joux. In this talk, we concentrate on the Kummer extension F_(q^(2(q-1)) ). We design a new heuristic algorithm with an improved bit complexity O(q^(3.4)) (or algebraic complexity O(q^(2.4)) ) to compute the discrete logarithms of elements in a factor base of cardinality q^2. We reduce the correctness of the algorithm to a conjecture concerning the determinant of a simple (q+1)-dimensional lattice, rather than to elusive smoothness assumptions. We verify the conjecture numerically for all q's such that 〖log〗_2 q^(2(q-1))≤5000, and provide theoretical supporting evidences. This is a joint work with Dianyan Xiao and Jincheng Zhuang.

Bio:

Dr. Qi Cheng is the Williams companies foundation presidential professor in the School of Computer Science at University of Oklahoma. His main research areas are in theoretical computer science, cryptography, coding theory, computational number theory and molecular computing. He obtained his Ph.D. degree in computer science from the University of Southern California in 2001. He has published seminal papers at top journals and conferences including STOC, FOCS, CRYPTO. He is a recipient of the NSF CAREER Award in 2003, and a recipient of the distinguished paper award of ISSAC 2013.