This introductory book emphasizes algorithms and applications, such as cryptography and error correcting codes, and is accessible to a broad audience. The presentation alternates between theory and applications in order to motivate and illustrate the mathematics. The mathematical coverage includes the basics of number theory, abstract algebra and discrete probability theory. This edition now includes over 150 new exercises, ranging from the routine to the challenging, that flesh out the material presented in the body of the text, and which further develop the theory and present new applications. The material has also been reorganized to improve clarity of exposition and presentation. Ideal as a textbook for introductory courses in number theory and algebra, especially those geared towards computer science students.

suﬃciently large x (read, “f is big-O of g”), • f = Ω(g) means that f (x) ≥ cg(x) for some positive constant c and all suﬃciently large x (read, “f is big-Omega of g”), • f = Θ(g) means that cg(x) ≤ f (x) ≤ dg(x), for some positive constants c and d and all suﬃciently large x (read, “f is big-Theta of g”), • f = o(g) means that f /g → 0 as x → ∞ (read, “f is little-o of g”), and • f ∼ g means that f /g → 1 as x → ∞ (read, “f is asymptotically equal to g”). Example 3.1. Let f (x) := x2 and g(x) :=

some trivial aspects of our data structure for representing large integers. For example, it is clear that in constant time, we can determine the sign of a given integer a, the bit length of a, and any particular bit of the binary representation of a; moreover, as discussed in Exercises 3.17 and 3.18, multiplications and divisions by powers of 2 can be computed in linear time via “left shifts” and “right shifts.” It is also clear that we can convert between the base-2 representation of a given

B (i.e., A ⊆ B but A = B); further, A ∪ B denotes the union of A and B, A ∩ B the intersection of A and B, and A \ B the set of all elements of A that are not in B. For sets S1 , . . . , Sn , we denote by S1 × · · · × Sn the Cartesian product xiv Preliminaries xv of S1 , . . . , Sn , that is, the set of all n-tuples (a1 , . . . , an ), where ai ∈ Si for i = 1, . . . , n. We use the notation S ×n to denote the Cartesian product of n copies of a set S, and for x ∈ S, we denote by x×n the

examine an even more specialized case of the above situation. Suppose that X1 , . . . , Xn are pairwise independent random variables, each of which takes the value 1 with probability p, and 0 with probability q := 1 − p. As before, let X be the sample mean of X1 , . . . , Xn . As we calculated in 6.5 Some useful bounds 119 Example 6.22, the Xi have a common expected value p and variance pq. Therefore, by (6.17), for any > 0, we have pq (6.19) P[|X − p| ≥ ] ≤ 2 . n The bound on the right-hand

1/n2 converges and the series 1/n diverges, the expectation E[X] exists, while E[X 2 ] does not. ✷ Theorems 6.6 and 6.7 hold under the additional hypothesis that E[X] and E[Y ] exist. If X1 , X2 , . . . is an inﬁnite sequence of real random variables, then the ran∞ dom variable X := ∞ i=1 Xi is well deﬁned provided the series i=1 Xi (u) ∞ converges for all u ∈ U. One might hope that E[X] = i=1 E[Xi ]; however, this is not in general true, even if the individual expectations E[Xi ] are