15 citations · 111 across the 23 of their papers we have counts for
3 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…
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…