Relaxed p-adic Hensel lifting for algebraic systems

 Univariate root lifting

In [BHL11, Section 7], it is shown how to compute the dth root of a p-adic number a in a recursive relaxed way, d being relatively prime to p. In this section, we extend this result to the relaxed lifting of a simple root of any polynomial P ∈R[Y ]. Hensel’s lemma ensures that from any modular simple root y0∈R/(p) of P¯ ∈R/(p)[Y ], there exists a unique lifted root y ∈ Rp of P such that y = y0 mod p. From now on, P is a polynomial with coefficients in R and y ∈ Rp is the unique root of P lifted from the modular simple root y0 ∈ R/(p)

Dense polynomials 

In this subsection, we fix a polynomial P of degree d given in dense representation, that is as the vector of its coefficients in the monomial basis (1, Y , , Y d ). To have a shifted algorithm, we need to express Φ(Y ) with a positive shift. Recall, from Definition 2.11, that the shift of Φ(Y ) is 0. In this chapter, for any two p-adics a and b, we denote by a · b their multiplication. If at least one of them has finite precision, we denote by a b their multiplication

Proposition 5.3. 

Given a polynomial P of degree d in dense representation and a modular simple root y0, Algorithm 5.2.1 defines a shifted algorithm Ψ associated to Φ. The precomputation of such an operator involves O(d) operations in R. If λ is the length of P ′ (y0), then we can lift y at precision N in time

Proof

 First, Ψ is a shifted algorithm for Φ. Indeed since sh(P(y0) − P ′ (y0) y0) = +∞ and, due to Lemma 5.2, sh(p 2 × (sq(Z)· Q(Z))) = 1, we have sh(Ψ) = 1. Also, thanks to Lemma 5.2, we can execute Ψ on y over the R-algebra Rp. Moreover, it is easy to see that Φ(Y ) = Ψ(Y ) over the R-algebra K[Y ]. The quotient polynomial Q is precomputed in time O(d) via the naïve Euclidean division algorithm. Using Horner scheme to evaluate Q(Z), we have L ∗ (Ψ) = d − 1 and we can apply Proposition 2.17. Note that by Proposition 3.6 for r = 1, the inversion of P ′ (y0) costs O(N R(λ)/λ). Finally, the evaluation of Q also involves O(d) on-line additions which cost O(N d).  In comparison, Newton iteration lifts y at precision N in time (3 d+O(1)) I(N)+ O(d N) (see [GG03, Theorem 9.25]). Here, the universal constant in the O(1) corresponds to p-adic inversion and can be taken less than 4. The reminder on Newton iteration can be found in Section 6.3.1. So the first advantage of our on-line algorithm is that it does asymptotically less on-line multiplications than Newton iteration does off-line multiplications. Also, we can expect better timings from the on-line method for the Hensel lifting of y when the precision N satisfies R(N) 6 3 I(N).

Polynomials as straight-line programs In [BHL11, Proposition 7.1], the case of the polynomial P(Y ) = Y d − a was studied. Although the general concept of a shifted algorithm was not introduced, an algorithm of multiplicative complexity O(L ∗ (P)) was given. The shifted algorithm was only present in the implementation in Mathemagix [HLM+02]. We clarify and generalize this approach to any polynomial P given as an s.l.p. and propose a shifted algorithm Ψ whose complexity is linear in L ∗ (P). In this subsection, we fix a polynomial P given as an s.l.p. Γ with L operations in Ω 7 {+, −, ·} ∪ R ∪ Rc and multiplicative complexity L ∗ 7 L ∗ (P), and a modular simple root y0 ∈ R/(p) of P. Then, we define the polynomials TP(Y ) 7 P(y0) + P ′ (y0) (Y − y0) and EP(Y ) 7 P(Y ) − TP(Y ).