108 citations · 310 across the 26 of their papers we have counts for
18 papers · 1 filter
Random primes without primality testing
Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray +1
Numerous algorithms call for computation over the integers modulo a randomly-chosen large prime. In some cases, the quasi-cubic complexity of selecting a random prime can dominate…
Sparse Polynomial Interpolation and Division in Soft-linear Time
Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray +1
Given a way to evaluate an unknown polynomial with integer coefficients, we present new algorithms to recover its nonzero coefficients and corresponding exponents. As an applicatio…
Fast In-place Algorithms for Polynomial Operations: Division, Evaluation, Interpolation
Pascal Giorgi, Bruno Grenet, Daniel S. Roche
We consider space-saving versions of several important operations on univariate polynomials, namely power series inversion and division, division with remainder, multi-point evalua…
Generic reductions for in-place polynomial multiplication
Pascal Giorgi, Bruno Grenet, Daniel Roche
The polynomial multiplication problem has attracted considerable attention since the early days of computer algebra, and several algorithms have been designed to achieve the best p…
LU factorization with errors *
Jean-Guillaume Dumas, Joris Van Der Hoeven, Clément Pernet +1
We present new algorithms to detect and correct errors in the lower-upper factorization of a matrix, or the triangular linear system solution, over an arbitrary field. Our main alg…
What Can (and Can't) we Do with Sparse Polynomials?
Daniel S. Roche
Simply put, a sparse polynomial is one whose zero coefficients are not explicitly stored. Such objects are ubiquitous in exact computing, and so naturally we would like to have eff…