. .. Vanilla-gröbner-bases, , p.90

. .. Vanilla-gröbner-stairs,

. .. Vanilla-gröbner-bases, 93 7.2 Terse representations of vanilla Gröbner bases

. .. Applications, 100 7.4.1 Multiplications in the quotient algebra

, The results in this chapter were published in [HL18a]. A proof-of-concept Pour nir, on peut mentionner les résultats de ces dernières années sur le sujet

, HH19a] ont amélioré la complexité de la multiplication entière à O

, été établie également pour les polynômes sur les corps nis. Très récemment, Harvey et van der Hoeven ont prouvé que la multiplication avait une complexité de O(n log n), aussi bien pour les entiers

, Schönhage et Strassen avaient conjecturé qu'il n'est pas possible de descendre en dessous de n log n. Cette borne inférieure n'a pas encore été prouvée, mais elle est largement admise. Rappelons toutefois que l'algorithme naïf (quadratique) était initialement considéré optimal, à tort ; une preuve serait donc nécessaire pour apporter une réponse dénitive

R. Larrieu, The Truncated Fourier Transform for mixed radices, Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC '17, p.261268, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01419442

R. Joris-van-der-hoeven and . Larrieu, The Frobenius FFT, Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC '17, p.437444, 2017.

R. Joris-van-der-hoeven, G. Larrieu, and . Lecerf, Implementing fast carryless multiplication, Proceedings of Mathematical Aspects of Computer and Information Sciences, p.121136, 2017.

R. Joris-van-der-hoeven and . Larrieu, Fast reduction of bivariate polynomials with respect to suciently regular Gröbner bases, Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC '18, 2018.

R. Joris-van-der-hoeven and . Larrieu, Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals. Applicable Algebra in Engineering, 2019.

R. Larrieu, Computing generic bivariate Gröbner bases with Mathemagix, 2019.

, Logiciels ? Routines pour la multiplication de polynômes dans F 2 [X] (voir [HLL17]), en collaboration avec Grégoire Lecerf et Joris van der Hoeven

, Une implémentation preuve-de-concept pour SageMath [Sag17] des algorithmes pour les bases de Gröbner bivariées génériques

, Une bibliothèque ecace pour le calcul des bases de Gröbner bivariées génériques dans le contexte de

, Une implémentation expérimentale pour le calcul avec des extensions de corps nis, en collaboration avec Luca De Feo. Disponible à l'adresse suivante

, La méthode et des résultats provisoires sont donnés en Annexe A. Bibliography

N. H. and A. , Mémoire sur les équations algébriques, où l'on démontre l'impossibilité de la résolution de l'équation générales du cinquième degré (1824), Oeuvres Complètes de Niels Henrik Abel: Nouvelle Édition, vol.1, 2012.

E. L. Allgower and K. Georg, Numerical Continuation Methods: An Introduction, 1990.

L. Auslander, J. R. Johnson, and R. W. Johnson, An equivariant Fast Fourier Transform algorithm, 1996.

B. Allombert, Explicit computation of isomorphisms between nite elds

, Finite Fields and Their Applications, vol.8, issue.3, pp.332-342, 2002.

P. Aubry, D. Lazard, and M. Maza, On the theories of triangular sets, Journal of Symbolic Computation, vol.28, issue.1, p.105124, 1999.
URL : https://hal.archives-ouvertes.fr/hal-01148870

P. Aubry and M. Moreno-maza, Triangular sets for solving polynomial systems: a comparative implementation of four methods, Journal of Symbolic Computation, vol.28, issue.1, pp.125-154, 1999.
URL : https://hal.archives-ouvertes.fr/hal-01148862

W. Auzinger and H. J. Stetter, An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations

I. Ravi, P. Agarwal, Y. M. Chow, and S. J. Wilson, Proceedings of the International Conference on Numerical Mathematics, p.1130, 1988.

D. H. Bailey, FFTs in external or hierarchical memory, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.234242

A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf et al., Algorithmes Ecaces en Calcul Formel. Frédéric Chyzak (auto-édit, vol.686, 2017.

W. Bosma, J. Cannon, and C. Playoust, The Magma algebra system. I. The user language, Computational algebra and number theory, vol.24, p.235265, 1993.

W. Bosma, J. Cannon, and A. Steel, Lattices of compatibly embedded nite elds, Journal of Symbolic Computation, vol.24, issue.3, pp.351-369, 1997.

L. +-17]-ludovic-brieulle, J. De-feo, J. Doliskani, É. Flori, and . Schost, Computing isomorphisms and embeddings of nite elds, 2017.

L. +-19]-ludovic-brieulle, J. De-feo, J. Doliskani, É. Flori, and . Schost, Computing isomorphisms and embeddings of nite elds, Mathematics of Computation, vol.88, issue.317, p.13911426, 2019.

J. Bezanson, A. Edelman, S. Karpinski, and . Shah, Julia: A fresh approach to numerical computing, SIAM Review, vol.59, issue.1, p.6598, 2017.

G. D. Bergland, Numerical Analysis: A fast Fourier transform algorithm for real-valued series, Communications of the ACM, vol.11, issue.10, p.703710, 1968.

D. J. Bernstein, Scaled remainder trees, 2004.

R. Bergmann, The fast Fourier transform and fast wavelet transform for patterns on the torus, Applied and Computational Harmonic Analysis, vol.35, issue.1, p.3951, 2013.

M. Bardet, J. Faugère, and B. Salvy, On the complexity of the F5 Gröbner basis algorithm, Journal of Symbolic Computation, p.124, 2014.

R. P. Brent and P. Gaudry, Emmanuel Thomé, and Paul Zimmermann. Faster multiplication in GF

, Algorithmic Number Theory, vol.5011, p.153166, 2008.

D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler, Bertini: Software for numerical algebraic geometry, 2006.

P. Richard, . Brent, T. Hsiang, and . Kung, Fast algorithms for manipulating formal power series, Journal of the ACM (JACM), vol.25, issue.4, p.581595, 1978.

E. Brieskorn and H. Knörrer, Plane Algebraic Curves, 2012.

D. Blessenohl, On the normal basis theorem, Note di Matematica, vol.27, issue.1, p.510, 2007.

. +-16]-yacine, S. Bouzidi, G. Lazard, M. Moroz, F. Pouget et al., Solving bivariate systems using rational univariate representations, Journal of Complexity, vol.37, pp.34-75, 2016.

A. Bostan, G. Lecerf, and É. Schost, Tellegen's principle into practice, Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, ISSAC '03, p.3744, 2003.

L. Bluestein, A linear ltering approach to the computation of discrete Fourier transform, IEEE Transactions on Audio and Electroacoustics, vol.18, issue.4, p.451455, 1970.

J. L. Bordewijk, Inter-reciprocity applied to electrical networks, Applied Scientic Research, Section A, vol.6, issue.1, p.174, 1957.

D. Bayer and M. Stillman, On the complexity of computing syzygies, Journal of Symbolic Computation, vol.6, issue.2-3, p.135147, 1988.

A. Bostan and É. Schost, On the complexities of multipoint evaluation and interpolation, Theoretical Computer Science, vol.329, issue.1, pp.223-235, 2004.

A. Bostan and É. Schost, Polynomial evaluation and interpolation on special sets of points, Journal of Complexity, vol.21, issue.4, pp.420-446, 2005.

A. Bostan, B. Salvy, and É. Schost, Fast algorithms for zerodimensional polynomial systems using duality. Applicable Algebra in Engineering, Communication and Computing, vol.14, issue.4, p.239272, 2003.
URL : https://hal.archives-ouvertes.fr/inria-00072296

B. Buchberger, Ein Algorithmus zum Aunden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal, 1965.

B. Buchberger, A criterion for detecting unnecessary reductions in the construction of Gröbner-bases, Symbolic and Algebraic Computation, p.321, 1979.

T. Becker and V. Weispfenning, Gröbner bases: a computational approach to commutative algebra, volume 141 of Graduate Texts in Mathematics, 1993.

A. Stephen, . Cook, O. Stål, and . Aanderaa, On the minimum computation time of functions, Transactions of the American Mathematical Society, vol.142, p.291314, 1969.

C. The and . Team, CADO-NFS, an implementation of the number eld sieve algorithm, 2017.

D. G. Cantor, On arithmetical algorithms over nite elds, Journal of Combinatorial Theory, Series A, vol.50, issue.2, pp.285-300, 1989.

M. Chen, C. Cheng, P. Kuo, W. Li, and B. Yang, Faster multiplication for long binary polynomials, CCK + 17, 2017.

M. Chen, C. Cheng, P. Kuo, W. Li, and B. Yang, Multiplying boolean polynomials with Frobenius partitions in additive fast Fourier transform, CCK + 18, 2018.

R. Crandall and B. Fagin, Discrete weighted transforms and large-integer arithmetic, Mathematics of computation, vol.62, issue.205, p.305324, 1994.

G. David, E. Cantor, and . Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, vol.28, issue.7, p.693701, 1991.

S. Collart, M. Kalkbrener, and D. Mall, Converting bases with the Gröbner walk, Journal of Symbolic Computation, vol.24, issue.3, pp.465-469, 1997.

D. Cox, J. Little, and D. Shea, Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra, Undergraduate Texts in Mathematics, 1992.

J. Couveignes, Isomorphisms between Artin-Schreier towers. Mathematics of Computation, vol.69, p.16251631, 2000.

J. W. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Mathematics of computation, vol.19, issue.90, p.301, 1965.

S. Covanov and E. Thomé, Fast integer multiplication using generalized Fermat primes, Mathematics of Computation, vol.88, issue.317, p.14491477, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01108166

J. Luca-de-feo, É. Doliskani, and . Schost, Fast algorithms for -adic towers over nite elds, Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, p.165172, 2013.

J. Luca-de-feo, É. Doliskani, and . Schost, Fast arithmetic for the algebraic closure of nite elds, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, p.122129, 2014.

D. I. Diochnos, Z. Ioannis, E. P. Emiris, and . Tsigaridas, On the asymptotic and practical complexity of solving bivariate systems over the reals, International Symposium on Symbolic and Algebraic Computation, vol.44, p.818, 2009.

W. Decker, G. Greuel, G. Pster, and H. Schönemann, Singular 4-1-0 A computer algebra system for polynomial computations, 2017.

F. Drexler, Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen, Numerische Mathematik, vol.29, issue.1, p.4558, 1977.

H. Luca-de-feo, É. Randriam, and . Rousseau, Standard lattices of compatibly embedded nite elds, Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation, ISSAC '19, p.122130, 2019.

É. Luca-de-feo and . Schost, Fast arithmetics in Artin-Schreier towers over nite elds, Journal of Symbolic Computation, vol.47, issue.7, p.771792, 2012.

J. Doliskani and É. Schost, Computing in degree 2 k -extensions of nite elds of odd characteristic. Designs, Codes and Cryptography, vol.74, p.559569, 2015.

P. Emeliyanenko and M. Sagralo, On the complexity of solving a bivariate polynomial system, Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ISSAC '12, p.154161, 2012.

J. Faugère, A new ecient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra, vol.139, issue.13, pp.61-88, 1999.

J. Faugère, A new ecient algorithm for computing Gröbner bases without reduction to zero (F5), Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC '02, p.7583, 2002.

J. Faugère, FGb: a library for computing Gröbner bases

I. K. Fukuda, J. Van-der-hoeven, M. Joswig, and N. Takayama, editors, Mathematical Software -ICMS 2010, vol.6327, p.8487, 2010.

J. Faugère, P. Gaudry, L. Huot, and G. Renault, Polynomial systems solving by fast linear algebra, 2013.

J. Faugère, P. Gaudry, L. Huot, and G. Renault, Sub-cubic change of ordering for Gröbner basis: A probabilistic approach, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, p.170177, 2014.

J. Faugere, P. Gianni, D. Lazard, and T. Mora, Ecient computation of zero-dimensional Gröbner bases by change of ordering, Journal of Symbolic Computation, vol.16, issue.4, p.329344, 1993.

R. Fröberg and J. Hollman, Hilbert series for ideals generated by generic forms, Journal of Symbolic Computation, vol.17, issue.2, pp.149-157, 1994.

C. Fieker, W. Hart, T. Hofmann, and F. Johansson, Nemo/Hecke: Computer algebra and number theory packages for the Julia programming language, Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '17, p.157164, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01524140

J. Faugere, K. Horan, D. Kahrobaei, M. Kaplan, E. Kashe et al., Fast quantum algorithm for solving multivariate quadratic equations, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01995374

G. Laurent-fousse, V. Hanrot, P. Lefèvre, P. Pélissier, and . Zimmermann, MPFR: A multiple-precision binary oating-point library with correct rounding, ACM Trans. Math. Softw, vol.33, issue.2, 2007.

C. M. Fiduccia, On obtaining upper bounds on the complexity of matrix multiplication, Complexity of Computer Computations, p.3140, 1972.

J. , C. Faugère, and A. Joux, Algebraic cryptanalysis of

, Hidden Field Equation (HFE) cryptosystems using Gröbner bases, Advances in Cryptology -CRYPTO 2003, p.4460, 2003.

M. Frigo and S. G. Johnson, The design and implementation of FFTW3, Special issue on Program Generation, Optimization, and Platform Adaptation, vol.93, issue.2, p.216231, 2005.

J. Michael, L. J. Fischer, and . Stockmeyer, Fast on-line integer multiplication, Journal of Computer and System Sciences, vol.9, issue.3, p.317331, 1974.

M. Fürer, Faster integer multiplication, SIAM Journal on Computing, vol.39, issue.3, p.9791005, 2009.

A. Galligo, A propos du théoreme de préparation de Weierstrass, Fonctions de plusieurs variables complexes, p.543579, 1974.

C. Friedrich and G. , Demonstratio nova theorematis omnem functionem algebraicam rationalem integram unius variabilis in factores reales primi vel secundi gradus resolvi posse, Apud CG Fleckeisen, p.1799

C. Friedrich and G. , Nachlass: Theoria interpolationis methodo nova tractata, Werke, vol.3, p.1866

P. Vladimir, Y. A. Gerdt, and . Blinkov, Involutive bases of polynomial ideals, Mathematics and Computers in Simulation, vol.45, issue.5, pp.519-541, 1998.

, GCC, the GNU Compiler Collection, from 1987. Software available at

J. Von-zur-gathen and J. Gerhard, Modern computer algebra

M. Giusti and J. Heintz, Algorithmes disons rapides pour la décomposition d'une variété algébrique en composantes irréductibles et équidimensionnelles, Eective Methods in Algebraic Geometry, p.169194, 1991.

J. Marc-giusti, J. E. Heintz, J. Morais, L. M. Morgenstem, and . Pardo, Straight-line programs in geometric elimination theory, Journal of Pure and Applied Algebra, vol.124, issue.1, pp.101-146, 1998.

M. Giusti, G. Lecerf, and B. Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity, vol.17, issue.1, pp.154-211, 2001.

A. Guessoum and R. M. Mersereau, Fast algorithms for the multidimensional discrete Fourier transform, IEEE Transactions on Acoustics, Speech and Signal Processing, vol.34, issue.4, p.937943, 1986.

G. Gallo and B. Mishra, Ecient algorithms and bounds for Wu-Ritt characteristic sets, Eective Methods in Algebraic Geometry, p.119142, 1991.

G. Gallo and B. Mishra, Discrete and Computational Geometry: Papers from the DI-MACS Special Year, vol.6, p.111136, 1991.

S. Gao and T. Mateer, Additive fast Fourier transforms over nite elds, IEEE Trans. Inform. Theory, vol.56, issue.12, p.62656272, 2010.

A. Giovini, T. Mora, G. Niesi, L. Robbiano, and C. Traverso, One sugar cube, please; or selection strategies in the Buchberger algorithm, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC '91, p.4954, 1991.

I. Good, The interaction algorithm and practical Fourier analysis, Journal of the Royal Statistical Society: Series B (Methodological), vol.20, issue.2, p.361372, 1958.

, Torbjörn Granlund and the GMP development team. GNU MP: The GNU Multiple Precision Arithmetic Library, 1991.

R. Daniel, M. E. Grayson, and . Stillman, Macaulay2, a software system for research in algebraic geometry

L. González, -. Vega, and M. Kahoui, An improved upper complexity bound for the topology computation of a real algebraic plane curve, Journal of Complexity, vol.12, issue.4, pp.527-544, 1996.

L. Gonzalez, -. Vega, and I. Necula, Ecient topology determination of implicitly dened algebraic plane curves, Computer Aided Geometric Design, vol.19, issue.9, pp.719-743, 2002.

D. Harvey, A cache-friendly truncated FFT, Theoretical Computer Science, vol.410, issue.27, pp.2649-2658, 2009.

W. B. Hart, Fast Library for Number Theory: An Introduction, Proceedings of the Third International Congress on Mathematical Software, ICMS'10, p.8891, 2010.

D. Harvey, Faster algorithms for the square root and reciprocal of power series, Mathematics of Computation, vol.80, issue.273, p.387394, 2011.

D. Harvey and J. Van-der-hoeven, Faster integer multiplication using plain vanilla FFT primes, Mathematics of Computation, vol.88, issue.315, pp.501-514, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02350423

D. Harvey and J. Van-der-hoeven, Faster integer multiplication using short lattice vectors, Proc. of the 13-th Algorithmic Number Theory Symposium, vol.2, p.293310, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02350426

D. Harvey and J. Van-der-hoeven, Faster polynomial multiplication over nite elds using cyclotomic coecient rings, Journal of Complexity, 2019.

D. Harvey and J. Van-der-hoeven, Integer multiplication in time, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02070778

D. Harvey and J. Van-der-hoeven, Polynomial multiplication over nite elds in time, 2019.

D. Harvey, J. Van-der-hoeven, and G. Lecerf, Fast polynomial multiplication over F 2 60, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '16, p.255262, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01265278

D. Harvey, J. Van-der-hoeven, and G. Lecerf, Even faster integer multiplication, Journal of Complexity, vol.36, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01022749

D. Harvey, J. Van-der-hoeven, and G. Lecerf, Faster polynomial multiplication over nite elds, Journal of the ACM (JACM), vol.63, issue.6, 2017.

D. Hilbert, Ueber die Theorie der algebraischen Formen, Mathematische Annalen, vol.36, issue.4, p.473534, 1890.

H. Hironaka, Resolution of singularities of an algebraic variety over a eld of characteristic zero: I, Annals of Mathematics, vol.79, issue.1, p.109203, 1964.

S. Lenwood, N. A. Heath, and . Loehr, New algorithms for generating Conway polynomials over nite elds, Journal of Symbolic Computation, vol.38, issue.2, pp.1003-1024, 2004.

G. Joris-van-der-hoeven and . Lecerf, Interfacing Mathemagix with C++, Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, p.363370, 2013.

G. Joris-van-der-hoeven and . Lecerf, Mathemagix User Guide, 2013.

R. Joris-van-der-hoeven and . Larrieu, The Frobenius FFT, Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC '17, p.437444, 2017.

R. Joris-van-der-hoeven and . Larrieu, Fast reduction of bivariate polynomials with respect to suciently regular Gröbner bases, Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC '18, 2018.

G. Joris-van-der-hoeven and . Lecerf, On the complexity exponent of polynomial system solving, 2018.

G. Joris-van-der-hoeven and . Lecerf, Directed evaluation, HAL, 2018.

G. Joris-van-der-hoeven and . Lecerf, Modular composition via factorization, Journal of Complexity, vol.48, pp.36-68, 2018.

R. Joris-van-der-hoeven and . Larrieu, Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals, 2019.

G. Joris-van-der-hoeven and . Lecerf, Accelerated tower arithmetic, Journal of Complexity, p.101402, 2019.

G. Joris-van-der-hoeven and . Lecerf, Fast computation of generic bivariate resultants, HAL, 2019.

R. Joris-van-der-hoeven, G. Larrieu, and . Lecerf, Implementing fast carryless multiplication, Proceedings of Mathematical Aspects of Computer and Information Sciences, p.121136, 2017.

G. Joris-van-der-hoeven, B. Lecerf, and . Mourrain, Mathemagix

R. Joris-van-der-hoeven, É. Lebreton, and . Schost, Structured FFT and TFT: Symmetric and lattice polynomials, Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, p.355362, 2013.

V. Seung-gyu-hyun, É. Neiger, and . Schost, Implementations of ecient univariate polynomial matrix algorithms and application to bivariate resultants, Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, ISSAC '19, p.235242, 2019.

J. Hoe, Les Systèmes d'équations polynômes dans le Siyuan Yujian: 1303, vol.6, 1977.

J. Van-der-hoeven, Relax, but don't be too lazy, Journal of Symbolic Computation, vol.34, issue.6, pp.479-542, 2002.

J. Van-der-hoeven, The Truncated Fourier Transform and applications, Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, ISSAC '04, p.290296, 2004.

J. Van-der-hoeven, Newton's method and FFT trading, Journal of Symbolic Computation, vol.45, issue.8, p.857878, 2010.

J. Van-der-hoeven, Faster relaxed multiplication, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, p.405412, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00687479

J. Van-der-hoeven, On the complexity of polynomial reduction, of Springer Proceedings in Mathematics and Statistics, vol.198, p.447458, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00658704

J. Van-der-hoeven, Faster Chinese remaindering, HAL, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01403810

D. Harvey and D. S. Roche, An in-place Truncated Fourier Transform and applications to polynomial multiplication, Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ISSAC '10, p.325329, 2010.

É. Joris-van-der-hoeven and . Schost, Multi-point evaluation in higher dimensions, vol.24, p.3752, 2013.

M. Janet, Sur les systèmes d'équations aux dérivées partielles. Journal de Mathématiques Pures et Appliquées, vol.170, p.65152, 1920.

J. R. Johnson and X. Xu, Generating symmetric DFTs and equivariant FFT algorithms, Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, ISSAC '07, p.195202, 2007.

M. Kalkbrener, Three contributions to elimination theory. PhD thesis, 1991.

A. Karatsuba and Y. Ofman, Multiplication of multidigit numbers on automata, Soviet physics doklady, vol.7, p.595596, 1963.

L. Kronecker, Grundzüge einer arithmetischen Theorie der algebraischen Grössen, Journal für die reine und angewandte Mathematik, vol.92, p.1882

A. Kudlicki, M. Rowicka, and Z. Otwinowski, The crystallographic fast Fourier transform. Recursive symmetry reduction, Acta Crystallographica Section A, vol.63, issue.6, p.465480, 2007.

S. Kiran, C. Kedlaya, and . Umans, Fast polynomial factorization and modular composition, SIAM Journal on Computing, vol.40, issue.6, p.17671802, 2011.

T. Hsiang and . Kung, On computing reciprocals of power series, Numerische Mathematik, vol.22, issue.5, p.341348, 1974.

R. Larrieu, The Truncated Fourier Transform for mixed radices, Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC '17, p.261268, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01419442

R. Larrieu, Computing generic bivariate Gröbner bases with Mathemagix, 2019.

D. Lazard, A new method for solving algebraic systems of positive dimension, Discrete Applied Mathematics, vol.33, issue.1, pp.147-160, 1991.

D. Lazard, Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, vol.13, issue.2, pp.117-131, 1992.

. Lck-+-18-;-wen-ding, M. Li, P. Chen, C. Kuo, B. Cheng et al., Frobenius additive fast Fourier transform, Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC '18, p.263270, 2018.

R. Lebreton, Relaxed Hensel lifting of triangular sets, Journal of Symbolic Computation, vol.68, issue.P2, p.230258, 2015.
URL : https://hal.archives-ouvertes.fr/lirmm-01282077

H. W. Lenstra, Finding isomorphisms between nite elds. Mathematics of Computation, vol.56, p.329347, 1991.

F. Gall, Powers of tensors and fast matrix multiplication, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, p.296303, 2014.

X. Li, M. Moreno-maza, and É. Schost, Fast arithmetic for triangular sets: From theory to practice, International Symposium on Symbolic and Algebraic Computation, vol.44, pp.891-907, 2009.

R. Lebreton, E. Mehrabi, and E. Schost, On the complexity of solving bivariate systems: The case of non-singular solutions, Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, p.251258, 2013.
URL : https://hal.archives-ouvertes.fr/lirmm-00814992

F. S. Macaulay, Some formulae in elimination, Proceedings of the London Mathematical Society, issue.1, p.327, 1902.

D. John, . Markel, and . Pruning, IEEE Transactions on Audio and Electroacoustics, vol.19, issue.4, p.305311, 1971.

T. Mateer, Fast Fourier Transform Algorithms with Applications, 2008.

E. Mayr, Membership in polynomial ideals over Q is exponential space complete, STACS, vol.89, p.400406, 1989.

R. M. Mersereau, An algorithm for performing an inverse chirp ztransform, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol.22, issue.5, p.387388, 1974.

M. B. Monagan, K. O. Geddes, K. M. Heal, G. Labahn, S. M. Vorkoetter et al.,

, Maple 10 Programming Guide, 2005.

H. and M. Möller, On the construction of Gröbner bases using syzygies, Journal of Symbolic Computation, vol.6, issue.2, pp.345-359, 1988.

R. E. Moore, Interval analysis, vol.4, 1966.

G. Moreno-socías, Degrevlex Gröbner bases of generic complete intersections, Journal of Pure and Applied Algebra, vol.180, issue.3, pp.263-283, 2003.

A. Morgan, Solving polynomial systems using continuation for engineering and scientic problems, vol.57, 2009.

J. Nicolas and G. Robin, Highly composite numbers by Srinivasa Ramanujan, The Ramanujan Journal, vol.1, issue.2, p.119153, 1997.

Y. Victor and . Pan, Simple multivariate polynomial multiplication, Journal of Symbolic Computation, vol.18, issue.3, pp.183-186, 1994.

C. H. Papadimitriou, Computational Complexity, 1994.

R. Parker, Finite elds and Conway polynomials, 1990. Talk given at IBM

J. Pommaret and A. Haddak, Eective methods for systems of algebraic partial dierential equations, Eective Methods in Algebraic Geometry, p.411426, 1991.

C. M. Rader, Discrete Fourier transforms when the number of data samples is prime, Proceedings of the IEEE, vol.56, issue.6, p.11071108, 1968.

C. Riquier,

, Les systèmes d'équations aux dérivées partielles

. Gauthier-villars, , 1910.

J. F. Ritt, Dierential equations from the algebraic standpoint, vol.14, 1932.

J. F. Ritt, Dierential algebra, vol.33, 1950.

A. Rosenfeld, Specializations in dierential algebra, Transactions of the American Mathematical Society, vol.90, issue.3, p.394407, 1959.

F. Rouillier, Solving zero-dimensional systems through the rational univariate representation, Applicable Algebra in Engineering, Communication and Computing, vol.9, issue.5, p.433461, 1999.
URL : https://hal.archives-ouvertes.fr/inria-00073264

L. R. Rabiner, R. W. Schafer, and C. M. Rader, The chirp z-transform algorithm, IEEE Transactions on Audio and Electroacoustics, vol.17, issue.2, p.8692, 1969.

, The Sage Developers. SageMath, the Sage Mathematics Software System, 2017.

A. Schönhage, Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acta Infor, vol.7, p.395398, 1977.

A. Scheerhorn, Trace-and norm-compatible extensions of nite elds, vol.3, 1992.

É. Schost, Complexity results for triangular sets, Journal of Symbolic Computation, vol.36, issue.3, pp.555-594, 2002.

V. Shoup, NTL: A library for doing number theory, 2001.

M. Sieveking, An algorithm for division of powerseries, Computing, vol.10, issue.1, p.153156, 1972.

H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, Real-valued fast Fourier transform algorithm, IEEE Transactions on Acoustics, Speech and Signal Processing, vol.35, issue.6, p.849863, 1987.

S. Smale, The fundamental theorem of algebra and complexity theory, Bulletin (New Series) of the American Mathematical Society, vol.4, issue.1, p.136, 1981.

S. Smale, Algorithms for solving equations, Proceedings of the International Congress of Mathematicians, pp.172-195, 1986.

A. Schönhage and . Volker-strassen, Fast multiplication of large numbers, Computing, vol.7, issue.3, p.281292, 1971.

. Volker-strassen, Gaussian elimination is not optimal, Numerische Mathematik, vol.13, issue.4, p.354356, 1969.

. Volker-strassen, Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoezienten, Numerische Mathematik, vol.20, issue.3, p.238251, 1973.

F. T. Lynn and . Eyck, Crystallographic Fast Fourier Transform, Acta Crystallographica Section A, vol.29, p.183191, 1973.

J. Miller and T. , Dierential systems, American Mathematical Society, vol.21, 1937.

H. Llewellyn and . Thomas, Using a computer to solve problems in physics. Applications of digital computers, p.4445, 1963.

J. Verschelde, Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Transactions on Mathematical Softwware, vol.25, issue.2, p.251276, 1999.

G. Villard, On computing the resultant of generic bivariate polynomials, Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC '18, p.391398, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01921369

A. Vince and X. Zheng, Computing the Discrete Fourier Transform on a hexagonal lattice, Journal of Mathematical Imaging and Vision, vol.28, issue.2, p.125133, 2007.

D. Wang, An elimination method for polynomial systems, Journal of Symbolic Computation, vol.16, issue.2, pp.83-114, 1993.

H. S. Warren, Hacker's Delight, 2012.

W. Wu, On the decision problem and the mechanization of theorem-proving in elementary geometry, Scientia Sinica, vol.21, issue.2, p.159172, 1978.

W. Wu, A zero structure theorem for polynomial equations-solving, Mathematics and Systems Science, vol.1, p.212, 1987.

Y. Wang and X. Zhu, A fast algorithm for the Fourier transform over nite elds and its VLSI implementation, IEEE Journal on Selected Areas in Communications, vol.6, issue.3, p.572577, 1988.

A. Yu, Y. A. Zharkov, and . Blinkov, Involution approach to investigating polynomial systems, Math. Comput. Simul, vol.42, p.323332, 1996.