E. F. Assmus and J. D. Key, Designs and Their Codes, 1992.

P. Beelen, J. Rosenkilde, and G. Solomatov, Fast Encoding of AG Codes over Cab Curves, IEEE Trans. of Information Theory

R. P. Brent and H. T. Kung, Fast Algorithms for Manipulating Formal Power Series, J. ACM, vol.25, pp.581-595, 1978.

G. David, E. Cantor, and . Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, vol.28, pp.693-701, 1991.

N. Coxon, Fast systematic encoding of multiplicity codes, Journal of Symbolic Computation, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01512372

R. A. Demillo and R. J. Lipton, A Probabilistic Remark on Algebraic Program Testing, vol.7, pp.193-195, 1978.

W. Hart, F. Johansson, and S. Pancratz, FLINT: Fast Library for Number Theory, 2015.

D. Harvey, J. Van-der-hoeven, and G. Lecerf, Faster polynomial multiplication over finite fields, J. ACM, vol.63, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01022757

. Kailath, Linear Systems, 1980.

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

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

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

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

V. Neiger and B. Salvy, Éric Schost, and Gilles Villard. 2020. Faster modular composition

V. Neiger and T. X. Vu, Computing Canonical Bases of Modules of Univariate Relations, International Symposium on Symbolic and Algebraic Computation, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01457979

M. Nüsken and M. Ziegler, Fast Multipoint Evaluation of Bivariate Polynomials, 2004.

H. Springer-berlin, , pp.544-555

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

S. Michael, L. J. Paterson, and . Stockmeyer, On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. Comput, vol.2, pp.60-66, 1973.

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

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

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

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

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

G. Joris-van-der-hoeven and . Lecerf, Fast multivariate multi-point evaluation revisited, Journal of Complexity, 2019.

J. Van-der-hoeven and É. Schost, 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

G. Villard, 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

G. Villard, On computing the resultant of generic bivariate polynomials, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01921369

J. Zur-gathen and J. Gerhard, Modern Computer Algebra, 2012.

R. Zippel, 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

. ?-x-?-x-?1-?-x-?-x-=-?, 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 ? ?)