We present a p-adic algorithm to recover the lexicographic Gröbner basis of an ideal in with a generating set in , with a complexity that is less than cubic in terms of the dimension of and softly linear in the height of its coefficients. We observe that previous results of Lazard’s that use Hermite normal forms to compute Gröbner bases for ideals with two generators can be generalized to a set of generators. We use this result to obtain a bound on the height of the coefficients of , and to control the probability of choosing a good prime p to build the p-adic expansion of .

Following recent work by van der Hoeven and Lecerf (ISSAC 2017), we discuss the complexity of linear mappings, called untangling and \emphtangling by those authors, that arise in the context of computations with univariate polynomials. We give a slightly faster tangling algorithm and discuss new applications of these techniques. We show how to extend these ideas to bivariate settings, and use them to give bounds on the arithmetic complexity of certain algebras.