25 citations · 71 across the 16 of their papers we have counts for
13 papers · 1 filter
Fast interpolation and multiplication of unbalanced polynomials
Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray +1
We consider the classical problems of interpolating a polynomial given a black box for evaluation, and of multiplying two polynomials, in the setting where the bit-lengths of the c…
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…