站内直航

您现在的位置:首页 > 学术活动
学术报告:Factor Base Discrete Logarithms in Kummer Extensions
 

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

题目:Factor Base Discrete Logarithms in Kummer Extensions

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

时间:2015623日(星期二), 上午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.

 
版权所有 © 中国科学院信息工程研究所信息安全国家重点实验室 备案序号:京ICP备12047326-1号
电话:010-82546611 传真:010-82546564
地址:北京市海淀区闵庄路甲89号 100093