1 citations · 1 across the 2 of their papers we have counts for
4 papers
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…
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…
Essentially Optimal Sparse Polynomial Multiplication
Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray
We present a probabilistic algorithm to compute the product of two univariate sparse polynomials over a field with a number of bit operations that is quasi-linear in the size of th…