题目：On the probability of generating a primitive matrix

报告人：陈经纬

时间：2023年3月16日（周四）16:00-16:45

地点：腾讯会议

报告人简介：陈经纬，中国科学院重庆绿色智能技术研究院副研究员，法国国家科研中心（CNRS）并行计算实验室（LIP）、加拿大菲尔兹（Fields）研究所访问学者，中科院青年促进会会员，入选中科院“西部之光”计划。主要从事格的理论、算法与应用研究，尤其是与基于格的密码学相关的方向，主持或参与国家重点研发计划、国家自然科学基金、重庆市自然科学基金、贵州省科技支撑计划等科研项目10余项，发表在Math. Comput., Sci. China, ISSAC等期刊或会议上的论文二十余篇。

摘要：Given a k × n integer primitive matrix A (i.e., a matrix can be extended to an n × n unimodular matrix over the integers) with the maximal absolute value of entries ∥A∥ bounded by an integer λ from above, we consider the probability that the m× n matrix extended from A by appending other m − k row vectors of dimension n with entries chosen randomly and independently from the uniform distribution over {0, 1, . . . , λ−1} is still primitive. In this talk, we will report that the probability is at least a constant for fixed m in the range [k+1, n−4]. As an application, we will prove that there exists a fast Las Vegas algorithm that completes a k × n primitive matrix A to an n × n unimodular matrix within expected \tilde{O} (n^ω log ∥A∥) bit operations, where \tilde{O} is big-O but without log factors, ω is the exponent on the arithmetic operations of matrix multiplication. This talk is based on a joint work with Yong Feng, Yang Liu and Wenyuan Wu.

邀请人：黄巧龙