25 citations · 71 across the 16 of their papers we have counts for
18 papers
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…
Random primes in arithmetic progressions
Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray +1
We describe a straightforward method to generate a random prime q such that the multiplicative group GF(q)* also has a random large prime-order subgroup. The described algorithm al…
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,…