Designs and Their Codes, 1992. ,

Fast Encoding of AG Codes over Cab Curves, IEEE Trans. of Information Theory ,

Fast Algorithms for Manipulating Formal Power Series, J. ACM, vol.25, pp.581-595, 1978. ,

On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, vol.28, pp.693-701, 1991. ,

Fast systematic encoding of multiplicity codes, Journal of Symbolic Computation, 2018. ,

URL : https://hal.archives-ouvertes.fr/hal-01512372

A Probabilistic Remark on Algebraic Program Testing, vol.7, pp.193-195, 1978. ,

FLINT: Fast Library for Number Theory, 2015. ,

Faster polynomial multiplication over finite fields, J. ACM, vol.63, 2017. ,

URL : https://hal.archives-ouvertes.fr/hal-01022757

Linear Systems, 1980. ,

Fast Polynomial Factorization and Modular Composition, SIAM J. Comput, vol.40, pp.1767-1802, 2011. ,

Ideal bases and primary decomposition: case of two variables, Journal of Symbolic Computation, vol.1, pp.261-270, 1985. ,

Powers of tensors and fast matrix multiplication, Proceedings of the 39th int. symp. on symbolic and algebraic comp, pp.296-303, 2014. ,

Algebraic geometric codes on certain plane curves, Electronics and Communications in Japan (Part III: Fundamental Electronic Science, vol.76, pp.1-13, 1993. ,

Éric Schost, and Gilles Villard. 2020. Faster modular composition ,

Computing Canonical Bases of Modules of Univariate Relations, International Symposium on Symbolic and Algebraic Computation, 2017. ,

URL : https://hal.archives-ouvertes.fr/hal-01457979

Fast Multipoint Evaluation of Bivariate Polynomials, 2004. ,

, , pp.544-555

Simple Multivariate Polynomial Multiplication, Journal of Sym. Comp, vol.18, pp.183-186, 1994. ,

On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. Comput, vol.2, pp.60-66, 1973. ,

Some properties of the control systems with irreducible matrixtransfer functions, Seminar on Diff. Eq. and Dyn. Sys., II, pp.169-180, 1970. ,

Fast Probabilistic Algorithms for Verification of Polynomial Identities, vol.27, pp.701-717, 1980. ,

NTL: A Library for doing Number Theory, 2020. ,

On the complexity of multivariate polynomial division, Special Sessions in App. of Computer Algebra, pp.447-458, 2015. ,

Modular composition via factorization, Journal of Complexity, vol.48, pp.36-68, 2018. ,

Fast multivariate multi-point evaluation revisited, Journal of Complexity, 2019. ,

Multi-point evaluation in higher dimensions, Applicable Algebra in Engineering, Communication and Computing, vol.24, pp.37-52, 2013. ,

URL : https://hal.archives-ouvertes.fr/hal-00477659

On computing the resultant of generic bivariate polynomials, Proc. of the 2018 ACM Int. Symp. on Symbolic and Algebraic Comp, pp.391-398, 2018. ,

URL : https://hal.archives-ouvertes.fr/hal-01921369

On computing the resultant of generic bivariate polynomials, 2018. ,

URL : https://hal.archives-ouvertes.fr/hal-01921369

, Modern Computer Algebra, 2012.

Probabilistic algorithms for sparse polynomials, EUROSAM'79, vol.72, pp.216-226, 1979. ,

A PROOFS Proof of Proposition 2.2. Note first that X 0 is the set of all x-coordinates in P, and X 0 ? X 1 ,

In fact, this shows that any element of ?G? reduces to zero when divided by G with the bivariate division algorithm according to ?, and hence G is a Gröbner basis. Consider now G ? . For each b i for i J then LC y (b i ) = LC(b i?1 ), and hence removing b i from G does not change the ideal generated. Hence ?G ? ? = ?G? = ?(P), and G ? is also a Gröbner basis. Observe that for j ? J then LT ? (b j ) is not divisible by any LT ? (b i ) for 0, . . . , ? x and hence G ? is a minimal Gröbner basis. ? The following is a simplification of Lazard's structure theorem of ideals of bivariate polynomials [11], which we use for the proof of Corollary 2.4: Proposition A.1. Let I ? K[x, y] be an ideal and G = {b 1 , . . . , b s } ? K[x, y] a minimal Gröbner basis according to the lex-order ? with x ? y with G ordered by increasing ?-order. Then (1) deg y b 1 < deg y b 2 < . . . < deg y b s ; and (2) LC y (b i+1 ) | LC y (b i ) for i = 1, . . . , s ? 1. Proof of Corollary 2.4. That M is an K[x]-module follows simply from I being an ideal of K[x, y], and in particular closed under addition and multiplication by K[x]-elements, which is therefore inherited by M. Clearly B ? M, and the elements of B all have different y-degree and so are K[x]-linearly independent. Also |B| = m ? deg y b 1, We may choose b ? i as in (1): For each i and ? there are ? ? interpolation constraints on b i,? , and since ? X i then ? ? < i. Hence we can satisfy the interpolation constraints while deg y b i,? < i. Therefore deg y b i = i for all i = 0, . . . , s, and LC y (b i ) = ? ?X i (x ? ?) ,