Errata et Addenda to the Third and Fourth Corrected Printings of

A Course in Computational Algebraic Number Theory by Henri Cohen (20001127 version)

Warning. The errata presented here are of course to be taken into account for the first and second printing, but the page and line numbering given here corresponds to the third and fourth printings and is quite different from that of the preceding printings.

Graduate Texts in Mathematics 138, Springer-Verlag, 1993,

Third, Corrected Printing 1996, XX + 545 pages.

ISBN 3-540-55640-0 Springer-Verlag Berlin Heidelberg New York

ISBN 0-387-55640-0 Springer-Verlag New York Berlin Heidelberg

p. VI at Shanks, add the footnote “Daniel Shanks died on September 6, 1996” p. VI middle and p. VII line 11, instead of “Francois Dress” read “François

Dress”

p. VI line -1, instead of “Jean-Francois Mestre, Francois Morain” read “Jean-François Mestre, François Morain”

p. 11 just before “Quite a different way” insert the following long text “Perhaps surprisingly, we can easily improve on Algorithm 1.2.4 by using a flex-

ible window of size at least k bits, instead of using a window of fixed size k. Indeed, it is easy to see that any positive integer N can be written in a unique way as

N = 2^{t_{0}}(a_{0} + 2^{t_{1}}(a_{1} + ⋯ + 2^{t_{e}}a_{e}))

where t_{i} ≥ k for i ≥ 1 and the a_{i} are odd integers such that 1 ≤ a_{i} ≤ 2^{k} − 1 (in Algorithm 1.2.4 we took t_{0} = 0, t_{i} = k for i ≥ 1, and 0 ≤ a_{i} ≤ 2^{k} − 1 odd or even).

As before, we can precompute g^{3}, g^{5}, …, g^{2^{k}−1} and then compute g^{N} by successive squarings and multiplications by g^{a_{i}}. To find the a_{i} and t_{i}, we use the following immediate sub-algorithm.

Sub-Algorithm 1.2.4.1 (Flexible Base 2^{k} Digits). Given a positive integer N and k ≥ 1, this sub-algorithm computes the unique integers t_{i} and a_{i} defined above. We use [N]_{b,a} to denote the integer obtained by extracting bits a through b (inclusive) of N, where bit 0 is the least significant bit.

1. [Compute t_{0}] Let t_{0} ← v_{2}(N), e ← 0 and s ← t_{0}.

2. [Compute a_{e}] Let a_{e} ← [N]_{s+k−1,s}.

3. [Compute t_{e}] Set m ← [N]_{∞,s+k}. If m = 0, terminate the sub-algorithm. Otherwise, set e ← e + 1, t_{e} ← v_{2}(m) + k, s ← s + t_{e} and go to step 2.

The flexible window algorithm is then as follows.

Algorithm 1.2.4.2 (Flexible Left-Right Base 2^{k} ). Given g ∈ G and n ∈ ℤ, this algorithm computes g^{n} in G. We write 1 for the unit element of G.

1. [Initialize] If n = 0, output 1 and terminate. If n < 0 set N ← −n and z ← g^{−1}. Otherwise, set N ← n and z ← g.

2. [Compute the a_{i} and t_{i}] Using the above sub-algorithm, compute a_{i}, t_{i} and e such that N = 2^{t_{0}}(a_{0} + 2^{t_{1}}(a_{1} + ⋯ + 2^{t_{e}}a_{e})) and set f ← e.

3. [Precomputations] Compute and store z^{3}, z^{5}, …, z^{2^{k}−1}.

4. [Loop] If f = e set y ← z^{a_{f}} otherwise set y ← z^{a_{f}} · y. Then repeat t_{f} times y ← y · y.

5. [Finished?] If f = 0, output y and terminate the algorithm. Otherwise, set f ← f − 1 and go to step 4.

We have used above the word “surprisingly” to describe the behavior of this algorithm. Indeed, it is not a priori clear why it should be any better than Algorithm 1.2.4. An easy analysis shows, however, that the average number of multiplications which are not squarings is now of the order of 2^{k−1} + lg |n|/(k + 1) (instead of 2^{k−1} + lg |n|/k in Algorithm 1.2.4), see Exercise 33. The optimal value of k is the smallest integer satisfying the inequality lg |n| ≤ (k + 1)(k + 2)2^{k−1}.

In the above example where n has 100 decimal digits, the flexible base 2^{5} algorithm takes on average (3/4)332 + 16 + 332/6 ≈ 320 multiplications, another 3% improvement. In fact, using a simple modification, in certain cases we can still easily improve (very slightly) on Algorithm 1.2.4.2, see Exercise 34.”

p. 11 line -11, instead of “the 2^{k} algorithm” read “the flexible 2^{k} algorithm” p. 17 in Algorithm 1.3.7, remove the initializations “A ← 1, B ← 0, C ← 0,

D ← 1” from step 1 and put them instead at the end of step 2

p. 45 add the following exercises. “33. Show that, as claimed in the text, the average number of multiplications which

are not squarings in the flexible left-right base 2^{k} algorithm is approximately 2^{k−1} + lg |n|/(k + 1), and that the optimal value of k is the smallest integer such that lg |n| ≤ (k + 1)(k + 2)2^{k−1}.

34. Consider the following modification to Algorithm 1.2.4.2. We choose some odd number L such that 2^{k−1} < L < 2^{k} and precompute only z, z^{3}, …, z^{L}. Show that one can write any integer N in a unique way as N = 2^{t_{0}}(a_{0} + 2^{t_{1}}(a_{1} + ⋯ + 2^{t_{e}}a_{e})) with a_{i} odd, a_{i} ≤ L, and t_{i} ≥ k − 1 for i ≥ 1, but t_{i} = k − 1 only if a_{i} > L − 2^{k−1}. Analyze the resulting algorithm and show that, in certain cases, it is slightly faster than Algorithm 1.2.4.2.” p. 52 line -1, instead of “column” read “column, with k + 1 ≤ i ≤ n” p. 69 step 4 of Algorithm 2.4.5, instead of “set k ← k + 1 and go to step 5”

read “set k ← k + 1, and if l > 1 and i = l set l ← l − 1, then go to step 5”

p. 72 line 4 of step 4 of Algorithm 2.4.8, instead of “W_{j} ← W_{j} − qW_{i}” read “W_{j} ← W_{j} − qW_{i} mod R”

p. 73 line -3, instead of “last n − r + 1” read “last n − r” p. 129 line 4, instead of “p = 2” read “p > 2” p. 129 line -20, instead of “U ∘ T ” read “U ∘ T mod A” p. 156 line -17, instead of “A_{1}(b) < 0 when” read “A_{1}(b) < 0 if and only if” p. 157 line -8, instead of “Proposition 4.8.6” read “Theorem 4.8.6” p. 159 line -5, instead of “r_{i,k}” read “r_{k,i}” p. 159 line -4, instead of “(r_{0,k}, r_{1,k}, …, r_{n−1,k}, 1)” read “(r_{k,0}, r_{k,1}, …, r_{k,n−1}, 1)”

and instead of “r_{i,k}” read “r_{k,i}”

p. 159 line -3, instead of “r_{i,0}” read “r_{0,i}” p. 160 line 10, instead of “r_{i,j}” read “r_{k,i}”

p. 161 middle, instead of “This will in practice be considered as a r_{1} +2r_{2} = nuplet of real numbers. Now operations” read “Operations”

p. 168 line 8 and 9, instead of “p is an odd prime” read “p is a prime” p. 176 lines 12 to 15, replace the four lines of the end of the proof starting with “If we set γ...” by “It follows that the vector of the (P (β_{i}))

and of the α_{ϕ(i)} are both solutions of the linear system ∑_{1≤i≤n} v_{i}β_{i}^{h} = s_{h}, and since the β_{i} are distinct this system has a unique solution, so the vectors are equal, thus proving the proposition.”

p. 179 line -3 and p. 180 line -11, instead of “a^{m−1}” read “a^{n−1}” p. 184 line -8, instead of “so M ⊂ M′” read “so M annihilates IH/IJ hence

M ⊂ M′”

p. 193 line 11, add “Note that this is simply the proof of the Chinese remainder theorem for ideals.”

p. 195 line 2 of Algorithm 4.7.10, instead of “ℤ_{K}-generators” read “ℤ-genera-tors”

p. 195 line 1 of step 3 of Algorithm 4.7.10, instead of “2 ≤ i ≤ m” read “2 ≤ i ≤ k”

p. 195 line 2 of step 4 of Algorithm 4.7.10, instead of “j + 1 ≤ i ≤ m” read “j + 1 ≤ i ≤ k”

p. 200 line 14, instead of “e_{i} = f_{i}” read “d_{i} = e_{i}” p. 201 line -5, instead of “Then y ∉ xR and y𝔭 ⊂ xR, hence a = y/x” read

“Since y𝔭 ⊂ xR, the element a = y/x”

p. 202 line -10, instead of “ ∑_{1≤≤n}” read “ ∑_{1≤i≤n}”

p. 204 line 3 of step 3, instead of “0” read “0” p. 204 line 1 of step 5, instead of “If p ∤ A_{n,n},” read “Using Algorithm 2.4.8,

replace A by its HNF. Then, if p ∤ A_{n,n},”

p. 206 line -7, instead of “determinant d(K)” read “discriminant d(K)” p. 211 line -13 and -12, instead of “where ∥x∥ denotes the absolute value of x

when x is real and the square of the modulus of x when x is complex” read “where ∥σ(x)∥ = |σ(x)| if σ is a real embedding and ∥σ(x)∥ = |σ(x)|^{2} if σ is a complex embedding”

p. 216 line 1, instead of “\frac{1}{6}” read “\frac{1}{60}”

p. 217 line -4, instead of “A ← 8b − 3a^{2}” read “A ← 3a^{2} − 8b” and line -2, instead of “(r_{1}, r_{2}) = (0, 4) iff D > 0 and AB < 0” read “(r_{1}, r_{2}) = (0, 2) iff D > 0 and either A ≤ 0 or B ≤ 0”

p. 224 line -2, replace 4 times small parentheses by larger ones p. 227 line 1, instead of “(−b + \sqrt{D})/2a” read “(−b + \sqrt{D})/(2a)” p. 234 line -6, instead of “H(0) = −1/12” read “H(N) = −1/12” p. 237 line -13, instead of “Let D be a negative fundamental discriminant”

read “Let D be a negative discriminant (not necessarily fundamental)”

p. 237 line -10 and -9, instead of “entire function satisfying” read “entire function. If in addition D is a fundamental discriminant, this function satisfies the functional equation”

p. 240 line 4, instead of “time” read “average time” p. 246 line 7, instead of “I_{i} = a_{i}ℤ + τ_{i}ℤ” read “I_{i} = a_{i}(ℤ + τ_{i}ℤ)” p. 246 line 9, instead of “τ_{3} = ua_{1}τ_{2} + va_{2}τ_{1} + wτ_{1}τ_{2}” read “τ_{3} = (d/d_{0})(uτ_{2} +

vτ_{1} + wτ_{1}τ_{2})”

p. 248 line 2 of step 3 of Algorithm 5.4.8, instead of “c_{2} = c_{2} + gd_{1}” read “c_{2} ← c_{2} + gd_{1}”

p. 249 line 2 of step 6 of Algorithm 5.4.9, instead of “c_{3} ← v_{3}d + gd_{1}” read “c_{3} ← v_{3}f + gd_{1}”

p. 250 line -16, instead of “guess that h(D)” read “guess that, for D < −4, h(D)”

p. 252 line 7, instead of “[McCur-Haf]” read “[Haf-McCur1]” p. 262 line -5, instead of “reduced form” read “quadratic form” p. 262 line -3, after (1) insert “If (a, b, c) is reduced, then” p. 262 line -2, instead of “More precisely” read “More precisely, if (a, b, c) is

reduced”

p. 276 line -7, add a white square at the end of the line p. 280 line -6, instead of “positive norm.” read “positive norm. By abuse of

notation, we will again denote by δ(f, g) the unique representative belonging to the interval [0, R^{+}[, and similarly for the distance between ideals.”

p. 282 line -16, instead of “very small.” read “very small. More precisely, it can be proved (see [Len1]) that δ(f, ρ^{2}(f)) > ln 2, hence the number of reduction steps is at most 4 ln(D)/ ln 2.”

p. 289 line -19, instead of “δ(1, f) = (eL ln 2 + ln R)/2” read “δ(f_{0}, f) = (eL ln 2 + ln R)/2 for some fixed form f_{0} equivalent to f”

p. 290 line 20, instead of “δ(1, f)” read “δ(∏_{p≤P} f_{p}^{e_{p}}, f)” p. 290 line -6, instead of “g = ∏_{p≤P} f_{p}^{v_{p}}” read “g = ∏_{p≤P} f_{p}^{ε_{p}v_{p}}”

p. 290 line -1, instead of “f_{p_{i}}^{a_{i,j}}” read “f_{p_{i}}^{−a_{i,j}}” p. 291 line 9, instead of “a_{n+1,j} =” read “a_{n+1,j} ≡” p. 304 lines -12 and -11, instead of “again by the binomial theorem” read

“using this time the multinomial theorem instead of the binomial theorem” p. 321 step 9, instead of “s” read “f” (3 times) p. 322 step 14, instead of “r” read “s” (7 times) and instead of “d” read “r”

(3 times)

p. 340 line 3, instead of “(\overline{f}, \overline{gh}) = 1” read “(\overline{f}, \overline{g}, \overline{h}) = 1”

p. 343 line 3 of Corollary 6.4.12, instead of “\frac{−3v ± u}{6v}” read “\frac{−3v ∓ u}{6v}” p. 359 line 4 of step 5, instead of “the matrix is not of maximal rank” read

“one of the matrices H or C is not of maximal rank”

p. 368 and following major correction (oversight in all the previous printings): exchange in most places “ω_{1}” and “ω_{2}”, except p. 415 where the “ω_{2}” is correct. In particular, the canonical basis (ω_{1}, ω_{2}) for a real elliptic curve is now such that ω_{2} is real and ω_{1} is in the upper half plane. Specifically, the corrections are p. 368, p. 370, p. 378, twice p. 395, five times page 396, twice p. 398 and p. 412 replace “ω_{2}/ω_{1}” by “ω_{1}/ω_{2}”, twice p. 395 and twice p. 396 replace “2π/ω_{1}” by “2π/ω_{2}”, twice p. 396 replace “cω_{2} + dω_{1}” by “cω_{1} + dω_{2}”, twice p. 396 and p. 398 replace z/ω_{1} by z/ω_{2}, three times p. 396, six times p. 398, twice p. 399 and p. 412 replace an isolated “ω_{1}” by “ω_{2}”, twice p. 398 and five times p. 399 (but not p. 415) replace an isolated “ω_{2}” by “ω_{1}”. Although not mathematically necessary, it is then more aesthetic to replace everywhere “ℤ + ℤτ” by “ℤτ + ℤ”.

p. 392 line -16, instead of “n ≥ 2” read “n ≤ 2” p. 395 line -1, add the following: “Warning. The condition m ≥ 1 in step 3

should in practice be implemented as m > 1 − ε for some small ε > 0 depending on the current accuracy. If this precaution is not taken the algorithm may loop indefinitely, and the cost is simply that the final τ may land very close to but not exactly in the standard fundamental domain, and this has absolutely no consequence for practical computations.”

p. 407 line 2 of step 3, instead of “set c ← 1” read “set c ← ν” p. 408 line 1 of step 9, instead of “a_{4}andp^{3}” read “a_{4} and p^{3}” p. 408 line 2 of step 9, instead of “a^{6}” read “a_{6}” p. 408 line 1 of step 11, instead of “X^{2}+a_{3}/p^{2}X +a_{6}/p^{4}” read “X^{2}+a_{3}/p^{2}X −

a_{6}/p^{4}”

p. 408 line -1, instead of “c ← 1 T ← II^{∗}” read “c ← 1, T ← II^{∗}” p. 416 line -4, instead of “f_{1}(\sqrt{D})” read “f_{1}(\sqrt{D/4})” p. 417 line 4 of Exercise 1, instead of “and b_{2} ≡ 0,... respectively” read “and

b_{2} ≡ −c_{6} (mod 12)”

p. 425 line 3 of Section 8.4, instead of “may be factor” read “may be a factor” p. 432 line 8, instead of “Proposition 8.5.3” read “Proposition 8.5.4” p. 435 line -3, instead of “corresponding to 𝔟” read “corresponding to 𝔟^{−1}” p. 436 line 1, instead of “δ(g_{1}, g) =” read “δ(g_{1}, g^{−1}) =” p. 440 line 19, instead of “It is also however also” read “It is however also” p. 440 line -10, instead of “We must show how are we going” read “We must

explain how we are going”

p. 452 line -6, instead of “max(e, k + 1))” read “max(e, k + u)) where u is as in Lemma 9.1.10”

p. 452 line -5, instead of “Proposition 9.1.8” read “Lemma 9.1.8” p. 453 middle, after “prime r dividing N” insert “(by Lemma 9.1.10 and our

choice of ℓ)”

p. 454 line -16, instead of “of order” read “of order dividing” p. 462 line 3 of the proof of Lemma 9.1.24, instead of “j_{3}(χ, χ, χ) =” read

“j_{3}(χ, χ, χ)^{γ} =”

p. 474 step 4 of Algorithm 9.2.4, instead of “(x+3y)” read “(x+3y)/2” (twice) and instead of “(x − 3y)” read “(x − 3y)/2” (twice)

p. 476 line 3 of Exercise 7. instead of “χ(x) ≠ 1” read “χ(x) ≠ 0 and 1” p. 476 Exercise 7, add the following question. “ c) Show that if χ is a primitive character modulo q which is not necessarily a

prime, we still have |τ(χ)| = \sqrt{q}.”

p. 478 line 5, instead of “ε = 0 or 1” read “ε_{k} = 0 or 1” p. 480 line 2 of the second remark, instead of “a follows” read “as follows” p. 482 lines 4, 14, 16, 19, instead of “1/2a” read “1/(2a)” p. 487 middle, instead of “t = 0 (mod N)” read “t ≡ 0 (mod N)” p. 490 line -12, instead of “we note than one can” read “we note that one can” p. 490 line -1, instead of “Pomerance ,” read “Pomerance,” p. 494 line -4, instead of “is t is the” read “if t is the” p. 499 line 9, instead of “N (a + bθ)” read “ln(N (a + bθ))” p. 500 line 19, instead of “Let V is the column” read “Let V be the column” p. 528 before [Lang1], add the following: “One can find at the URL

      http://www-cs-faculty.stanford.edu/~knuth/index.html

nearly 350 pages of corrections and additions to [Knu1], [Knu2] and [Knu3], absolutely necessary for those having the older editions of Knuth’s books. This has been incorporated in a new 3 volume set which came out in 1996.” p. 535 in [Len-Len2], instead of “nmber field” read “number field”

6

p. 538 instead of “[de Weg] de Weger B.,” read “[deWeg] B. de Weger,”