Solving quadratic equations over polynomial rings of characteristic two

Publicacions Matem`atiques, Vol 42 (1998), 131–142. SOLVING QUADRATIC EQUATIONS OVER POLYNOMIAL RINGS OF CHARACTERISTIC TWO Jørgen Cherly, Luis Gallardo, Leonid Vaserstein and Ethel Wheland Abstract We are concerned with solving polynomial equations over rings. More precisely, given a commutative domain Awith 1 and a polynomial equation antn+···+a 0= 0 with coefficients aiin A, our problem is to find its roots in A. We show that when A=B[x] is a polynomial ring, our problem can be reduced to solving a finite sequence of polynomial equations over B. As an application of this reduction, we obtain a finite algorithm for solving a polynomial equation over Awhen Ais F[x1,... ,x N]orF(x 1 ,... ,x N) for any finite field Fand any number Nof variables. The case of quadratic equations in characteristic two is studied in detail. 1. Introduction Let Abe a commutative domain with 1. We consider an equation (1) antn+···+a 0=0 for twith given aiin A. We call such an equation a polynomial equation over Aof degree ≤n(or degree nif an6= 0). Its roots tare to be found in A. We will show that when A=B[x], the polynomial ring in one variable x, then solving (1) can be reduced to solving a finite system of polynomial equations over B. Each of these equations has degree at most n, and the number of the equations can be bound in terms of degrees of ai. By induction on N, this gives a reduction of the problem over A=E[x1,... ,x N] to solving a finite sequence of equations over E. When Eis a finite field or the ring of integers, there are finite algorithms 132 J. Cherly, L. Gallardo, L. Vaserstein, E. Wheland for solving polynomial equations over E. So we obtain a finite algorithm for solving (1) over A=E[x1,... ,x N]. Solving (1) over the field Rof quotients of Acan be easily reduced to solving a similar equation with a monic polynomial in A[t] whose roots over Rbelong to A. So we also obtain a finite algorithm for solving (1) over the field A=E(x1,... ,x N) when Eis a finite field or the field of rational numbers. This can be generalized to subrings Aof E(x1,... ,x N) when the membership in the subring can be decided in finitely many steps. A more general problem of factorization of multivariate polynomials in any degree with coefficients in finitely generated fields has been considered before (see [2], [4]). As will be seen, we take a different approach to this problem. Given a quadratic equation, that is, (1) with n=2,a 26= 0, a wellknown formula reduces it to an equation of the form y2= ∆ and a linear equation, provided that 2 A6= 0. We consider in detail the case 2 A=0 when, obviously, the above-mentioned formula doesn’t apply. 2. Reduction from A=B[x]to B Given ai∈A=B[x], we want to solve (1) in A.Ifa n=0ora 0=0, then (1) reduces to an equation of a smaller degree, so we will assume that ana06=0. First we obtain bounds for the degree d= deg(t) of a solution t∈A=B[x] of (1) in terms of di= deg(ai) (with the convention that deg(0) = −∞). Proposition 1. If (1) with ana06=0has a root t∈A=B[x], then deg(t)≤min(d0,max i=0,... ,n−1((di−dn)/(n−i))). Proof: Since tdivides a0, deg(t)≤d0. If deg(t)>(di−dn)/(n−i) for all i, then the term antnhas a higher degree in xthan any other term in the left hand side of (1). Remark. If we plot the points (0,d n),... ,(n+1,d 0) in the Euclidean plane and consider the least concave function D(i)≤dn−i, then the maximum in the proposition is the slope of D(i)ati= 0, which is the largest slope of D. If this slope is negative, i.e., dn>d ifor i<n, then (1) has no solutions in A. In general there are at most ndistinct slopes of D, and the bound for deg(t) in the proposition can be improved as follows: deg(t) is at most the largest slope not exceeding d0. Polynomial Equations 133 Theorem 1. Finding all roots tin A=B[x]of a given degree dfor (1) with n≥1can be reduced to solving in Ba finite sequence of at most 1+n+···+n dpolynomial equations in one variable over B, each of them of degree ≤n. Proof: Without loss of generality, we can assume that an6=0. We proceed by induction on d. When d=−∞, i.e., t= 0, we do not need to solve any equations (we have to check only whether a0is 0). When d= 0, (1) is equivalent to a system of at most max(deg(ai)) polynomial equations over Bfor t∈B, each of them of degree ≤n.We solve one of them and then verify the other equations for each of at most nroots in B. Assume now that d≥1. Let t=t0+xs with t0∈B,s∈A=B[x], deg(s)=d−1. Taking the smallest degree terms in (1), we obtain a polynomial equation for t0over Bof positive degree ≤n. Solving it, we obtain at most nvalues for t0in B. Substituting each of them in (1), we obtain a polynomial equation of degree ≤nfor s∈ B[x] with deg(s)≤n−1. Using the induction hypothesis, we reduce the problem of finding all roots of degree dfor (1) to solving at most 1+n(1 + n+···+n d−1)=1+n+···+n dequations over B(and verifying several equalities in B). Assuming that we can solve polynomial equations over B, we can solve (1) over Ain finitely many steps, using Theorem 1 together with Proposition 1. To get a good bound for the number of steps needed, one has to be able to control a possible branching. When the left hand side of (1) is 0, every t∈A=B[x] satisfies (1). Assume that an6=0,n≥0 in (1). When n= 0, (1) has no solutions. Let now n= 1. When d1= deg(a1)>d 0= deg(a0), (1) has no roots in A. Otherwise, it has at most one root t, and deg(t)=d 0−d 1=d. Substituting t=Pd i=0 tixiinto the equation a1t+a0= 0, we obtain d0+ 1 equations for tiin B, each of them of degree ≤1. As in the general case, we can find t0,t 1,... consecutively. There is no branching. The total number of equations in one variable over Bwe have to solve is d+ 1, and we have to verify d1equalities. We could also proceed from the other end, finding td,t d−1,... ,t 0consecutively. Then the equations we have to solve are of the form bti=ci, where b∈Bis the leading coefficient of a1∈A=B[x], ci∈B, and i=d, d −1,... ,0. The rest of the paper is about the case n= 2. In a future paper, we will apply our methods to higher degree equations. 134 J. Cherly, L. Gallardo, L. Vaserstein, E. Wheland 3. Quadratic equations in characteristic two The well-known formula for solving the quadratic equation (2) a2t2+a1t+a0=0 with a26= 0 does not work when we cannot divide by two in our ring A containing the given coeficients ai. If we are looking for roots of (2) in a field A, then a linear change of variables reduces the equation to one of two particular forms, (3) y2+∆=0 when a1= 0 and (4) y2+y+∆=0 when a16=0. Junjie Tang [10], solved (2) when Ais a finite field Fof characteristic two. In this case, y=∆ q/2is a root of (3) with q= card(A), and (4) has roots in Aif and only if Tr(∆) = 0, where Tr is the trace from A to GF(2) (Niederreiter [8]) (see Section 6 below for more details). In this paper we are interested in solving (2) in a commutative domain Aof characteristic two. This means that the given coefficients ai belong to A,2A= 0, and we are looking for roots in A. We show that when A=B[x] is a polynomial ring in one variable x(hence Bis a commutative domain of characteristic 2), then solving a quadratic equation (2) in Acan be reduced to solving several quadratic equations over B. The number of these equations is at most deg(a0) + deg(a2)+1. In particular, we get an effective algorithm for solving (2) over A=F[x1,... ,x k] for a finite field F. The number of steps in our method is O(deg(a0a2)), at each step we solve (3) with a number ∆ ∈F, except perhaps at one step, where we might have to solve (4) instead of (3). When Fis finite, it is easy to solve (3) and (4) with ∆ ∈F. Namely, y=∆ q/2is a root of (3) with q= card(F), and solving (4) will be discussed in Section 6. In general solving (2) over A=B[x] depends on solving (2) over B. The main equation studied in the rest of the paper is (2) with a2=1, namely (5) t2+a1t+a0=0. Polynomial Equations 135 We can reduce (2) to an equation of the form (5) by a change of variable. More precisely, the roots t=u/a2of (2) are in 1-1 correspondence with the roots of u2+a1u+a2a0= 0 with udivisible by a2. If a1= 0 in (5), i.e., we have an equation of the form (3), then it is reduced to a set of similar equations over B. Namely, (3) has a solution if and only if all the monomials in ∆ ∈B[x] have even degree (i.e., ∆0=0) and all the coefficients are squares. The solution, if it exists, is unique. In the case when Bis a finite field with qelements, the explicit solution is t=Pcq/2 2ixifor ∆ = Pc2ix2i. It can be computed in O(log(q) deg(∆)) multiplications in B(when deg(∆) ≥1). So in the rest of the paper we assume that a16= 0 in (5). We will apply the method of Section 2 to (5) in the next section. In Section 5 we give a method of reducing the degree of a1in (5) to 0. Section 6 deals with (5) with constant a1. Without loss of generality, we can assume that a06= 0, because otherwise (5) reduces to a degree one equation. Note that (5) has a root in a domain Aif and only if the polynomial t2+a1t+a0∈A[t] is reducible. When A=F[x] with a finite field F of characteristic two, there is a well-known irreducibility criterion using reduction modulo a polynomial p: Theorem 2. Let F=GF (2m),a0,a 1∈F[x],a 16=0, and let α be one element of the algebraic closure of GF(2), such that its minimal polynomial pover Fis relatively prime with a1. Suppose that (6) Tr(a0(α)/a1(α)2)=1. Then t2+a1t+a0is irreducible in the ring F[x, t]. The trace Tr is always taken over the prime subfield GF(2) = F2. For example, the polynomial t2+(x 2+x)t+x 3+xover F2[x] has no roots t∈F2[x], as seen by choosing the irreducible polynomial p=x2+x+ 1, or, with a slightly more complicated computation, by choosing p=x3+x+ 1, and it is clear that picking pof degree one gives no information here. Besides the obstructions for existence of roots of (5) given by Theorem 2 (in the particular case when Bis finite), there are degree obstructions (on degrees of a0,a 1) given by the following proposition (for any domain B). The proof is easy and will be left to the reader. 136 J. Cherly, L. Gallardo, L. Vaserstein, E. Wheland Proposition 2. Suppose that (5) with a0a16=0has a root tin B[x], where Bis a domain. Set r=∞when a1∈B, and r= deg(a0)/deg(a2 1) otherwise. (a) 2 r≥1. (b) If r≤1, then one of the roots tof (5), is such that deg(t)= deg(a0)−deg(a1). (c) If r=1, then both roots have the same degree, equal to deg(a1), and B6=F2. (d) If r>1, then the two roots tand −t−a1of (5) have the same degree, deg(a0)is even and deg(t) = deg(a0)/2 = deg(t+a1). 4. Solving (5) by the method of Section 2 We consider (5) with a0a16= 0 over B[x] with a domain Bof characteristic 2. Set di= deg(ai). We will show that finding a root of (5) can be reduced to solving 1+max(d0/2,d 0−d 1) equations over Bof degree 1 or 2. More precisely, we have max(d0/2−d1,0) equations of type (4), at most one quadratic equation over Bwith a nonzero linear term, and 1 + max(d0−d1,d 1) linear equations over B. Let rbe as in Proposition 2. We will show that solving (5) with r≥1 can be reduced to solving a similar equation with r<1 by solving a few quadratic equations over B, and that solving (5) with r<1 can be reduced to solving a few linear equations over B. Let t=Pd i=0 tixibe an unknown root of (5) with d6=0. When r<1, we can assume that d=d0−d1by Proposition 2. We have a linear equation tdb=cdfor td, where bis the leading coefficient of a1and cdis the leading coefficient of a0. If this equation has a root td∈B, we have a linear equation td−1b=cd−1with the same band some cd−1∈B. So consecutively solving d+ 1 linear equations of the form tib=ciover Bfor i=d, d −1,..., we solve (5) for t. When r= 1 (this case is impossible when B=F2), d=d1=d0/2by Proposition 2. We obtain a quadratic equation t2 d+btd+c= 0, where bis the leading coefficient of a1and cis the leading coefficient of a0. Having chosen a root td(if it exists), we obtain an equation for the rest of tof the form (5) with r<1. This equation can be reduced as above to dlinear equations over B. When r>1, d= deg(a0)/2 by Proposition 2. To find the leading coefficient tdof t, we utilize the equation t2 d=cd, where cdis the leading coefficient of a0. This equation over Bhas at most one root. Once Polynomial Equations 137 tdis found, we have a similar equation for td−1, and so on. Thus, we consecutively obtain equations t2 i=cifor i=d,... ,d 1+ 1. For the rest of t, we solve, as above, one quadratic and d1−1 linear equations over B. In all three cases, there are 2d+ 1 equations over B(some of which do not contain unknown coefficients tiof t). We find these d+ 1 coefficients (if they exist) from d+ 1 of the equations. Then we can check whether the other dequations hold. Remark. Assume that Bis a field, and consider the fraction a0/a2 1=u/v reduced to lowest terms in B[x], i.e., such that gcd(u, v)=1, with monic v. When (5) has a root, it is easy to see that vis the square of a polynomial. The Eisenstein criterion follows from this observation. 5. Induction on d1 As above, Bis a domain of characteristic 2. The idea is to write any polynomial p∈B[x]asp=f+xg, where f=(xp)0is the sum of even degree terms in pand xg =xp0is the sum of odd degree terms in p. Theorem 3. Suppose that (5) has a root t∈B[x]. Then a2 1|(a0 0)2+ a0 1(a1a0)0. Proof: Differentiating (5) we obtain (7) a0 1t=a1t0+a0 0. Squaring (7) and applying (5) we obtain (a0 1)2(a1t+a0)+a2 1(t0)2=(a 0 0 ) 2 . Using (7) to eliminate a0 1t,weget (8) a2 1((t0)2+a0 1t0)+(a 0 0 ) 2+a 0 1 (a 1 a 0 ) 0=0 which proves the conclusion of the theorem. Remark. Suppose that Aa1+Aa0 1=A=B[x] and that the leading coefficient of a1is invertible in B(when Bis a field, this means that a1is square-free). Then the conclusion of the theorem is equivalent to a1|(a0 1)2a0+(a 0 0 ) 2 . If, furthermore, d0/2≤d1<d 0 , then a root tof (5) in Acan be found as the polynomial tsuch that a0 1t≡a0 0modulo a1 and deg(t)<deg(a1)=d 1 . 138 J. Cherly, L. Gallardo, L. Vaserstein, E. Wheland Now we write down the reduction step. We will show that when (5) has a root, say t=(xt)0+xt0, then t0satisfies a ‘smaller’ quadratic equation of type (5). To obtain such an equation (t0)2+a0 1t0+((a 0 0 ) 2+a 0 1 (a 1 a 0 ) 0 )/a2 1=0 we divide (8) by a2 1; if the constant term is not divisible by a2 1then (5) has no roots by Theorem 3. Note that all coefficients in this equation are polynomials in x2, and the unknown root t0is also a polynomial in x2:t0(x)=f(x 2 ). So we obtain a quadratic equation for fof the form f2+a3f+a2= 0 with deg(a3)≤(deg(a1)−1)/2. Once we find fand hence t0, we can find tfrom (7) when a0 16=0. When a0 1= 0, we can use the linear equation (7) to find t0, rather than the quadratic equation (8). Then, to reconstruct the even part (xt)0of t we can use the even part of (5), i.e., (9) (xt)02+(xa1)0(xt)0+(xt0)2+(xa0)0+x2a0 1t0=0. This is a quadratic equation for (xt)0of type (5) with linear coefficient (xa1)0=a1. Moreover, writing the coefficients and (xt)0as polynomials in x2, we obtain a similar equation with the linear coefficient having degree equal to half the degree of a1. Repeating this process at most [log2(deg(a1)] times, we either obtain (5) with a constant linear term, or at some step we are in violation of the conclusion of Theorem 3 (in which case the original equation (5) has no roots). 6. Solving (5) with constant a1 The case when a1= 0 was dealt with in Section 3. So we assume now that a0a16= 0. As usual, we will reduce solving (5) over A=B[x]to solving equations over B. We set b=a1∈Band write a0=P2d i=0 cixi with ci∈B,c2d6= 0 (if deg(a0) is odd, there are no roots). Let t= Pd i=0 tixi. Collecting constant terms in (5), we obtain t2 0+bt0+c0= 0. This equation over Bis needed to find the constant term t0=t(0) of t.A method of solving it in the case of finite Bis considered at the end of this section. Polynomial Equations 139 To find the other coefficients tiof twe can proceed as in Section 2. In degree 2i>0, we have t2 i=c2iwhen d/2<i≤d. When d/4<i≤d/2, we have t2 i=c2i+bt2i, and so on. Thus, to find td,t d−1,... ,t 1we have to solve dquadratic equations over Bof the form (3). Alternatively, we can look for the unknown coefficients of tstarting from lower degrees. For each odd k, we have btk=ck(in other words, t0b=a0 0, so we have a linear equation for t0). Next bt2k=c2k+t2 kis a linear equation for t2konce we have found tk, and so on. Thus, we can find all ti,i=1,2,... ,d, by solving linear equations, all of them with linear coefficient b. In this way, neccessary conditions for existence of the root tare that certain elements of Bgiven as polynomials in given ciare divisible by b, while in the first approach, certain elements should be squares. To make it more explicit, note that our system of equations for ti,i≥1 splits into subsystems corresponding to odd numbers k≤2d. For each such k, we have the system ck2j=btk2j+t2 k2j−1for all j≥0 with tk/2= 0. This is a system of linear equations for t1/2j k2j. Thus, for each k, we obtain a neccessary condition for existence of tin the next theorem. This condition is sufficient (i.e., it implies that certain elements of Bare divisible by bor are squares) provided that the ring Bhas the following property: (10) if y∈Band y2∈b2B, then y∈bB. The condition holds, e.g., when bB =B,orBis a unique factorization domain, or Bis integrally closed in its field of fractions. Theorem 4. For the equation t2+bt +a0=0with given nonzero b∈B,a0=P2d i=0 cixi∈B[x]to have a root t∈B[x], the following two conditions must be satisfied: (a) t2 0+bt0+c0=0has a root t0∈B, (b) for every integer m≥0and every odd number ksuch that d/2m<k≤d/2m−1, (11) m X j=0 c2j k2m−jb2m+1−2j+1 =0.