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

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

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

D. A. Cox, J. Little, and D. O'shea, Ideals, Varieties, and Algorithms, 2015.

N. Coxon, Fast systematic encoding of multiplicity codes, J. Symb. Comput, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01512372

X. Dahan, Size of Coefficients of Lexicographical Gröbner Bases: The Zero-Dimensional, Radical and Bivariate Case, Proceedings ISSAC 2009. 119-126, 2009.

R. A. Demillo and R. J. Lipton, A Probabilistic Remark on Algebraic Program Testing, Inf. Process. Lett, vol.7, issue.78, pp.90067-90071, 1978.

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

C. Jeannerod, V. Neiger, É. Schost, and G. Villard, Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts, Proceedings ISSAC 2016, pp.295-302, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01265983

. 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, J. Symb. Comput, vol.1, p.3, 1985.

F. and L. Gall, Powers of tensors and fast matrix multiplication, Proceedings ISSAC 2014. ACM, 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, B. Salvy, É. Schost, and G. Villard, Faster modular composition, 2020.

V. Neiger and T. X. Vu, Computing Canonical Bases of Modules of Univariate Relations, Proceedings ISSAC 2017, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01457979

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

V. Y. Pan, Simple Multivariate Polynomial Multiplication, J. Symb. Comput, vol.18, pp.183-186, 1994.

M. S. Paterson and L. J. 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, J. ACM, 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, Proceedings ACA 2015. 447-458, 2015.

J. Van-der-hoeven and G. Lecerf, Modular composition via factorization, J. Complexity, vol.48, pp.36-68, 2018.
URL : https://hal.archives-ouvertes.fr/hal-02350457

J. Van-der-hoeven and G. Lecerf, Fast multivariate multi-point evaluation revisited, J. Complexity, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01848571

J. Van-der-hoeven and É. Schost, Multi-point evaluation in higher dimensions, Appl. Algebra Eng. Commun. Comput, vol.24, pp.37-52, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00477659

G. Villard, On computing the resultant of generic bivariate polynomials, Proceedings ISSAC 2018. 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. Von-zur-gathen, Functional decomposition of polynomials: the tame case, J. Symb. Comput, vol.9, p.3, 1990.

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

R. Zippel-;-|-·-·-·-|-lc-y, Let G = {b 0 , . . . , b s } ? K[x, y] be a minimal ? lex -Gröbner basis, sorted according to ? lex . Then (1) deg y b 0 < . . . < deg y b s ; and (2) LC y (b s ) | LC y (b s?1 ), Proceedings EUROSAM'79, pp.216-226, 1979.

, Since I is an ideal of K[x, y] and I ? =

. I-?-k,

, Clearly B ? I ? , and the elements of B all have different y-degree and so are K[x]-linearly independent. Also |B| = ? ? d 0 , so if B generates B generates I ? , so take some f ? I ? . Since f ? I the multivariate division algorithm using G and the order ? lex results in q 0

, Thus no term of q i b i is divisible by LT lex (b i+1 ) for any i < s. But by Corollary A.1 then LC y (b i+1 ) divides LC y (b i ), and so if deg y (q i b i ) ? deg y b i+1 then LT lex

A. Lemma, There is an algorithm which inputs a ? lex -Gröbner basis G = [b 0 , . . . , b s ] ? K[x, y] with deg y b 0 = 0, and a polynomial f ? K[x, y], and outputs f rem G in timeÕ(|G |d x (deg y f )), where d x = max