10 citations · 17 across the 6 of their papers we have counts for
8 papers · 1 filter
Fast polynomial computations with space constraints
Bruno Grenet
The works presented in this habilitation concern the algorithmics of polynomials. This is a central topic in computer algebra, with numerous applications both within and outside th…
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…
On exact division and divisibility testing for sparse polynomials
Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray
No polynomial-time algorithm is known to test whether a sparse polynomial G divides another sparse polynomial . While computing the quotient Q=F quo G can be done in polynomial…
Polynomial modular product verification and its implications
Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray
Polynomial multiplication is known to have quasi-linear complexity in both the dense and the sparse cases. Yet no truly linear algorithm has been given in any case for the problem,…
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…