Errata et Addenda to the Second Corrected Printing of the Book A Course in Computational Algebraic Number Theory by Henri Cohen (19960419 version)

Graduate Texts in Mathematics 138, Springer-Verlag, 1993, Second Corrected Printing 1995, XXII + 534 pages. ISBN 3-540-55640-0 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-55640-0 Springer-Verlag New York Berlin Heidelberg

p. VII lines 1 and 2, put Serre and Stark in correct alphabetical order p. VII line -1, instead of “Vallee” read “Vallée” p. XII line 20, instead of “being is” read “being” p. XII lines -4 to -2, replace text starting with “For Chapter 7,..” and ending with “prepara-

tion” by “For Chapter 7, [Sil] and [Sil3] are excellent books, and contain numerous exercises” p. 24 line 9, instead of “result” read “results” p. 30 line 4, instead of “step 2” read “step 3” p. 30 line 6, instead of “odd value of b” read “odd value of a” p. 34 line -12, instead of “0 < x_{0} < p” read “p/2 < x_{0} < p” p. 39 middle, instead of “The choices” read “The choice” p. 43 line 3 of Exercise 16, instead of “ℚ(ζ)” read “ℤ[ζ]” p. 43 line 5 of Exercise 16, instead of “(−1)^{(p−1)/2}” read “(−1)^{(p−1)/2}p” p. 55 line 2 of step 3, instead of “and finally set” read “set h_{i,m−1} ← 0, and finally set” p. 57 line 5, instead of “exists” read “exist” p. 68 line 4, instead of “l = 1” read “l ← 1” and instead of “l = m−n+1” read “l ← m−n+1” p. 73 line -1, instead of “lowest” read “least” p. 102 line 15, after “linear algebra algorithms” insert “(over ℝ and not over ℤ)” p. 108 line -6, instead of “need, use” read “need use” p. 124 line -9, instead of “V_{k+1} = V_{k} if p ∤ k” read “V_{k+1} = V_{k} if p | k” p. 150 Addendum. Add the following exercise.

“31. Let A(X) = a_{n}X^{n} + ⋯ + a_{1}X + a_{0} be a polynomial such that a_{n} ≠ 0. Show that

disc(A(X^{k})) = (−1)^{nk(k+3)/2}k^{nk}(a_{n}a_{0})^{k−1} disc(A)^{k} .′′

p. 151 line 4, instead of “[Sam] however these have” read “[Sam]. However, they usually have” p. 156 line -3, instead of “subring ℤ[α]” read “subfield ℚ(α)” p. 156 line -1, instead of “subring” read “subfield” p. 162 line 5, instead of “ℤ[X],” read “ℤ[X] of degree n,” p. 168 line 14, instead of “method shows” read “method show” p. 171 line -15, instead of “degree I have” read “degree, I have” p. 181 line -9, instead of “take R = · · ·. Then” read “let ω = (1 + \sqrt{−7})/2, take R = ℤ + 3ωℤ

and I = J = 3ℤ + 3ωℤ. Then”

p. 182 line 1, instead of “We will prove” read “Assume for example that I is invertible. We will prove”

p. 185 line 4, instead of “lowest” read “least” p. 190 middle, add a third item to the statement of the proposition: “(3) If α and β are in K, then I = αℤ_{K} + βℤ_{K} if and only if for every prime ideal 𝔭 we have

min(v_{𝔭}(α), v_{𝔭}(β)) = v_{𝔭}(I)

Typeset by AMS-TEX

where v_{𝔭} denotes the 𝔭-adic valuation at the prime ideal 𝔭.”

p. 191 line -17, add the proof of (3) as follows:

“For (3) recall that the sum of ideals correspond to GCD, and that the GCD is computed by taking the minimum of the 𝔭-adic valuations.”

p. 192 middle, replace everything starting with the statement of Lemma 4.7.9 until the end of the section by the following.

Lemma 4.7.9. Let 𝔭 be a prime ideal above p of norm p^{f} (f is called the residual degree of 𝔭 as we will see in the next section), and let α ∈ 𝔭. Then we have 𝔭 = (p, α) = pℤ_{K} + αℤ_{K} if and only if v_{p}(N (α)) = f or v_{p}(N (α + p)) = f, where v_{p} denotes the ordinary p-adic valuation.

Proof. This proof assumes some results and definitions introduced in the next section. Assume first that v_{p}(N (α)) = f. Then, since α ∈ 𝔭 and N (𝔭) = p^{f}, for every prime 𝔮 above p and different from 𝔭 we must have v_{𝔮}(α) = 0 otherwise 𝔮 would contribute more powers of p to N (α). In addition and for the same reason we must have v_{𝔭}(α) = 1. It follows that for any prime ideal 𝔮, min(v_{𝔮}(p), v_{𝔮}(α)) = v_{𝔮}(𝔭) and so 𝔭 = (p, α) by Proposition 4.7.7 (3).

If v_{p}(N (α + p)) = f we deduce from this that 𝔭 = pℤ_{K} + (α + p)ℤ_{K}, but this is clearly also equal to pℤ_{K} + αℤ_{K}.

Conversely, let 𝔭 = pℤ_{K} + αℤ_{K}. Then for every prime ideal 𝔮 above p and different from 𝔭 we have v_{𝔮}(α) = 0, while for 𝔭 we can only say that min(v_{𝔭}(p), v_{𝔭}(α)) = 1.

Assume first that v_{𝔭}(α) = 1. Then clearly v_{p}(N (α)) = v_{p}(N (𝔭)) = f as desired. Otherwise we have v_{𝔭}(α) > 1, and hence v_{𝔭}(p) = 1. But then we will have v_{𝔭}(α + p) = 1 (otherwise v_{𝔭}(p) = v_{𝔭}((p + α) − α) > 1), and still v_{𝔮}(α + p) = 0 for all other primes 𝔮 above p, and so v_{p}(N (α + p)) = f as before, thus proving the lemma. □

Note that the condition v_{p}(N (α)) = f, while sufficient, is not a necessary condition (see Exercise 20).

Note also that if we write α = ∑_{1≤i≤k} λ_{i}γ_{i} where the γ_{i} is some generating set of 𝔭, we may always assume that |λ_{i}| ≤ p/2 since p ∈ 𝔭. In addition, if we choose γ_{1} = p, we may assume that λ_{1} = 0.

This suggests the following algorithm, which is simple minded but works quite well.

Algorithm 4.7.10 (Two-Element Representation of a Prime Ideal). Given a prime ideal 𝔭 above p by a system of ℤ_{K}-generators γ_{i} for (1 ≤ i ≤ k), this algorithm computes a two-element representation (p, α) for 𝔭.

We assume that one knows the norm p^{f} of 𝔭 (this is always the case in practice, and in any case it can be obtained by computing the HNF of 𝔭 from the given generators), and that γ_{1} = p (if this is not the case just add it to the list of generators).

1. [Initialize] Set R ← 1.

2. [Set coefficients] For 2 ≤ i ≤ k set λ_{i} ← R.

3. [Compute α and check] Let α ← ∑_{2≤i≤m} λ_{i}γ_{i}, n ← N (α)/p^{f}, where the norm is computed, for example, using the sub-resultant algorithm (see Section 4.3). If p ∤ n, then output (p, α) and terminate the algorithm. Otherwise, set n ← N (α + p)/p^{f}. If p ∤ n then output (p, α) and terminate the algorithm.

4. [Decrease coefficients] Let j be the largest i ≤ k such that λ_{i} ≠ −R (we will always keep λ_{2} ≥ 0 so j will exist). Set λ_{j} ← λ_{j} − 1 and for j + 1 ≤ i ≤ m set λ_{i} ← R.

5. [Search for first non-zero] Let j be the smallest i ≤ k such that λ_{i} ≠ 0. If no such j exists (i.e. if all the λ_{i} are equal to 0) set R ← R + 1 and go to step 2. Otherwise go to step 3.

Remarks. 1) Steps 4 and 5 of this algorithm represent a standard backtracking procedure. What we do essentially is to search for α = ∑_{2≤i≤k} λ_{i}γ_{i}, where the λ_{i} are integers between −R and R. To avoid searching both for α and −α, we add the condition that the first non-zero λ should be positive. If the search fails, we start it again with a larger value of R. Of course, some time will be wasted since many old values of α will be recomputed, but in practice this has no real importance, and in fact R = 1 or R = 2 is usually sufficient. The remark made after Lemma 4.7.9 shows that the algorithm will stop with R ≤ p/2.

2) It is often the case that one of the γ_{i} for 2 ≤ i ≤ k will satisfy one of the conditions of step 3. Thus it is useful to test this before starting the backtracking procedure.

We refer to [Poh-Zas] for extensive information on the use of two-element representations.” p. 195 line -2, instead of “If p = ∏_{i=1}^{g} 𝔭_{i} is an unramified prime in K” read “If p is an

unramified prime in K with pℤ_{K} = ∏_{i=1}^{g} 𝔭_{i}”

p. 197 line 10, instead of “essential” read “inessential”

p. 199 line 10 and line 11, instead of “q_{j}” read “𝔮_{j}”

p. 199 middle, instead of “p^{−1} = R + aR” read “𝔭^{−1} = R + aR”

p. 201 line -4, instead of “Z[θ]” read “ℤ[θ]”

p. 203 line -4 until p. 204 line -12, replace completely by the following.

“To compute the inverse of an ideal I given by a ℤ-basis γ_{j} represented by an n × n matrix M on the integral basis as above, we thus proceed as follows. Computing T^{−1} we first obtain a basis of the codifferent 𝔡(K)^{−1}. We then compute the ideal product I𝔡(K)^{−1} by Hermite reduction of an n × n^{2} matrix as explained in Section 4.7.1. If N is the HNF matrix of this ideal product, then by Proposition 4.8.19, the columns (N^{t}T)^{−1} will form a ℤ-basis of the ideal (I𝔡(K)^{−1})^{−1}𝔡(K)^{−1} = I^{−1}, thus giving the inverse of I after another HNF. In paractice, it is better to work only with integral ideals, and since we know that det(T) = d(K), this means that we will replace 𝔡(K)^{−1} by d(K)𝔡(K)^{−1} which is an integral ideal.

This leads to the following algorithm.

Algorithm 4.8.21 (Ideal Inversion). Given an integral basis (ω_{i})_{1≤i≤n} of the ring of integers of a number field K and an integral ideal I given by an n × n matrix M whose columns give the coordinates of a ℤ-basis γ_{j} of I on the ω_{i}, this algorithm computes the HNF of the inverse ideal I^{−1}.

1. [Compute d(K)𝔡(K)^{−1}] Compute the n × n matrix T = (t_{i,j}) such that t_{i,j} = Tr_{K/ℚ}(ω_{i}ω_{j}). Set d ← det(T) (this is the determinant d(K) of K hence is usually available with the ω_{i} already). Finally, call δ_{j} the elements of ℤ_{K} whose coordinates on the ω_{i} are the columns of dT^{−1} (thus the δ_{j} will be a ℤ-basis of the integral ideal d(K)𝔡(K)^{−1}).

2. [Compute d(K)I𝔡(K)^{−1}] Let N be the HNF of the n×n^{2} matrix whose columns are the coordinates on the integral basis of the n^{2} products γ_{i}δ_{j} (the columns of N will form a ℤ-basis of d(K)I𝔡(K)^{−1}).

3. [Compute I^{−1}] Set P ← d(K)(N^{t}T)^{−1}, and let e be a common denominator for the entries of the matrix P. Let W be the HNF of eP. Output (W, e) as the HNF of I^{−1} and terminate the algorithm.

Remarks.

(1) If many ideal inversions are to be done in the same number field, step 1 should of course be done only once. In addition, it may be useful to find a two-element representation for the integral ideal d(K)𝔡(K)^{−1} since this will considerably speed up the ideal multiplication of step 2. Algorithm 4.7.10 cannot directly be used for that purpose since it is valid only for prime ideals, but similar algorithms exist for general ideals (see Exercise 30). In addition, if ℤ_{K} = ℤ[θ] and if P [X] is the minimal monic polynomial of θ, then one can prove (see Exercise 33) that 𝔡(K) is the principal ideal generated by P′(θ), so the ideal multiplication of step 2 is even simpler.

(2) If we want to compute the HNF of the different 𝔡(K) itself, we apply the above algorithm to the integral ideal d(K)𝔡(K)^{−1} (with M = d(K)T^{−1}) and multiply the resulting inverse by d(K) to get 𝔡(K).”

p. 204 (if the replacement above is not made) line -14, instead of “p_{i}” read “𝔭_{i}” p. 213 line -2, instead of “Brauer-Siegel” read “Brauer-Siegel theorem” p. 217 Addendum. Add the following exercises.

“29. Let 𝔭 be a prime ideal above the prime 2 in a number field K such that e(𝔭/2) = 2. Show

that the congruences x^{2} ≡ a (mod 𝔭^{3}) have a solution for a = −1 and a = −2.

30. Let I be an integral ideal in a number field K and let ℓ(I) be the positive generator of I ∩ ℤ.

a) Show that

ℓ(I) = ∏_{p|N (I)} p^{max_{𝔭|p}⌈v_{𝔭}(I)/e(𝔭/p)⌉} .

b) Let α ∈ I be such that (N (I), N (α)/ N (I)) = 1. Show that

I = ℓ(I)ℤ_{K} + αℤ_{K} = N (I)ℤ_{K} + αℤ_{K}

(this is a partial generalization of Lemma 4.7.9).

c) Deduce from this an algorithm for finding a two-element representation of I analogous to Algorithm 4.7.10.

31. Let 𝔭 be a prime ideal in a number field K, and denote by p the prime number below 𝔭, by e = e(𝔭/p) the ramification index, and by f = f(𝔭/p) the residual degree of 𝔭. The goal of this exercise is to find the Abelian group structure of ℤ_{K}/𝔭^{k} and also of (ℤ_{K}/𝔭^{k})^{∗} in a number of cases.

a) Let k ≥ 1 be an integer, and let k − 1 = qe + r be the Euclidean division of k − 1 by e, with 0 ≤ r < e. Show that we have the Abelian group isomorphism

ℤ_{K}/𝔭^{k} ≃ (ℤ/p^{q+1}ℤ)^{f(r+1)} × (ℤ/p^{q}ℤ)^{f(e−r−1)} .

b) Let k ≥ 1 be an integer, and let k − 2 = qe + r be the Euclidean division of k − 2 by e, with 0 ≤ r < e. Assume that p ≥ min(k, e + 2). Show that we have the Abelian group isomorphism

(ℤ_{K}/𝔭^{k})^{∗} ≃ (ℤ/(p^{f} − 1)ℤ) × (ℤ/p^{q+1}ℤ)^{f(r+1)} × (ℤ/p^{q}ℤ)^{f(e−r−1)} ,

where the left hand side is a multiplicative group and the right hand side an additive group (note that the formula for the p-part of this formula is the same as in a) but with different values of q and r).

c) Assume that e = 1, i.e. that 𝔭 is an unramified prime ideal. The above isomorphism gives the structure of (ℤ_{K}/𝔭^{k})^{∗} for p ≥ 3. Show that for p = 2,

(ℤ_{K}/𝔭^{k})^{∗} ≃ (ℤ/(p^{f} − 1)ℤ) × (ℤ/p^{k−1}ℤ)^{f−1} × ℤ/p^{k−2}ℤ × ℤ/pℤ .

d) Assume on the contrary that e is large, say e ≥ k(p − 1)/p. Set u_{m} = ⌊(k − 1)/p^{m}⌋ for all m ≥ 0, so that u_{m} = 0 for m sufficiently large. Show that

(ℤ_{K}/𝔭^{k})^{∗} ≃ (ℤ/(p^{f} − 1)ℤ) × ∏_{m≥1} (ℤ/p^{m}ℤ)^{f(u_{m−1}−2u_{m}+u_{m+1})} .

e) Assume that e is not divisible by p−1. Show that there exists an Abelian group G of order p^{k−1} such that

(ℤ_{K}/𝔭^{k})^{∗} ≃ (ℤ/(p^{f} − 1)ℤ) × G^{f} .

f) Determine the structure of (ℤ_{K}/𝔭^{k})^{∗} for 1 ≤ k ≤ 5. The results can be expressed solely as functions of p, k, e and f, and also in the case p = 3, e = 2 and 4 ≤ k ≤ 5, of ε where ε = 1 if there exists a solution of x^{2} ≡ −3 (mod 𝔭^{3}), ε = 0 otherwise.

32. Given a prime ideal 𝔭 in a number field K and a positive integer k, write an algorithm which computes the Abelian group structure of (ℤ_{K}/𝔭^{k})^{∗} as a product of cyclic groups.

33. Let K = ℚ[θ] be a number field, where θ is an algebraic integer whose minimal monic polynomial is P (X) ∈ ℤ[X]. Assume that ℤ_{K} = ℤ[θ]. Show that the different 𝔡(K) is the principal ideal generated by P′(θ).

34. Let I and J be two integral ideals in a number field K given by their HNF matrices M_{I} and M_{J}. Assume that I and J are coprime, i.e. that I + J = ℤ_{K}. Give an algorithm which finds i ∈ I and j ∈ J such that i + j = 1.

35. a) Using the preceding exercise, give an algorithm wich finds explicitly the element β ∈ ℤ_{K}

whose existence is proven in Proposition 4.7.8.

b) Deduce from this an algorithm which finds a two-element representation I = αℤ_{K} + βℤ_{K} of an integral ideal I given a non-zero element α ∈ I.

c) In the case where α = ℓ(I), compare the theoretical and practical performance of this algorithm with the one given in Exercise 30.

36. Let W = (w_{i,j})_{1≤i,j≤n} be the (upper triangular) n × n Hermite Normal Form matrix of a prime ideal 𝔭 on some integral basis ω_{i} (so there is no denominator) where we assume as usual that ω_{1} = 1, let p be the prime number below 𝔭 and let f = f(𝔭/p) be the residual index of 𝔭.

a) Show that the diagonal of W has only 1 and p, with exactly f occurences of p, and that w_{1,1} = p and w_{n,n} = 1.

b) If w_{j,j} = 1, we already know that all other elements w_{j,k} of the same row are equal to zero. Show that if w_{j,j} = p, all other elements w_{i,j} of the same column are equal to zero (hint: note that pω_{j} ∈ 𝔭 and induct on i).

37. Modify Proposition 4.3.4 so that it is still valid when T (X) ∈ ℚ[X] and not necessarily monic.” p. 218 line -3, instead of “Corollary 4.4.6” read “Corollary 4.4.7” p. 229 lines 2-3, instead of “Appendix C” read “Appendix B” p. 229 line 11, instead of “−127, … ” read “−127, …, −2683.” p. 229 line 13, instead of “−251, … ” read “−251, …, −5923.” p. 229 line 19 to 21, instead of “but to my knowledge... 1 and 2)” read “but the explicit

computations have been carried to the end only for class numbers 1, 2, 3, 4 and all odd numbers up to 23 (see [ARW])”

p. 229 line -12, instead of “enables” read “enable” p. 235 line -20, instead of “whether it is not in” read “whether or not it is in” p. 236 line 2 of Step 3, instead of “go to step 7” read “go to step 6” p. 237 line 8, instead of “lowest” read “least” p. 243 line 2 of step 4 of Algorithm 5.4.8, instead of “step 2” read “step 3” p. 243 step 3 of Algorithm PARTEUCL, instead of “Let q ← ⌊d/v_{3}⌋ and simultaneously

t_{3} ← d mod v_{3}” read “Let d = qv_{3} + t_{3} be the Euclidean division of d by v_{3} with 0 ≤ t_{3} < |v_{3}|” p. 278 line 3, instead of “|(b + \sqrt{D})/(b − \sqrt{D})” read “|(b + \sqrt{D})/(b − \sqrt{D})|”

p. 283 line -11, instead of “the real part of Δ_{C} lies in the hyperplane ∑_{i} x_{i} = 0” read “the sum of the r_{1} + r_{2} components of Δ_{C} is an integral multiple of 2iπ”

p. 285 lines -9 to page 286 line 9, replace completely by the following:

“We thus obtain a matrix A = (a_{i,j}) with n + 1 rows and k columns, whose entries in the first n rows are integers and the entries in the last row are real numbers. Note that by definition, for every j ≤ k we have

δ (1, ∏_{1≤i≤n} f_{p_{i}}^{a_{i,j}} ) ≡ a_{n+1,j} (mod R(D)) .

Since the distance function that we have chosen is exactly additive, it follows that when performing column operations on the complete matrix A, this relation between the n + 1-st component and the others is preserved.

Hence we apply Hermite reduction to the matrix formed by the first n rows, but performing the corresponding column operations also the entries of the last row. The first k − n columns of the resulting matrix will thus have only zero entries, except perhaps for the entry in the n + 1-st row. By the remark made above, for 1 ≤ j ≤ k − n we will thus have

a_{n+1,j} = δ(1, 1) ≡ 0 (mod R(D)) ,

in other words a_{n+1,j} is equal to a multiple of the regulator R(D) for 1 ≤ j ≤ k − n.

If k is large enough, it follows that in a certain sense the GCD of the a_{n+1,j} for 1 ≤ j ≤ k − n should be exactly equal to R(D). We must be careful in the computation of this “GCD” since we are dealing with inexact real numbers. For this purpose, we can either use the LLL algorithm which will give us a small linear combination of the a_{n+1,j} for 1 ≤ j ≤ k − n with integral coefficients, which should be the regulator R(D), or use the “real GCD” Algorithm 5.9.3 as described below.”

p. 290 lines 12, instead of “55” read “K” and instead of “∏_{p|D}” read “∏_{p|D}^{∗}”

p. 290 lines 13-14, instead of “if (D, 5077) = 1 (see [Oes] for a general result), which is” read “where K = 55 if (D, 5077) = 1 and K = 7000 otherwise, and the star indicates that the product is taken over all prime divisors p of D with the exception of the largest prime divisor (see [Oes]). This is of course”

p. 292 line -14, instead of “the similarly” read “similarly”

p. 293 end of Exercise 5, instead of “and to my knowledge...assumption” read “the complete result without the randomness assumption has only recently been proved by Duke [Duk].”

p. 293 line -1, instead of “in terms of” read “as a function of”

p. 294 line 1 of Exercise 11, instead of “integers” read “integers, and assume that at most one of them is equal to zero”

p. 302 line 8, instead of “lowest” read “least”, and remove “(lcm)”

p. 302 line 9, instead of “PID” read “PID,”

p. 313 line 15, instead of “lowest” read “least”

p. 319 middle, replace “ℤ/3ℤ” by “C_{3}” and “(A_{3}, +)” by “(C_{3}, +)”

p. 328 line 5, instead of “X^{6} +10X^{5} +55X^{4} +140X^{3} +175X^{2} +170X +25” read “X^{6} −2X^{5} − 5X^{2} − 2X − 1”

p. 328 line 7, instead of “X^{6} + 10X^{5} + 55X^{4} + 140X^{3} + 175X^{2} − 3019X + 25” read “X^{6} − X^{5} − 10X^{4} + 30X^{3} − 31X^{2} + 7X + 9”

p. 339 line 6, instead of “we take in step 9” read “in step 9 we take”

p. 342 Corollary 6.4.15, in (3) and in (4), instead of “If p ≡ 1 (mod 3)” read “If p ∤ a, p ≡ 1 (mod 3)”, and in (5) instead of “If p = 3” read “If p = 3 and p ∤ a”

p. 346 line 8, instead of “are prime ideals” read “are distinct prime ideals” p. 354 line 3 of (4), instead of “g_{i}” read “\overline{g_{i}}” (twice) p. 355 line 2 of Algorithm 6.5.10, instead of “computes and” read “computes an” p. 356 line 2 of Step 9, instead of “in K),” read “in K). If I ≠ αℤ_{K}, output an error message

stating that the accuracy is not sufficient to compute α. Otherwise, ”

p. 356 Addendum before Section 6.6, add the following.

Remark. It is often useful in Step 5 to give more information than just the negative information that I is not a principal ideal. Indeed, if as suggested in Remark (4) after Algorithm 6.5.9, the explicit generators \overline{g_{i}} of order d_{i} of the class group Cl(K) have been computed, we can easily compute α and k_{i} such that I = α ∏_{i} g_{i}^{k_{i}} and 0 ≤ k_{i} < d_{i}. The necessary modifications of the above algorithm are easy and left to the reader.

p. 357 Exercise 7, instead of “ Find also” read “. Find also”

p. 357 Exercise 10 d), instead of “essential discriminant divisor” read “inessential discriminantal divisor”

p. 359 Exercise 26, instead of “Let ω_{i}” read “Let (ω_{i})_{1≤i≤n}”

p. 385 line 1, instead of “f_{E}(it/\sqrt{N}” read “f_{E}(it/\sqrt{N})”

p. 385 lines 12 to -11, replace completely the two paragraphs by the following.

“The main theorem concerning this conjecture is Wiles’s celebrated theorem, which states than when N is squarefree, the conjecture is true (see [Wil], [Tay-Wil]). This result has been generalized by Diamond ([Dia]) to the case where N is only assumed not to be divisible by 9 and 25. In addition, it was proved long ago by Shimura (see [Shi1] and [Shi2]) that it is true for elliptic curves with complex multiplication.

There is also a recent conjecture of Serre (see [Ser1]), which roughly states that any odd 2dimensional representation of the Galois group Gal(\overline{ℚ}/ℚ) over a finite field must come from a modular form. It can be shown that Serre’s conjecture implies the Taniyama-Weil conjecture.

The Taniyama-Weil conjecture, and hence the Taylor-Wiles proof, is mainly important for its own sake. However, it has attracted a lot of attention because of a deep result due to Ribet [Rib], saying that the Taniyama-Weil conjecture for squarefree N implies the full strength of Fermat’s last “theorem” (FLT): if x^{n} + y^{n} = z^{n} with x, y, z non-zero integers, then one must have n ≥ 2. Thanks to Wiles, this is now really a theorem. Although it is not so interesting in itself, FLT has had amazing consequences on the development of number theory, since it is in large part responsible for the remarkable achievements of algebraic number theorists in the nineteenth century, and also as a further motivation for the study of elliptic curves, thanks to Ribet’s result.”

p. 398 middle to end, replace completely by the following.

“ Another algorithm for computing a_{p} has been discovered by R. Schoof ([Scho]). What is remarkable about it is that it is a polynomial time algorithm, more precisely it runs in time O(ln^{8} p). The initial version did not seem to be very useful in practice, but a lot of progress has been done since.

Schoof’s idea, which we will not explain in detail here, is to use the division polynomials for the Weierstraß ℘ function, i.e. polynomials which express ℘(nz) and ℘′(nz) in terms of ℘(z) and ℘′(z) for integer n (in fact a prime number n). This gives congruences for the a_{p}, and using the Chinese remainder theorem we can glue together these congruences to compute the a_{p}.

An interesting blend of the baby-step giant-step algorithm and Schoof’s algorithm is to compute Schoof-type congruences for a_{p} modulo a few primes ℓ. If for example we find the congruences modulo 2, 3 and 5, we can divide the search interval by 30 in the algorithm above, and hence this allows the treatment of larger primes.

The main practical problem with Schoof’s idea is that the equations giving the division polynomials are of degree (n^{2} − 1)/2, and this becomes very difficult to handle as soon as n is a little large.

Recently Elkies has been able to show that in many cases, this degree can be reduced to n + 1, which is much more manageable. Couveignes has also shown how to use n which are powers of small primes and not only primes.

Combining all these ideas, Morain and Lercier (Internet announcement) have been able to deal with a 500-digit prime, which is the current record at the time of this writing.

p. 410 line 2 Exercise 9 a), replace “a polynomial g” by “a unique polynomial g” p. 411 end of Exercise 9, replace “[Mes3]” by “[Nag]” and replace “rank 12” by “rank 13” p. 411 line -2, instead of “ express” read “, express” p. 413 line -8, instead of “1872851947” read “436273009” p. 413 line -7, instead of “1999066711391” read “304599508537, see [Bre3]” p. 414 middle, instead of “x^{c} for some c close to 0.1” read “C · x^{2/7} for some positive constant

C”

p. 415 Step 4 of Algorithm 8.2.2, instead of “Set” read “[Repeat test] Set” p. 415 line -9, instead of “usuaally” read “usually” p. 421 line -8, instead of “2^{lgT} − 1” read “2^{lg T} − 1” p. 422 Step 2 of Algorithm 8.5.2, instead of “x ← x^{2} + 1” read “x ← x^{2} + 1 mod N” p. 422 line -2, instead of “[Mon1]” read “[Mon2]” p. 424 line -11, instead of “2^{lg(x\sqrt{p})}” read “2^{⌊lg(x\sqrt{p})⌋}” p. 424 line -8 to line -3, replace the variable “x” by the variable name “y” (12 times) p. 428 line -8, instead of “theorem 90” read “Theorem 90” p. 432 line 14, instead of “lowest” read “least” p. 433 line 6, instead of “occurs (in step 6)” read “occurs in step 6” p. 436 line 1, instead of “Let h > 1 be an integer” read “Let h > 1 be an integer such that

h ≡ 1 (mod F_{0}F_{1}F_{2}F_{3}F_{4})”

p. 439 line -4, instead of “modulo p” read “modulo 𝔭” p. 441 line -7, instead of “y = tx” read “x = ty” p. 446 line 5, -12 (twice) and line -8, instead of “n” read “N” p. 448 line 7, instead of “an = p^{v_{p}(a)−v_{p}(b)}b” read “an = p^{v_{p}(a)−v_{p}(b)}bm” p. 456 line 1, instead of “If p ≥ 3” read “If p ≥ 3 or p = 2 and k = 2” p. 456 line 7, instead of “j^{2} (χ_{2,q}^{2^{k−3}}, χ_{2,q}^{2^{k−3}})” read “j^{2} (χ_{2,q}^{2^{k−3}}, χ_{2,q}^{3·2^{k−3}})” p. 457 line 4, instead of “2δ_{N}” read “δ_{N}” p. 459 line 16, instead of “Z/Nℤ” read “ℤ/Nℤ” p. 464 line -8, instead of “(resp. 6)” read “(resp. six)” p. 467 Step 12, instead of “P” read “P ” p. 471 middle, instead of “(V, U, (U^{2} − D)/(4V)” read “(V, U, (U^{2} − D)/(4V))” p. 474 line 5, instead of “[Coh-Len1]” read “(see Section 5.10.1 and [Coh-Len1])” p. 497 Exercise 8, instead of “x ∈ ℤ_{K}” read “x = a + bθ ∈ ℤ_{K}” and at the end replace “.” by

“, where (\frac{x}{𝔭}) is defined in Exercise 19 of Chapter 4.”

p. 497 line 1 of Exercise 9, instead of “numbers the” read “numbers, the” p. 518 in [Bac-Sha], instead of “in preparation”, read “Vol. 1: Efficient Algorithms, MIT

Press, Cambridge, Mass, 1996”

p. 521 after [Sil], insert the following. “[Sil3] J. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves, Graduate texts in

Math. 151, Springer-Verlag, New-York, 1994.

The long awaited sequel to [Sil].” p. 521 in [Arn], instead of “(to appear)”, read “64 (1995), 335–361” p. 521 after [Arn], insert the following new reference: “[ARW] S. Arno, M. Robinson and F. Wheeler, Imaginary quadratic fields with small odd class

number, to appear.”

p. 522 after [Bre2], insert the following new reference: “[Bre3] R.P. Brent, The first occurence of large gaps between successive primes, Math. Comp.

27 (1973), 959–963”

p. 523 line -15, in [Coh-Mar3], instead of “(to appear)”, read “63 (1994), 329–334” p. 524 line 3, before [Duv] insert the following reference: “[Duk] W. Duke, Hyperbolic distribution functions and half-integral weight Maass forms, Invent.

Math. 92 (1988), 73–90.”

p. 525 middle, put the reference to [Mart] in correct alphabetical order between [Mah] and [Maz]

p. 526 add the complete references to [Nag] and [Nag-Kou] as follows: “[Nag] K. Nagao, An example of elliptic curve over ℚ(T) with rank ≥ 13, Proc. Japan Acad.

70 (1994), 152–153.”

“[Nag-Kou] K. Nagao and T. Kouya, An example of elliptic curve over ℚ with rank ≥ 21, Proc. Japan Acad. 70 (1994), 104–105.”

p. 530 insert index entry “Duke, W.”, 293 p. 530 remove entry “essential discriminantal divisors, 197” p. 531 add entry “inessential discriminantal divisor, 197, 357”