nomial. In the ring Z[X, Y] we have

a = (5X2 ’ 3X + 4)Y + (2X2 + 1)

= 5X2 Y + 2X2 ’ 3XY + 4Y + 1

= (5Y + 2)X2 + (’3Y)X + (4Y + 1).

We have Deg(a) = 3, degX (a) = 2, and degY (a) = 1. 2

More generally, if X1 , . . . , Xn are indeterminates, we can form the ring

230 Rings

R[X1 , . . . , Xn ] of multi-variate polynomials in n variables over R. For-

mally, we can think of this ring as R[X1 ][X2 ] · · · [Xn ]. Any multi-variate poly-

nomial can be expressed uniquely as the sum of monomials of the form

cXe1 · · · Xen for non-zero c ∈ R and non-negative integers e1 , . . . , en ; the total

n

1

degree of such a monomial is de¬ned to be i ei , and the total degree of

a multi-variate polynomial a, denoted Deg(a), is de¬ned to be the maxi-

mum degree of its monomials. As above, for a, b ∈ R[X1 , . . . , Xn ], we have

Deg(ab) ¤ Deg(a) + Deg(b), while equality always holds if R is an integral

domain.

Just as for bivariate polynomials, the order of the indeterminates is not

important, and for any i = 1, . . . , n, one can naturally view any a ∈

R[X1 , . . . , Xn ] as a polynomial in Xi over the ring R[X1 , . . . , Xi’1 , Xi+1 , . . . , Xn ],

and de¬ne degXi (a) to be the degree of a when viewed in this way. Anal-

ogously, one can formally di¬erentiate a with respect to any variable Xi ,

obtaining the “partial” derivative DXi (a).

Just as polynomials in a single variable de¬ne polynomial functions, so do

polynomials in several variables. If R is a subring of E, a ∈ R[X1 , . . . , Xn ],

and ± = (±1 , . . . , ±n ) ∈ E —n , we de¬ne a(±) to be the element of E ob-

tained by evaluating the expression obtained by substituting ±i for Xi in a.

Theorem 9.10 carries over directly to the multi-variate case.

Exercise 9.22. Let R be a ring, and let ±1 , . . . , ±n be elements of R. Show

that any polynomial a ∈ R[X1 , . . . , Xn ] can be expressed as

a = (X1 ’ ±1 )q1 + · · · + (Xn ’ ±n )qn + r,

where q1 , . . . , qn ∈ R[X1 , . . . , Xn ] and r ∈ R. Moreover, show that the

value of r appearing in such an expression is uniquely determined (by a

and ±1 , . . . , ±n ).

Exercise 9.23. This exercise generalizes Theorem 9.14. Let D be an inte-

gral domain, and let a ∈ D[X1 , . . . , Xn ], with Deg(a) = k ≥ 0. Let T be a

¬nite subset of D. Show that the number of elements ± ∈ T —n such that

a(±) = 0 is at most k|T |n’1 .

Exercise 9.24. Let F be a ¬nite ¬eld of cardinality q, and let t be a positive

integer. Let A := F —t and Z := F . Use the result of the previous exercise to

construct a family H of hash functions from A to Z that is an O(len(t)/q)-

forgeable message authentication scheme, where logq |H| = len(t) + O(1).

(See §6.7.2 and also Exercise 9.12.)

9.3 Ideals and quotient rings 231

9.3 Ideals and quotient rings

De¬nition 9.18. Let R be a ring. An ideal of R is a subgroup I of the

additive group of R that is closed under multiplication by elements of R, that

is, for all a ∈ I and r ∈ R, we have ar ∈ I.

Expanding the above de¬nition, we see that a non-empty subset I of R is

an ideal of R if and only if for all a, b ∈ I and r ∈ R, we have

a + b ∈ I, ’a ∈ I, and ar ∈ I.

Observe that the condition ’a ∈ I is redundant, as it is implied by the

condition ar ∈ I with r = ’1R . Note that in the case when R is the ring Z,

this de¬nition of an ideal is consistent with that given in §1.2.

Clearly, {0R } and R are ideals of R. From the fact that an ideal I is

closed under multiplication by elements of R, it is easy to see that I = R if

and only if 1R ∈ I.

Example 9.30. For m ∈ Z, the set mZ is not only a subgroup of the

additive group Z, it is also an ideal of the ring Z. 2

Example 9.31. For m ∈ Z, the set mZn is not only a subgroup of the

additive group Zn , it is also an ideal of the ring Zn . 2

Example 9.32. In the previous two examples, we saw that for some rings,

the notion of an additive subgroup coincides with that of an ideal. Of

course, that is the exception, not the rule. Consider the ring of polynomial

R[X]. Suppose a is a non-zero polynomial in R[X]. The additive subgroup

generated by a consists of polynomials whose degrees are at most that of a.

However, this subgroup is not an ideal, since any ideal containing a must

also contain a · Xi for all i ≥ 0, and must therefore contain polynomials of

arbitrarily high degree. 2

Let a1 , . . . , ak be elements of a ring R. Then it is easy to see that the set

a1 R + · · · + ak R := {a1 r1 + · · · + ak rk : r1 , . . . , rk ∈ R}

is an ideal of R, and contains a1 , . . . , ak . It is called the ideal of R gener-

ated by a1 , . . . , ak . Clearly, any ideal I of R that contains a1 , . . . , ak must

contain a1 R + · · · + ak R, and in this sense, a1 R + · · · + ak R is the smallest

ideal of R containing a1 , . . . , ak . An alternative notation that is often used

is to write (a1 , . . . , ak ) to denote the ideal generated by a1 , . . . , ak , when the

ring R is clear from context. If an ideal I is of the form aR = {ar : r ∈ R}

for some a ∈ R, then we say that I is a principal ideal.

232 Rings

Note that if I and J are ideals of a ring R, then so are I + J := {x + y :

x ∈ I, y ∈ J} and I © J (verify).

Since an ideal I of a ring R is a subgroup of the additive group R, we may

adopt the congruence notation in §8.3, writing a ≡ b (mod I) if and only if

a ’ b ∈ I.

Note that if I = dR, then a ≡ b (mod I) if and only if d | (a ’ b), and as a

matter of notation, one may simply write this congruence as a ≡ b (mod d).

Just considering R as an additive group, then as we saw in §8.3, we can

form the additive group R/I of cosets, where (a + I) + (b + I) := (a + b) + I.

By also considering the multiplicative structure of R, we can view R/I as a

ring. To do this, we need the following fact:

Theorem 9.19. Let I be an ideal of a ring R, and let a, a , b, b ∈ R. If

a ≡ a (mod I) and b ≡ b (mod I), then ab ≡ a b (mod I).

Proof. If a = a + x for x ∈ I and b = b + y for y ∈ I, then a b =

ab+ay +bx+xy. Since I is closed under multiplication by elements of R, we

see that ay, bx, xy ∈ I, and since it is closed under addition, ay +bx+xy ∈ I.

Hence, a b ’ ab ∈ I. 2

This theorem is perhaps one of the main motivations for the de¬nition of

an ideal. It allows us to de¬ne multiplication on R/I as follows: for a, b ∈ R,

(a + I) · (b + I) := ab + I.

The above theorem is required to show that this de¬nition is unambiguous.

Once that is done, it is straightforward to show that all the properties that

make R a ring are inherited by R/I ” we leave the details of this to the

reader. In particular, the multiplicative identity of R/I is the coset 1R + I.

The ring R/I is called the quotient ring or residue class ring of R

modulo I.

Elements of R/I may be called residue classes. As a matter of notation,

for a ∈ R, we de¬ne [a]I := a + I, and if I = dR, we may write this simply

as [a]d . If I is clear from context, we may also just write [a].

Example 9.33. For n ≥ 1, the ring Zn is precisely the quotient ring Z/nZ.

2

Example 9.34. Let f be a monic polynomial over a ring R with deg(f ) =

≥ 0, and consider the quotient ring E := R[X]/f R[X]. By the division with

remainder property for polynomials (Theorem 9.12), for every a ∈ R[X],

there exists a unique polynomial b ∈ R[X] such that a ≡ b (mod f ) and

9.3 Ideals and quotient rings 233

deg(b) < . From this, it follows that every element of E can be written

uniquely as [b]f , where b ∈ R[X] is a polynomial of degree less than .

The assumption that f is monic may be relaxed a bit: all that really

matters in this example is that the leading coe¬cient of f is a unit, so that

the division with remainder property applies. Also, note that in this situa-

tion, we will generally prefer the more compact notation R[X]/(f ), instead

of R[X]/f R[X]. 2

Example 9.35. Consider the polynomial f := X2 + X + 1 ∈ Z2 [X] and the

quotient ring E := Z2 [X]/(f ). Let us name the elements of E as follows:

00 := [0]f , 01 := [1]f , 10 := [X]f , 11 := [X + 1]f .

With this naming convention, addition of two elements in E corresponds to

just computing the bit-wise exclusive-or of their names. More precisely, the

addition table for E is the following:

+ 00 01 10 11