4 papers
Hilbert's Nullstellensatz is in the Counting Hierarchy
Robert Andrews, Abhibhav Garg, Éric Schost
We show that Hilbert's Nullstellensatz, the problem of deciding if a system of multivariate polynomial equations has a solution in the algebraic closure of the underlying field, li…
Faster modular composition using two relation matrices
Vincent Neiger, Bruno Salvy, Éric Schost +1
Modular composition is the problem of computing the composition of two univariate polynomials modulo a third one. For a long time, the fastest algebraic algorithm for this problem…
Faster Modular Composition
Vincent Neiger, Bruno Salvy, Éric Schost +1
A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by ,…
Explicit isogenies in quadratic time in any characteristic
Luca De Feo, Cyril Hugounenq, Jérôme Plût +1
Consider two elliptic curves defined over the finite field , and suppose that there exists an isogeny between and . We propose an algorithm that de…