Errata: A Computational Introduction to Number Theory andAlgebra (Version 2)
Last updated: 3/28/2017
p. 45: last line of Exercise 2.41. “2pf ” should be “2pf /2 ”. [Chihong Joo, 9/9/2010]
p. 45: Exercise 2.44. First line, replace “≡ 0 (mod n)” with “= n”; last line, replace“≡ 0 (mod n/p2 )” with “= n/p2 ”. [Chihong Joo, 9/9/2010]
p. 60: line 14 of Fig. 3.1. “bi ” should be “bj ”. Note that this typo was already presentin Version 1. [Christophe Weis, 12/28/2008]
p. 63: Exercise 3.24. The statement is correct, but can be improved: the inequality“len(a) − len(b) − 1 ≤ len(q) ≤ len(a) − len(b) + 1” may be replaced by theinequality “len(a) − len(b) ≤ len(q) ≤ len(a) − len(b) + 1”. [Thai Duong,7/24/2009]
p. 64: PExercise 3.25. Again, the statement
Pkis correct, but can be improved: the valueklen(n)−kcanbereplacedbyii=1i=1 len(ni )−k+1. [Thai Duong, 7/27/2009]p. 142: Exercise 6.17.
6/23/2009]“n/ gcd(m, n)” should be “gcd(m, n)”.

[Thai Duong,p. 165: Exercise 6.53, the exercise may be done without the assumption that mG =G, and the hint as stated may not be particularly helpful. [Michael Forbes,4/16/2014]
p. 171: Theorem 7.3, first line of proof. “ab = bc implies” should be “ab = ac”.
[Hrvoje Bandov, 8/8/2010]
p. 177: Last two lines. It could be that gh = 0, in which case, we have not yet defineddeg(gh) — we define deg(0) = −∞ a few lines below, so there is a slight logicalsequencing problem here. [VS, 3/28/2017]p. 200: Line 7. “Example 7.45” should be “Example 7.54”.
1/22/2012][Michael Forbes,

p. 250: Exercise 8.43. m should be defined as m := |S|. In addition, the following
hint for part (d) may be helpful. Let N := n(n − 1)/2, and define independent
random variables Wij , where each Wij is 1 with probability m/N and 0 withprobability 1 − m/N. Set Dij = Cij Wij , and bound from below the probability
that some Dij = 1. [Michael Forbes, 4/16/2014]
p. 265: Exercise 8.64. “a family hash functions” should be “a family of hash functions”. [Michael Forbes, 4/16/2014]
p. 339: Exercise 11.18, last line. “is at least 1/t” should be “is at least 1 − 1/t”.
[Michael Forbes, 4/16/2014]1

p. 357: Line 8 of §12.7: “2 log p” should be “2(log p)2 ”. [Michael Forbes, 4/16/2014]
p. 389: line 18. “affected” should be “effected”. [VS, 11/6/2009]p. 390: line 4 of Fig. 14.1. “i ≤ m” should be “i < m”. [Artem Pelenitsyn, 12/7/2010]
p. 485: footnote. The paper by Umans has appeared in pages 481–490 of the STOC
proceedings. The paper by Kedlaya and Umans appeared in pages 146–155 of
49th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
2008. A draft of a merged version of these two papers appears on Umans’ website: www.cs.caltech.edu/~umans/research.
Their algorithms do not treat the ring as an abstract data type, but rather, work
directly on concrete representations of certain finite rings (including most finite
fields of practical interest). Using fast algorithms for polynomial and integerarithmetic, their algorithm solves the modular composition problem over a finite
field of order q in time (i.e., bit complexity) O(`1+o(1) ·len(q)1+o(1) ). The resulting
algorithm for computing minimal polynomials over a finite field of order q (seefootnote, p. 508) runs in time O(`1+o(1) · len(q)1+o(1) ). The resulting polynomial
factorization algorithm (see footnote, p. 547) factors a polynomial of degree `over a finite field of order q in timeO (`1.5+o(1) + `1+o(1) len(q)) · len(q)1+o(1) .
[VS, 1/15/2009]p. 535: Third line from end of proof, in the line beginning E[Lij ] = · · ·, the index on
the second summation should be n, rather than i. [Elena Kirshanova, 10/2/2014]2