AAECC DOI 10.1007/s00200-015-0254-7 ORIGINAL PAPER

On the arithmetic of the endomorphism ring End(Z p [x]/ f (x) × Z p2 [x]/ f (x) ) Yun Gao · Yonglin Cao

Received: 3 March 2014 / Revised: 28 January 2015 / Accepted: 1 February 2015 © Springer-Verlag Berlin Heidelberg 2015

Abstract Let p be a prime number, f (x) a monic basic irreducible polynomial in Z p2 [x] and f (x) = f (x) mod p. Set F = Z p [x]/ f (x) and R = Z p2 [x]/ f (x) , and denote by End(F × R) the endomorphism ring of the R-module F × R. We identify the elements of End(F × R) with elements in a new set, denoted by E p, f , of matrices of size 2 × 2, whose elements in the first row belong to F and the elements in the second row belong to R; also, using the arithmetic in F and R, we introduce the arithmetic in E p, f and prove that End(F × R) is isomorphic to the ring E p, f . Moreover, we introduce the characteristic polynomial for each element in E p, f and consider its applications. Keywords Endomorphism ring · Ring isomorphism · Invertible element · Characteristic polynomial Mathematics Subject Classification

16S50 · 16W20 · 13B25

1 Introduction and preliminary Let p be a prime number. Bergman [1] established that End(Z p × Z p2 ) is a semilocal ring with p 5 elements that cannot be embedded in matrices over any commutative ring. Climent et al. [2] identified the elements of End(Z p × Z p2 ) with elements in a new set, denoted by E p , of matrices of size 2 × 2, whose elements in the first row belong to Z p

Y. Gao · Y. Cao (B) School of Sciences, Shandong University of Technology, Zibo 255091, Shandong, China e-mail: [email protected] Y. Gao e-mail: [email protected]

123

Y. Gao, Y. Cao

and the elements in the second row belong to Z p2 ; also, using the arithmetic in Z p and Z p2 , they introduced the arithmetic in that ring and prove that the ring End(Z p × Z p2 ) is isomorphic to the ring E p . In this paper, we propose an approach following [2] to investigate the arithmetic of an extensive kind of endomorphisms rings. Let n be a fixed positive integer. For any a ∈ Z, by the integer division with remainder algorithm we obtain a unique pair (b, r ) of integers such that a = bn + r and 0 ≤ r ≤ n−1. In this paper, we denote r = a mod n and let Zn = {0, 1, . . . , n−1}. Recall that Zn is a commutative unitary ring with the addition and multiplication mod n : a + b = (a + b) mod n and a · b = ab mod n, ∀a, b ∈ Zn , where a + b and ab in the right hand side are the sum and product of a and b as integers, respectively. In this paper, we will regard Zn as a subset of Z, even though (Zn , +, ·) is not a subring of (Z, +, ·) (see [2, p. 92]). Let a(x), f (x) ∈ Z[x]. If f (x) is monic and of degree d, by the polynomial division with remainder algorithm we obtain a unique pair (q(x), r (x)) of polynomials in Z[x] such that a(x) = f (x)q(x) + r (x) where r (x) = 0 or deg(r (x)) < d. In this paper, we denote r (x) = rem(a(x), f (x), x). ring over Zn with the indeterminate x. For any Let Zn [x] be the polynomial s i ∈ Z[x] with a ∈ Z, in this paper we denote a x polynomial a(x)  = i i i=0 s i ∈ Z [x]. We will regard Z [x] as a subset a(x) mod n = (a mod n)x i n n i=0 of Z[x], even though (Zn [x], +, ·) is not a subring of (Z[x], +, ·). In fact, for any a(x), b(x) ∈ Zn [x] the sum and product of a(x) and b(x) in Zn [x] are given by a(x) + b(x) = (a(x) + b(x)) mod n and a(x) · b(x) = a(x)b(x) mod n, respectively, where a(x) + b(x) and a(x)b(x) in the right hand side are the sum and product of a(x) and b(x) as polynomials in Z[x], respectively. For any fixed monic polynomial f (x) ∈ Zn [x] of degree d ≥ 1, we can regard f (x) as a monic polynomial d−1 ai x i , ai ∈ Zn , i = in Z[x]. It is known that Zn [x]/ f (x) = {a(x) | a(x) = i=0 0, 1, . . . , d − 1}, which is a commutative unitary ring with addition and multiplication given by: for any a(x), b(x) ∈ Zn [x]/ f (x) , a(x) + b(x) = rem(a(x) + b(x), f (x), x) mod n, a(x) · b(x) = rem(a(x)b(x), f (x), x) mod n, where a(x) + b(x) and a(x)b(x) in the right hand sides are the sum and product of a(x) and b(x) as polynomials in Z[x], respectively. Notation 1.1 Let n be a positive integer and f (x) a monic polynomial in Z[x]. For simplifying notations in this paper, for any a(x) ∈ Z[x] we denote πn (a(x)) = a(x) mod n, R f (a(x)) = rem(a(x), f (x), x), Γ f,n (a(x)) = πn (R f (a(x))) = rem(a(x), f (x), x) mod n. Then the following lemma is well known from properties of rings Z[x] and Z.

123

On the arithmetic of the endomorphism ring

Lemma 1.2 For any a(x), b(x) ∈ Z[x], the following hold (i) πn (a(x) + b(x)) = πn (a(x)) + πn (b(x)) and πn (a(x)b(x)) = πn (πn (a(x)) · πn (b(x))). Hence πn is a surjective ring homomorphism from Z[x] onto Zn [x]. (ii) R f (a(x) + b(x)) = R f (a(x)) + R f (b(x)) and R f (a(x)b(x)) = R f (R f (a(x)) · R f (b(x))). Hence R f is a surjective ring homomorphism from Z[x] onto Z[x]/ f (x) . (iii) Γ f,n (a(x) + b(x)) = Γ f,n (a(x)) + Γ f,n (b(x)) and Γ f,n (a(x)b(x)) = Γ f,n (Γ f,n (a(x)) · Γ f,n (b(x))). Hence Γ f,n is a surjective ring homomorphism from Z[x] onto Zn [x]/πn ( f (x)) . Notation 1.3 From now on, let f (x) be a fixed monic basic irreducible polynomial in Z p2 [x] of degree d ≥ 1, i.e., f (x) ∈ Z p2 [x], f (x) is monic, deg( f (x)) = d and π p ( f (x)) is irreducible in Z p [x]. In this paper, we denote f (x) = π p ( f (x)), F = Z p [x]/ f (x) and R = Z p2 [x]/ f (x) . It is known that F is a finite field of cardinality p d and R is a Galois ring of characteristic p 2 and cardinality p 2d (cf. Wan [6, Theorem 14.1]). In the rest of this paper, we regard F as a subset of R, even though (F, +, ·) is not a subfield of (R, +, ·). In fact, we will regard F as the Teichmüller set of R. Then every element α of R can be uniquely expressed α = v(x) + pu(x), u(x), v(x) ∈ F.

(1)

Furthermore, α is invertible if and only if v(x) = 0, and pα = 0 if and only if α = pu(x), i.e., α is not invertible in R (cf. [6, Theorem 14.8]). Lemma 1.4 Let F × R = {(a(x), b(x)) | a(x) ∈ F, b(x) ∈ R}. Then it forms a R-module with the following addition and scalar multiplication: (a1 (x), b1 (x)) + (a2 (x), b2 (x)) = (Γ f, p (a1 (x) + a2 (x)), Γ f, p2 (b1 (x) + b2 (x))), c(x) · (a1 (x), b1 (x)) = (Γ f, p (c(x)a1 (x)), Γ f, p2 (c(x)b1 (x))), where a1 (x), a2 (x) ∈ F and b1 (x), b2 (x), c(x) ∈ R. Let ϕ be a transformation of F × R. We call ϕ an endomorphism of the R-module F × R if ϕ is R-linear, i.e., ϕ(ξ + η) = ϕ(ξ ) + ϕ(η) and ϕ(λ · ξ ) = λ · ϕ(ξ ) for all ξ, η ∈ F × R and λ ∈ R. In this paper, we denote by End(F × R) the endomorphism ring of the R-module F × R. Let  E p, f =

  a(x) b(x) | a(x), b(x), c(x) ∈ F, d(x) ∈ R , pc(x) d(x)

123

Y. Gao, Y. Cao

where pc(x) represses an element of R for any c(x) ∈ F.  Theorem 1.5 For any Ai = and di (x) ∈ R, i = 1, 2, define  A1 + A2 =  A1 · A2 =

ai (x) bi (x) pci (x) di (x)

 ∈ E p, f with ai (x), bi (x), ci (x) ∈ F

 Γ f, p (a1 (x) + a2 (x)) Γ f, p (b1 (x) + b2 (x)) , pΓ f, p (c1 (x) + c2 (x)) Γ f, p2 (d1 (x) + d2 (x))

 Γ f, p (a1 (x)b2 (x) + b1 (x)d2 (x)) Γ f, p (a1 (x)a2 (x)) . pΓ f, p (c1 (x)a2 (x) + d1 (x)c2 (x)) Γ f, p2 (d1 (x)d2 (x) + pc1 (x)b2 (x))

Then (E p, f , +, ·) is a noncommutative unitary ring. Proof The proof is straightforward.



The present paper is organized as follows. In Sect. 2, we construct a ring isomorphism from End(F × R) onto E p, f . Then we investigate the arithmetic of the ring E p, f in Sect. 3, in terms of the arithmetic of the polynomial ring Z[x] and the finite field F. In Sect. 4, we introduce the characteristic polynomial for each element in E p, f and consider its applications. 2 A characterization of the ring End(F × R) Using the notations of Sect. 1, we consider to construct a ring isomorphism from End(F × R) onto E p, f . From now on, we denote by 1 p and 1 p2 the identity of F and R, respectively. As F × R is a R-module, each of its elements can be uniquely expressed as r (x) · (1 p , 0) + s(x) · (0, 1 p2 ), r (x) ∈ F, s(x) ∈ R. Let ϕ ∈ End(F × R). As ϕ is R-linear, we have ϕ(r (x) · (1 p , 0) + s(x) · (0, 1 p2 )) = r (x) · ϕ(1 p , 0) + s(x) · ϕ(0, 1 p2 ) for all r (x), s(x) ∈ R. Therefore, ϕ is uniquely determined by two elements ϕ(1 p , 0) and ϕ(0, 1 p2 ) of F × R. Now, we assume ϕ(1 p , 0) = (a(x), w(x)) and ϕ(0, 1 p2 ) = (b(x), d(x)), where a(x), b(x) ∈ F and w(x), d(x) ∈ R. By p · a(x) = p · 1 p = 0 it follows that (0, pw(x)) = ( p · a(x), p · w(x)) = p · (ϕ(1 p , 0)) = ϕ( p · 1 p , p · 0) = (0, 0), which implies pw(x) = 0 in the Galois ring R. Hence there exists   a unique a(x) b(x) ∈ E p, f . As element c(x) ∈ F such that w(x) = pc(x). Denote Aϕ = pc(x) d(x) stated above, we conclude that Ψ : ϕ → Aϕ is well-defined and an injective mapping from End(F × R) to E p, f .

123

On the arithmetic of the endomorphism ring

Theorem 2.1 Ψ is a ring isomorphism from End(F × R) onto E p, f . 

 a(x) b(x) Proof Let A = ∈ E p, f . For any r (x), s(x) ∈ R, define ϕ(r (x) · pc(x) d(x) (1 p , 0) + s(x) · (0, 1 p2 )) = r (x) · (a(x), pc(x)) + s(x) · (b(x), d(x)). Then a straightforward computation shows that ϕ is a R-linear transformation of F × R, i.e., ϕ ∈ End(F × R), and Ψ (ϕ) = A since ϕ(1 p , 0) = (a(x), pc(x)) and ϕ(0, 1 p2 ) = (b(x), d(x)). Hence Ψ is surjective.   ai (x) bi (x) ∈ E p, f , i.e., ϕi (1 p , 0) = Now, let ϕi ∈ End(F × R) and Aϕi = pci (x) di (x) (ai (x), pci (x)) and ϕi (0, 1 p2 ) = (bi (x), di (x)), for i = 1, 2. It is clear that ϕ1 + ϕ2 , ϕ1 ϕ2 ∈ End(F × R). From (ϕ1 + ϕ2 )(1 p , 0) = ϕ1 (1 p , 0) + ϕ2 (1 p , 0) = (a1 (x), pc1 (x)) + (a2 (x), pc2 (x)) = (Γ f, p (a1 (x) + a2 (x)), Γ f, p2 ( pc1 (x) + pc2 (x))) = (Γ f, p (a1 (x) + a2 (x)), pΓ f, p (c1 (x) + c2 (x))), (ϕ1 + ϕ2 )(0, 1 p2 ) = ϕ1 (0, 1 p2 ) + ϕ2 (0, 1 p2 ) = (b1 (x), d1 (x)) + (b2 (x), d2 (x)) = (Γ f, p (b1 (x) + b2 (x)), Γ f, p2 (d1 (x) + d2 (x))) and by Theorem 1.5 we deduce that Ψ (ϕ1 + ϕ2 ) = Aϕ1 + Aϕ2 = Ψ (ϕ1 ) + Ψ (ϕ2 ). Moreover, by Lemma 1.2(iii) and Lemma 1.4 we have (ϕ1 ϕ2 )(1 p , 0) = ϕ1 (ϕ2 (1 p , 0)) = ϕ1 (a2 (x), pc2 (x)) = ϕ1 (a2 (x)(1 p , 0) + pc2 (x)(0, 1 p2 )) = a2 (x)(a1 (x), pc1 (x)) + pc2 (x)(b1 (x), d1 (x)) = (Γ f, p (Γ f, p (a2 (x)a1 (x)) + Γ f, p ( pc2 b1 (x))), Γ f, p2 (Γ f, p2 ( pa2 (x)c1 (x)) + Γ f, p2 ( pc2 (x)d1 (x)))) = (Γ f, p (a1 (x)a2 (x)), pΓ f, p (c1 (x)a2 (x) + d1 (x)c2 (x))), (ϕ1 ϕ2 )(0, 1 p2 ) = ϕ1 (ϕ2 (0, 1 p2 )) = ϕ1 (b2 (x), d2 (x)) = ϕ1 (b2 (x)(1 p , 0) + d2 (x)(0, 1 p2 )) = b2 (x)(a1 (x), pc1 (x)) + d2 (x)(b1 (x), d1 (x)) = (Γ f, p (Γ f, p (b2 (x)a1 (x)) + Γ f, p (d2 (x)b1 (x))), Γ f, p2 (Γ f, p2 ( pb2 (x)c1 (x)) + Γ f, p2 (d2 (x)d1 (x)))) = (Γ f, p (a1 (x)b2 (x) + b1 (x)d2 (x)), Γ f, p2 (d1 (x)d2 (x) + pc1 (x)b2 (x))). From these and by Theorem 1.5 we deduce that Ψ (ϕ1 ϕ2 ) = Aϕ1 · Aϕ2 = Ψ (ϕ1 )·Ψ (ϕ2 ).

Hence Ψ is a ring isomorphism from End(F × R) onto E p, f . From now on, we identify the elements of End(F × R) with elements of E p, f , and the arithmetic of End(F × R) with the arithmetic of E p, f .

123

Y. Gao, Y. Cao

Corollary 2.2 The number of elements in E p, f is p 5d . Proof |E p, f | = |F|3 |R| = ( p d )3 p 2d = p 5d by the definition of E p, f .



3 The arithmetic of the ring E p, f In this section, we consider the arithmetic of E p, f . As we have already mentioned earlier in Sect. 1, we can regarded both F and R as subsets of Z[x]; in particular, F = {Γ f, p (a(x)) | a(x) ∈ Z[x]} and R = {Γ f, p2 (a(x)) | a(x) ∈ Z[x]}. By Eq. (1) in Sect. 1, the map Υ : F × F → R defined by Υ (v(x), u(x)) = v(x) + pu(x), ∀v(x), u(x) ∈ F ⊆ Z[x] is a bijection. But Υ is not a ring isomorphism from the direct product ring F × F onto the Galois ring R, see the following. Lemma 3.1 Let di (x) = vi (x) + pu i (x) ∈ R with vi (x), u i (x) ∈ F ⊆ Z[x], for i = 1, 2. In R the following hold. (i) d1 (x) + d2 (x) = v(x) + pu(x) where v(x) = π p (v1 (x) + v2 (x)) and u(x) = π p (u 1 (x) + u 2 (x) + (v1 (x)+v2p(x))−v(x) ) in F. (ii) d1 (x) · d2 (x) = w0 (x) + pw1 (x) where w0 (x) = Γ f, p (v1 (x)v2 (x)) and w1 (x) = Γ f, p (v1 (x)u 2 (x) + u 1 (x)v2 (x) +

R f (v1 (x)v2 (x)−w0 (x)) ) p

in F.

Proof (i) From the definition of v(x) and u(x) we deduce that v(x), u(x) ∈ F, v1 (x) + v2 (x) = v(x) + pr (x) ∈ Z[x] for some r (x) ∈ Z[x] and u 1 (x)+u 2 (x)+r (x) = u 1 (x)+u 2 (x)+

v1 (x)+v2 (x)−v(x) = u(x)+ ps(x) p

for some s(x) ∈ Z[x]. Therefore, as polynomials in Z[x] we obtain d1 (x) + d2 (x) = v1 (x) + v2 (x) + p(u 1 (x) + u 2 (x)) = v(x) + pr (x) + p(u(x) + ps(x) − r (x)) = v(x) + pu(x) + p 2 s(x). Hence d1 (x) + d2 (x) = Γ f, p2 (d1 (x) + d2 (x)) = v(x) + pu(x) in R by Lemma 1.2(iii). (ii) By the definition of w0 (x) and w1 (x) it follows that w0 (x), w1 (x) ∈ F, v1 (x)v2 (x) = w0 (x) + r1 (x) f (x) + ps1 (x) ∈ Z[x] for some r1 (x), s1 (x) ∈ Z[x], where deg(s1 (x)) < d, and hence ps1 (x) = R f (v1 (x)v2 (x) − w0 (x)). So v1 (x)u 2 (x) + u 1 (x)v2 (x) + s1 (x) R f (v1 (x)v2 (x) − w0 (x)) = v1 (x)u 2 (x) + u 1 (x)v2 (x) + p = w1 (x) + r2 (x) f (x) + ps2 (x)

123

On the arithmetic of the endomorphism ring

for some r2 (x), s2 (x) ∈ Z[x]. Therefore, as polynomials in Z[x] we obtain d1 (x)d2 (x) = v1 (x)v2 (x) + p(v1 (x)u 2 (x) + u 1 (x)v2 (x)) + p 2 u 1 (x)u 2 (x) = w0 (x) + r1 (x) f (x) + ps1 (x) + p 2 u 1 (x)u 2 (x) + p(w1 (x) + r2 (x) f (x) + ps2 (x) − s1 (x)) = w0 (x) + pw1 (x) + (r1 (x) + pr2 (x)) f (x) + p 2 h(x). where h(x) = s2 (x) + u 1 (x)u 2 (x) ∈ Z[x]. So d1 (x) · d2 (x) = Γ f, p2 (d1 (x)d2 (x))

= w0 (x) + pw1 (x) in R by Lemma 1.2(iii). By Lemma 3.1, it is easy to compute addition and multiplication of the elements in R using only arithmetic in Z[x]. Next we provide the way to compute the inverse of each invertible element of R using only arithmetic in Z[x] and the finite field F by the following lemma. Lemma 3.2 Let d(x) = v(x) + pu(x) ∈ R, v(x), u(x) ∈ F. Then d(x) is invertible in R if and only if v(x) = 0, and in this case the inverse d(x)−1 of d(x) in R is given by −1

d(x)

= v(x)

−1

  R f (v(x)v(x)−1 − 1) −1 2 −1 , · v(x) + pΓ f, p −u(x)(v(x) ) − p

where v(x)−1 is the inverse of v(x) in F and we regard v(x)−1 as a polynomial belong to Z[x] in the right hand side. Proof The statement that d(x) is invertible in R if and only if v(x) = 0 follows from Galois ring theory as we have already mentioned earlier in Sect. 1. Now, we assume v(x) = 0 in the following. Since 0 = v(x) ∈ F, there is a unique inverse v(x)−1 of v(x) such that v(x)v(x)−1 = 1 in F. Denote a(x) = v(x)−1 ∈ F and regard it as a polynomial in Z[x]. Then Γ f, p (v(x)a(x)) = 1, which implies that v(x)a(x)−1 = r (x) f (x)+ ps(x) for some r (x), s(x) ∈ Z[x] satisfying deg(s(x)) < d. From this we deduce s(x) =

R f (v(x)a(x) − 1) . p

(2)

As polynomials in Z[x], by d(x) = v(x) + pu(x) it follows d(x)a(x) = v(x)a(x) + pu(x)a(x) = 1 + r (x) f (x) + p(s(x) + u(x)a(x)). Denote w(x) = 1 + r (x) f (x) − p(s(x) + u(x)a(x)). Multiplying w(x) to two sides of the above equation, we obtain d(x)a(x)w(x) = (1 + r (x) f (x))2 − p 2 (s(x) + u(x)a(x))2 .

123

Y. Gao, Y. Cao

Then by Lemma 1.2(iii) and Eq. (2), we have d(x) · Γ f, p2 (a(x)w(x)) = Γ f, p2 (d(x)a(x)w(x)) = 1 in R, which implies d(x)−1 = Γ f, p2 (a(x)w(x)) = Γ f, p2 (a(x) + a(x)r (x) f (x) − p(s(x)a(x) + u(x)a(x)2 )) = a(x) + p(Γ f, p (−u(x)a(x)2 − s(x)a(x))).

Now, we consider the arithmetic of the ring E p, f using only arithmetic of Z[x] and F. First, by Lemma 3.1 and the definitions of addition and multiplication in Theorem 1.5 we have the following corollary.   bi (x) ai (x) ∈ E p, f with ai (x), bi (x), Corollary 3.3 For any Ai = pci (x) vi (x) + pu i (x) ci (x), vi (x), u i (x) ∈ F, i = 1, 2, the following hold.  A1 + A2 =

π p (a1 (x) + a2 (x)) π p (b1 (x) + b2 (x)) pπ p (c1 (x) + c2 (x)) g(x) + ph(x)



where g(x) = π p (v1 (x) + v2 (x)) and h(x) = π p (u 1 (x) + u 2 (x) + (v1 (x)+v2p(x))−g(x) ), and   Γ f, p (a1 (x)b2 (x) + b1 (x)v2 (x)) Γ f, p (a1 (x)a2 (x)) A1 · A2 = v(x) + pu(x) pΓ f, p (c1 (x)a2 (x) + v1 (x)c2 (x)) where v(x) = Γ f, p (v1 (x)v2 (x)), and u(x) = π p (w(x) + Γ f, p (c1 (x)b2 (x))) in which w(x) = Γ f, p (v1 (x)u 2 (x) + u 1 (x)v2 (x) +

R f (v1 (x)v2 (x)−v(x)) ). p

Next we determine the invertible elements in E p, f and consider how to calculate the inverse of each invertible element effectively.   a(x) b(x) Theorem 3.4 Let M = ∈ E p, f with a(x), b(x), c(x), v(x), pc(x) v(x) + pu(x) u(x) ∈ F. Then M is invertible if and only if a(x) = 0 and v(x) = 0, and in this case the inverse M −1 of M in E p, f is given by M −1 =



Γ f, p (−a(x)−1 b(x)v(x)−1 ) a(x)−1 −1 −1 v(x)−1 + pw(x) pΓ f, p (−v(x) c(x)a(x) )

 (3)

where w(x) = Γ f, p (c(x)a(x)−1 b(x)(v(x)−1 )2 − u(x)(v(x)−1 )2 − s(x)v(x)−1 ) ∈ F and s(x) =

R f (v(x)v(x)−1 −1) p

∈ Z[x].

∈ E p, f



 r (x) s(x) pt (x) k(x) + ph(x) with r (x), s(x), t (x), k(x), h(x) ∈ F such that M B = I where I =

Proof Assume that M is invertible. Then there exists B =

123

On the arithmetic of the endomorphism ring



 10 . From this and by Corollary 3.3 we deduce that Γ f, p (a(x)r (x)) = 1 and 01 Γ f, p (v(x)k(x)) = 1. Hence a(x) = 0 and v(x) = 0. Now, let a(x) = 0 and v(x) = 0. Then in the finite field F the inverse a(x)−1 and v(x)−1 of a(x) and v(x) exist, respectively. Assume that B ∈ E p, f being the element defined by the right hand side of  expression (3). Then by Corollary 3.3 and Lemma α β 1.2 we have M B = , where pγ η + pξ α = Γ f, p (a(x)a(x)−1 ) = 1, β = Γ f, p (a(x) · Γ f, p (−a(x)−1 b(x)v(x)−1 ) + b(x)v(x)−1 ) = Γ f, p (b(x)v(x)−1 − a(x)a(x)−1 b(x)v(x)−1 )) = 0, γ = Γ f, p (c(x)a(x)−1 + v(x)Γ f, p (−v(x)−1 c(x)a(x)−1 )) = Γ f, p (c(x)a(x)−1 − v(x)v(x)−1 c(x)a(x)−1 ) = 0, η = Γ f, p (v(x)v(x)−1 ) = 1, ξ = π p (Γ f, p (v(x)Γ f, p (c(x)a(x)−1 b(x)(v(x)−1 )2 − u(x)(v(x)−1 )2 − s(x)v(x)−1 ) + u(x)v(x)−1 + s(x)) + Γ f, p (c(x)Γ f, p (−a(x)−1 b(x)v(x)−1 ))) = Γ f, p (v(x)c(x)a(x)−1 b(x)(v(x)−1 )2 − v(x)u(x)(v(x)−1 )2 − v(x)s(x)v(x)−1 + u(x)v(x)−1 + s(x) − c(x)a(x)−1 b(x)v(x)−1 ) = 0, R (v(x)v(x)−1 −1)

where s(x) = f . And consequently M B = I . Following a similar p argument we have that B M = I . Therefore, M is invertible in E p, f and M −1 = B.

Corollary 3.5 Let U p, f be the set of all invertible elements of E p, f . Then |U p, f | = p 3d ( p d − 1)2 . Proof By Theorem 3.4, the number of invertible elements of E p, f equals |U p, f | =

|F|3 |F\{0}|2 = p 3d ( p d − 1)2 . |U

|

f Remark As |E p, = p (pp5d−1) = (1 − p1d )2 , for large values of p or d almost all of p, f | the element of E p, f are invertible. Now, we choose p = 2. For any positive integer d, it is well known that there are monic basic irreducible polynomials over Z4 of degree d (cf. [6, Theorem 13.9]). Table 1 shows the percentage of invertible elements of E 2, f for certain values of d = deg( f (x)).

d 6

3d

d

2

|E 2,d |

|U2,d | 1073741824

Percentage 1040449536

96.89941406

7

34359738368

33824964608

98.44360352

8

1099511627776

1090938470400

99.22027588

9 10

35184372088832

35047067353088

99.60975647

1125899906842624

1123701957328896

99.80478287

123

Y. Gao, Y. Cao

4 The characteristic polynomial of each element in E p, f In this section, we introduce a polynomial for each element in E p, f which annihilates this element and consider its applications.   0 Γ f, p (a(x)) . Then it For any a(x) ∈ Z[x], we define Γ (a(x)) = 0 Γ f, p2 (a(x)) is clear that Γ : a(x) → Γ (a(x)) (∀a(x) ∈ Z[x]) is a ring homomorphism from Z[x] into E p, f and that Γ (Z[x]) = {Γ (a(x)) | a(x) ∈ Z[x]} is a commutative subring of E p, f . In the rest of this paper, for any a(x) ∈ Z[x] we identify a(x) with Γ (a(x)) ∈ E p, f and denote a(x)A = Γ (a(x)) · A for all A ∈ E p, f . Let Y be an indeterminate over the ring Z[x] and Z[x][Y ] the polynomial ring over Z[x] with the indeterminate Y . Now, let M be a fixed element of E p, f . For any g(Y ) = a0 (x) + a1 (x)Y + · · · + ak (x)Y k ∈ Z[x][Y ] with a0 (x), a1 (x), . . . , ak (x) ∈ Z[x], we define g(M) = a0 (x)I + a1 (x)M + · · · + ak (x)M k ∈ E p, f , where I is the multiplicative identity of E p, f .   a(x) b(x) Theorem 4.1 Let M = ∈ E p, f with a(x), b(x), c(x) ∈ F and d(x) ∈ pc(x) d(x) R. Assume r (x) = π p2 (−a(x) − d(x)), s(x) = Γ f, p2 (a(x)d(x) − pb(x)c(x)) ∈ R and denote χ M (Y ) = s(x) + r (x)Y + Y 2 ∈ (R)[Y ] ⊆ Z[x][Y ]. Then χ M (M) = s(x)I2 + r (x)M + M 2 = 0.  Proof Assume that χ M (M) = s(x)I2

+r (x)M + M 2

=

 α β . Then by Lemma 1.2 pγ δ

it follows that α = Γ f, p (Γ f, p (s(x)) + Γ f, p (r (x)a(x)) + Γ f, p (a(x)2 + pb(x)c(x))) = Γ f, p (a(x)d(x) − pb(x)c(x) − a(x)2 − d(x)a(x) + a(x)2 + pb(x)c(x)) = 0; β = Γ f, p (Γ f, p (−a(x)b(x) − d(x)b(x)) + Γ f, p (a(x)b(x) + b(x)d(x))) = 0; γ = Γ f, p (Γ f, p (−a(x)c(x) − d(x)c(x)) + Γ f, p (a(x)c(x) + d(x)c(x))) = 0; δ = Γ f, p2 (Γ f, p2 (a(x)d(x) − pb(x)c(x)) + Γ f, p2 (−a(x)d(x) − d(x)2 ) + Γ f, p2 (d(x)2 + pb(x)c(x))) = 0. Therefore χ M (M) = 0 in E p, f .



In the notations of Theorem 4.1, we call χ M (Y ) the characteristic polynomial of M ∈ E p, f over the Galois ring R or the ring Z[x]. By use of the characteristic polynomial of M, we can simplify the computations of g(M) for any g(Y ) ∈ Z[x][Y ] and M −1 in E p, f .

123

On the arithmetic of the endomorphism ring

Corollary 4.2 In the notations of Theorem 4.1 and assume d(x) = v(x) + pu(x) where v(x), u(x) ∈ F. Then the following hold. (i) For any g(Y ) ∈ Z[x][Y ], by the polynomial division with remainder algorithm over Z[x][Y ] we obtain g(Y ) = p(Y )χ M (Y )+k(x)+h(x)Y where k(x), h(x) ∈ Z[x] and p(Y ) ∈ Z[x][Y ]. Assume ξ(x) = Γ f, p2 (k(x)), η(x) = Γ f, p2 (h(x)) ∈ R. Then g(M) = ξ(x)I2 + η(x)M. (ii) Let Z[x][M] = {g(M) | g(Y ) ∈ Z[x][Y ]}. Then Z[x][M] is a commutative subsemigroup of the multiplicative semigroup (E p, f , ·) and Z[x][M] = {ξ(x)I2 + η(x)M | ξ(x), η(x) ∈ R}. Hence |Z[x][M]| ≤ p 4d . (iii) Let a(x) = 0 and v(x) = 0. We calculate w(x) = Γ f, p2 (−a(x)v(x) − p(a(x)u(x) − b(x)c(x))) and the inverse w(x)−1 of w(x) in the Galois ring R. Then M −1 = ϕ(x)I2 + ψ(x)M where ϕ(x) = Γ f, p2 (w(x)−1r (x)) and ψ(x) = Γ f, p2 (w(x)−1 ). Proof (i) It follows from that p 2 M = 0 and g(M) = p(M)χ M (M) + k(x)I2 + h(x)M = k(x)I2 + h(x)M by Theorem 4.1. (ii) It follows from (i) and |R| = p 2d . (iii) By Lemma 3.2, w(x) = Γ f, p2 (−s(x)) which is invertible and its inverse w(x)−1 can be computed efficiently in R. Now, we regard w(x)−1 as a polynomial in Z[x]. By s(x)s(x)−1 = (−w(x))(−w(x))−1 = w(x)w(x)−1 = 1 in R there exist ε(x), σ (x) ∈ Z[x] such that s(x)−1 s(x) = 1+ε(x) f (x)+ p 2 σ (x). Denote N = ϕ(x)I2 +ψ(x)M. Then by Theorem 4.1 and p 2 M = f (x)M = 0 it follows that M N = M(Γ f, p2 (w(x)−1r (x))I2 + Γ f, p2 (w(x)−1 )M) = M(−s(x)−1 (r (x)I2 + M)) = −s(x)−1 (r (x)M + M 2 ) = −s(x)−1 (−s(x)I2 ) = (1 + ε(x) f (x) + p 2 σ (x))I2 = I2 . From this and by N M = M N = I2 we conclude that M −1 = N .



Cryptography primitives using more complex algebraic system rather than traditional finite cyclic groups or finite fields have been proposed in the last decade, and led to a flourishing field of researches [4] and [5]. The Diffie–Hellman key interchange protocol presented in [2] using some polynomial functions over E p defined by polynomials in Z[x] had been proved insecure by Kamal and Youssef [3]. One can consider to present a Diffie–Hellman key interchange protocol using some polynomial functions over E p, f defined by polynomials over Z[x] and cryptanalyze its security. Acknowledgments Part of this work was done when Y. Cao was visiting Chern Institute of Mathematics, Nankai University, Tianjin, China. Y. Cao would like to thank the institution for the kind hospitality. This research is supported in part by the National Natural Science Foundation of China (No. 11471255).

123

Y. Gao, Y. Cao

References 1. Bergman, G.M.: Example in PI ring theory. Isr. J. Math. 18, 257–277 (1974) 2. Climent, J.-J., Navarro, P.R.: On the arithmetic of the endomophisms ring End(Z p ×Z p2 ). Appl. Algebra Eng. Commun. Comput. 22, 91–108 (2011) 3. Kamal, A.A., Youssef, A.M.: Cryptanalysis of a key exchange protocol based on the endomorphisms ring End(Z p × Z p2 ). Appl. Algebra Eng. Commun. Comput. 23, 143–149 (2012) 4. Stickel, E.: A new method for exchanging secret keys. In: Proceedings of the Third International Conference on Information Technology and Applications (ICITA’05), pp. 426–430. Sydney, Australia (2005) 5. Tsaban, B.: Combinatorial Group Theory and Cryptograhy Bulletin (CGC Bulletin). http://u.cs.biu.ac. il/tsaban/CGC/cgc.html 6. Wan, Z.-X.: Lectures on Finite Fields and Galois Rings. World Scientific, Singapore (2003)

123