On the Ideal Shortest Vector Problem over Random Rational Primes

：程岐（美国俄克拉荷马大学）
：2023-07-13 10:00
：海韵园数理大楼686会议室

报告人：程岐（美国俄克拉荷马大学）

时  间：2023年7月13日10:00

地  点：海韵园数理大楼686会议室

内容摘要:

Any non-zero ideal in a number field can be factored into a product of prime ideals. In this talk we report a surprising connection between the complexity of the shortest vector problem (SVP) of prime ideals in number fields and their decomposition groups. When applying the result to number fields, such as power-of-two cyclotomic fields, we show that a majority of rational primes lie under prime ideals admitting a polynomial time algorithm for SVP. This is a joint work with Yanbin Pan, Jun Xu and Nick Wadleigh.    

个人简介：

Dr. Qi Cheng joined the faculty of the University of Oklahoma in 2001, where he is now a Presidential Professor in the School of Computer Science. He received the B.S. degree from Nankai University, the M.S. degree from Fudan University, and the Ph.D. degree in computer science from the University of Southern California. His research interests include theoretical computer science and computational number theory. He was the principle investigator of several NSF grants including a CAREER award. He won the Distinguished Paper Award at the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2013. He published many papers in prestigious journals and conferences such as STOC, FOCS, SODA, Crypto, Eurocrypt, IEEE Transaction on Information Theory and SIAM journal on computing.

 

联系人：祝辉林