2019/05/10 by Seung Gyu Hyun, Hyun, Seung Gyu, Vincent Neiger +3
Computer Science · #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1905.04356
openalex publication_date 2019/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Complexity bounds for many problems on matrices with univariate polynomial\nentries have been improved in the last few years. Still, for most related\nalgorithms, efficient implementations are not available, which leaves open the\nquestion of the practical impact of these algorithms, e.g. on applications such\nas decoding some error-correcting codes and solving polynomial systems or\nstructured linear systems. In this paper, we discuss implementation aspects for\nmost fundamental operations: multiplication, truncated inversion, approximants,\ninterpolants, kernels, linear system solving, determinant, and basis reduction.\nWe focus on prime fields with a word-size modulus, relying on Shoup's C++\nlibrary NTL. Combining these new tools to implement variants of Villard's\nalgorithm for the resultant of generic bivariate polynomials (ISSAC 2018), we\nget better performance than the state of the art for large parameters.\n