% To be compiled with AmsTeX 2.0 or later
%\documentstyle{amsppt}
\magnification=\magstephalf
% \nologo
\font\sans=cmss10
\def\ltextindent#1{\hbox to \hangindent{#1\hss}\ignorespaces}
\def\litem{\par\noindent\dimen0=\parindent%
    \advance\dimen0 by-4pt
               \hangindent=\dimen0\ltextindent}
\def\llitem{\par\noindent
               \hangindent=\parindent\ltextindent}
\def\stno#1{\litem{\sans #1}}
\def\exno#1{\llitem{\rm #1}}
\def\t{\theta}
\def\p{\goth p}
\def\q{\goth q}
\def\om{\omega}
\def\eps{\varepsilon}
\def\Gal{\operatorname{Gal}}
\def\Z{\Bbb Z}
\def\Q{\Bbb Q}
\def\R{\Bbb R}
\def\F{\Bbb F}
\def\fp{\qed}
\def\bb{\bold b}
\def\N{\operatorname{\Cal N}}
\def\Tr{\operatorname{Tr}}
\def\ov#1{\overline{\vphantom{T}#1}}
\def\leg#1#2{\fracwithdelims(){#1}{#2}}
\def\gd{{\goth d}}
\def\isom{\simeq}
\def\disc{\operatorname{disc}}
\def\nli{\newline\indent}
\centerline{\bf Errata et Addenda to the Second Corrected Printing of the Book}
\smallskip
\centerline{\bf A Course in Computational Algebraic Number Theory}
\smallskip
\centerline{by \bf Henri Cohen}
\smallskip
\centerline{(19960419 version)}
\medskip
{\obeylines
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
\bigskip
p. VII\quad lines 1 and 2, put Serre and Stark in correct alphabetical order
p. VII\quad line -1, instead of ``Vallee'' read ``Vall\'ee''
p. XII\quad line 20, instead of ``being is'' read ``being''
p. XII\quad lines -4 to -2, replace text starting with ``For Chapter 7,..'' and ending with ``preparation'' by ``For Chapter 7, [Sil] and [Sil3] are excellent books, and contain numerous exercises''
p. 24\quad line 9, instead of ``result'' read ``results''
p. 30\quad line 4, instead of ``step 2'' read ``step 3''
p. 30\quad line 6, instead of ``odd value of $b$'' read ``odd value of $a$''
p. 34\quad line -12, instead of ``$0<x_0<p$'' read ``$p/2<x_0<p$''
p. 39\quad middle, instead of ``The choices'' read ``The choice''
p. 43\quad line 3 of Exercise 16, instead of ``$\Q(\zeta)$'' read ``$\Z[\zeta]$''
p. 43\quad line 5 of Exercise 16, instead of ``$(-1)^{(p-1)/2}$'' read ``$(-1)^{(p-1)/2}p$''
p. 55\quad line 2 of step 3, instead of ``and finally set'' read ``set $h_{i,m-1}\gets0$, and finally set''
p. 57\quad line 5, instead of ``exists'' read ``exist''
p. 68\quad line 4, instead of ``$l=1$'' read ``$l\gets1$'' and instead of ``$l=m-n+1$'' read ``$l\gets m-n+1$''
p. 73\quad line -1, instead of ``lowest'' read ``least''
p. 102\quad line 15, after ``linear algebra algorithms'' insert ``(over $\R$ and not over $\Z$)''
p. 108\quad line -6, instead of ``need, use'' read ``need use''
p. 124\quad line -9, instead of ``$V_{k+1}=V_k$ if $p\nmid k$'' read ``$V_{k+1}=V_k$ if $p\mid k$''
p. 150\quad {\bf Addendum.} Add the following exercise.
}
\smallskip
\exno{``31.}\quad Let $A(X)=a_nX^n+\cdots+a_1X+a_0$ be a polynomial such that
$a_n\neq0$. Show that
$$\disc(A(X^k))=(-1)^{nk(k+3)/2}k^{nk}(a_na_0)^{k-1}\disc(A)^k\enspace.''$$
\smallskip
{\obeylines
p. 151\quad line 4, instead of ``[Sam] however these have'' read ``[Sam]. However, they usually have''
p. 156\quad line -3, instead of ``subring $\Z[\alpha]$'' read ``subfield $\Q(\alpha)$''
p. 156\quad line -1, instead of ``subring'' read ``subfield''
p. 162\quad line 5, instead of ``$\Bbb Z[X]$,'' read ``$\Bbb Z[X]$ of degree $n$,''
p. 168\quad line 14, instead of ``method shows'' read ``method show''
p. 171\quad line -15, instead of ``degree I have'' read ``degree, I have''
p. 181\quad line -9, instead of ``take $R=\cdots$. Then'' read ``let $\om=(1+\sqrt{-7})/2$, take $R=\Z+3\om\Z$ and $I=J=3\Z+3\om\Z$. Then''
p. 182\quad line 1, instead of ``We will prove'' read ``Assume for example that $I$ is invertible. We will prove''
p. 185\quad line 4, instead of ``lowest'' read ``least''
p. 190\quad middle, add a third item to the statement of the proposition:
}
\smallskip
``(3) {\it If $\alpha$ and $\beta$ are in $K$, then $I=\alpha\Z_K+\beta\Z_K$
if and only if for every prime ideal $\p$ we have
$$\min(v_{\p}(\alpha),v_{\p}(\beta))=v_{\p}(I)$$
where $v_{\p}$ denotes the $\p$-adic valuation at the prime ideal $\p$.''}
\smallskip
{\obeylines
p. 191\quad line -17, add the proof of (3) as follows:
}
\smallskip
``For (3) recall that the sum of ideals correspond to GCD, and that the
GCD is computed by taking the minimum of the $\p$-adic valuations.''
\smallskip
{\obeylines
p. 192\quad middle, replace everything starting with the statement of Lemma 4.7.9 until the end of the section by the following.
}
\smallskip
\proclaim\nofrills{\bf Lemma 4.7.9.}\quad Let $\p$ be a prime ideal above $p$ of norm 
$p^f$ ($f$ is called the residual degree of $\p$ as we will see in the 
next section), and let $\alpha\in\p$. Then we have 
$\p=(p,\alpha)=p\Z_K+\alpha\Z_K$ if and only if $v_p(\N(\alpha))=f$ or
$v_p(\N(\alpha+p))=f$, where $v_p$ denotes the ordinary $p$-adic valuation.\endproclaim

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

If $v_p(\N(\alpha+p))=f$ we deduce from this that 
$\p=p\Z_K+(\alpha+p)\Z_K$, but this is clearly also equal to
$p\Z_K+\alpha\Z_K$.

Conversely, let $\p=p\Z_K+\alpha\Z_K$. Then for every prime ideal $\q$
above $p$ and different from $\p$ we have $v_{\q}(\alpha)=0$, while
for $\p$ we can only say that $\min(v_{\p}(p),v_{\p}(\alpha))=1$.

Assume first that $v_{\p}(\alpha)=1$. Then clearly 
$v_p(\N(\alpha))=v_p(\N(\p))=f$ as desired. Otherwise we have
$v_{\p}(\alpha)>1$, and hence $v_{\p}(p)=1$. But then we will have
$v_{\p}(\alpha+p)=1$ (otherwise $v_{\p}(p)=v_{\p}((p+\alpha)-\alpha)>1$),
and still $v_{\q}(\alpha+p)=0$ for all other primes $\q$ above $p$, and so
$v_p(\N(\alpha+p))=f$ as before, thus proving the lemma.\fp

Note that the condition $v_p(\N(\alpha))=f$, while sufficient, is not a
necessary condition (see Exercise 20).

Note also that if we write $\alpha=\sum_{1\le i\le k}\lambda_i\gamma_i$
where the $\gamma_i$ is some generating set of $\p$, we may always assume
that $|\lambda_i|\le p/2$ since $p\in\p$. In addition, if we choose
$\gamma_1=p$, we may assume that $\lambda_1=0$. 

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

\proclaim\nofrills{\bf Algorithm 4.7.10}{\rm\ (Two-Element
Representation of a Prime Ideal). }{\sans Given a
prime ideal $\p$ above $p$ by a system of $\Z_K$-generators $\gamma_i$ for
$(1\le i\le k)$, this algorithm computes a two-element representation
$(p,\alpha)$ for $\p$.

We assume that one knows the norm $p^f$ of $\p$ (this is always the case
in practice, and in any case it can be obtained by computing the HNF of
$\p$ from the given generators), and that $\gamma_1=p$ (if this is not the
case just add it to the list of generators).\smallskip
\stno{1.}\quad [Initialize] Set $R\gets1$.\smallskip
\stno{2.}\quad [Set coefficients] For $2\le i\le k$ set $\lambda_i\gets R$.\smallskip
\stno{3.}\quad [Compute $\alpha$ and check] Let 
$\alpha\gets\sum_{2\le i\le m}\lambda_i\gamma_i$,
$n\gets\N(\alpha)/p^f$, where the norm is computed, for example, using 
the sub-resultant algorithm (see Section 4.3). If $p\nmid n$, 
then output $(p,\alpha)$ and terminate the algorithm.
Otherwise, set $n\gets\N(\alpha+p)/p^f$. If $p\nmid n$ then output
$(p,\alpha)$ and terminate the algorithm.\smallskip
\stno{4.}\quad [Decrease coefficients] Let $j$ be the largest $i\le k$ 
such that $\lambda_i\neq -R$ (we will always keep $\lambda_2\ge0$ so $j$
will exist). Set $\lambda_j\gets\lambda_j-1$ and for $j+1\le i\le m$ set 
$\lambda_i\gets R$.\smallskip
\stno{5.}\quad [Search for first non-zero] Let $j$ be the smallest 
$i\le k$ such that $\lambda_i\neq 0$. If no such $j$ exists (i.e.~if all
the $\lambda_i$ are equal to 0) set $R\gets R+1$ and go to step 2.
Otherwise go to step 3.}
\endproclaim
\medskip
{\bf Remarks.} 
1) Steps 4 and 5 of this algorithm represent a standard backtracking 
procedure. What we do essentially is to search for 
$\alpha=\sum_{2\le i\le k}\lambda_i\gamma_i$, where the $\lambda_i$ are
integers between $-R$ and $R$. To avoid searching both for $\alpha$ and 
$-\alpha$, we add the condition that the first non-zero $\lambda$ 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 $\alpha$ 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\le p/2$.

2) It is often the case that one of the $\gamma_i$ for $2\le i\le 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.''
\smallskip
{\obeylines
p. 195\quad line -2, instead of ``{\it If $p=\prod_{i=1}^g\goth p_i$ is an unramified prime in $K$}'' read ``{\it If $p$ is an unramified prime in $K$ with $p\Z_K=\prod_{i=1}^g\goth p_i$}''
p. 197\quad line 10, instead of ``{\sl essential\/}'' read ``{\sl inessential\/}''
p. 199\quad line 10 and line 11, instead of ``$q_j$'' read ``$\frak q_j$''
p. 199\quad middle, instead of ``$p^{-1}=R+aR$'' read ``$\p^{-1}=R+aR$''
p. 201\quad line -4, instead of ``$Z[\theta]$'' read ``$\Z[\theta]$''
p. 203\quad line -4 until p. 204 line -12, replace completely by the following.
}
\smallskip
``To compute the inverse of an ideal $I$ given by a $\Z$-basis $\gamma_j$ 
represented by an $n\times 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 $\gd(K)^{-1}$. We then compute the {\it ideal}
product $I\gd(K)^{-1}$ by Hermite reduction of an $n\times 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^tT)^{-1}$ will form
a $\Z$-basis of the ideal $(I\gd(K)^{-1})^{-1}\gd(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 $\gd(K)^{-1}$ by $d(K)\gd(K)^{-1}$ which
is an integral ideal.
\smallskip
This leads to the following algorithm.

\proclaim\nofrills{\bf Algorithm 4.8.21}{\rm\ (Ideal Inversion). }{\sans
Given an integral basis $(\om_i)_{1\le i\le n}$ of the ring of integers
of a number field $K$ and an integral ideal $I$ given by an $n\times n$
matrix $M$ whose columns give the coordinates of a $\Z$-basis $\gamma_j$
of $I$ on the $\om_i$, this algorithm computes the HNF of the inverse 
ideal $I^{-1}$.\smallskip
\stno{1.}\quad [Compute $d(K)\gd(K)^{-1}$] Compute the $n\times n$ matrix 
$T=(t_{i,j})$ such that $t_{i,j}=\Tr_{K/\Q}(\om_i\om_j)$. Set 
$d\gets\det(T)$ (this is the determinant $d(K)$ of $K$ hence is usually
available with the $\om_i$ already). Finally, call $\delta_j$ the elements
of $\Z_K$ whose coordinates on the $\om_i$ are the columns of $dT^{-1}$
(thus the $\delta_j$ will be a $\Z$-basis of the integral ideal 
$d(K)\gd(K)^{-1}$).\smallskip
\stno{2.}\quad [Compute $d(K)I\gd(K)^{-1}$] Let $N$ be the HNF of the
$n\times n^2$ matrix whose columns are the coordinates on
the integral basis of the $n^2$ products $\gamma_i\delta_j$ (the
columns of $N$ will form a $\Z$-basis of $d(K)I\gd(K)^{-1}$).\smallskip
\stno{3.}\quad [Compute $I^{-1}$] Set $P\gets d(K)(N^tT)^{-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.}\endproclaim\medskip

{\bf Remarks.}
\roster\item 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)\gd(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 $\Z_K=\Z[\t]$ and if $P[X]$ is the minimal monic polynomial of $\t$, 
then one can prove (see Exercise 33) that $\gd(K)$ is the principal
ideal generated by
$P'(\t)$, so the ideal multiplication of step 2 is even simpler.
\item If we want to compute the HNF of the different $\gd(K)$ itself,
we apply the above algorithm to the integral ideal $d(K)\gd(K)^{-1}$
(with $M=d(K)T^{-1}$) and multiply the resulting inverse by $d(K)$ to
get $\gd(K)$.''\endroster
\smallskip
{\obeylines
p. 204\quad (if the replacement above is not made) line -14, instead of ``$p_i$'' read ``$\frak p_i$''
p. 213\quad line -2, instead of ``Brauer-Siegel'' read ``Brauer-Siegel theorem''
p. 217\quad {\bf Addendum.} Add the following exercises.
}
\smallskip
\exno{``29.}\quad Let $\p$ be a prime ideal above the prime 2 in a 
number field $K$ such that $e(\p/2)=2$. Show that the congruences
$x^2\equiv a\pmod{\p^3}$ have a solution for $a=-1$ and $a=-2$.
\smallskip
\exno{30.}\quad Let $I$ be an integral ideal in a number field $K$ and
let $\ell(I)$ be the positive generator of $I\cap\Z$.\nli
a) Show that
$$\ell(I)=\prod_{p\mid\N(I)}p^{\max_{\p\mid p}\lceil v_{\p}(I)/e(\p/p)\rceil}\enspace.$$\nli
b) Let $\alpha\in I$ be such that $(\N(I),\N(\alpha)/\N(I))=1$. Show that
$$I=\ell(I)\Z_K+\alpha\Z_K=\N(I)\Z_K+\alpha\Z_K$$
(this is a partial generalization of Lemma 4.7.9).\nli
c) Deduce from this an algorithm for finding a two-element representation
of $I$ analogous to Algorithm 4.7.10.\smallskip
\exno{31.}\quad Let $\p$ be a prime ideal in a number field $K$, and 
denote by $p$ the prime number below $\p$, by $e=e(\p/p)$ the ramification
index, and by $f=f(\p/p)$ the residual degree of $\p$. The goal of this
exercise is to find the Abelian group structure of $\Z_K/\p^k$ and also of
$(\Z_K/\p^k)^*$ in a number of cases.\nli
a) Let $k\ge1$ be an integer, and let $k-1=qe+r$ be the Euclidean division
of $k-1$ by $e$, with $0\le r<e$. Show that we have the Abelian group
isomorphism
$$\Z_K/\p^k\isom\left(\Z/p^{q+1}\Z\right)^{f(r+1)}\times
\left(\Z/p^q\Z\right)^{f(e-r-1)}\enspace.$$\nli
b) Let $k\ge1$ be an integer, and let $k-2=qe+r$ be the Euclidean division
of $k-2$ by $e$, with $0\le r<e$. Assume that $p\ge\min(k,e+2)$. Show 
that we have the Abelian group isomorphism
$$\left(\Z_K/\p^k\right)^*\isom\left(\Z/(p^f-1)\Z\right)\times
\left(\Z/p^{q+1}\Z\right)^{f(r+1)}\times
\left(\Z/p^q\Z\right)^{f(e-r-1)}\enspace,$$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$).\nli
c) Assume that $e=1$, i.e. that $\p$ is an unramified prime ideal.
The above isomorphism gives the structure of $(\Z_K/\p^k)^*$ for $p\ge3$.
Show that for $p=2$,
$$\left(\Z_K/\p^k\right)^*\isom\left(\Z/(p^f-1)\Z\right)\times
\left(\Z/p^{k-1}\Z\right)^{f-1}\times
\Z/p^{k-2}\Z\times\Z/p\Z\enspace.$$\nli
d) Assume on the contrary that $e$ is large, say $e\ge k(p-1)/p$.
Set $u_m=\lfloor(k-1)/p^m\rfloor$ for all $m\ge0$, so that $u_m=0$ for
$m$ sufficiently large. Show that
$$\left(\Z_K/\p^k\right)^*\isom\left(\Z/(p^f-1)\Z\right)\times
\prod_{m\ge1}\left(\Z/p^m\Z\right)^{f(u_{m-1}-2u_m+u_{m+1})}\enspace.$$\nli
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
$$\left(\Z_K/\p^k\right)^*\isom\left(\Z/(p^f-1)\Z\right)\times G^f
\enspace.$$\nli
f) Determine the structure of $(\Z_K/\p^k)^*$ for $1\le k\le 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\le k\le5$, of $\eps$ where $\eps=1$
if there exists a solution of $x^2\equiv-3\pmod{\p^3}$, $\eps=0$
otherwise.\smallskip
\exno{32.}\quad Given a prime ideal $\p$ in a number field $K$ and a 
positive integer $k$, write an algorithm which computes the Abelian
group structure of $(\Z_K/\p^k)^*$ as a product of cyclic groups.
\smallskip
\exno{33.}\quad Let $K=\Q[\t]$ be a number field, where $\t$ is an
algebraic integer whose minimal monic polynomial is $P(X)\in\Z[X]$.
Assume that $\Z_K=\Z[\t]$. Show that the different $\gd(K)$ is the
principal ideal generated by $P'(\t)$.\smallskip
\exno{34.}\quad 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=\Z_K$. Give an algorithm which finds $i\in I$
and $j\in J$ such that $i+j=1$.\smallskip
\exno{35.}\quad a) Using the preceding exercise, give an algorithm wich
finds explicitly the element $\beta\in\Z_K$ whose existence is proven in
Proposition 4.7.8.\nli
b) Deduce from this an algorithm which finds a two-element
representation $I=\alpha\Z_K+\beta\Z_K$ of an integral ideal $I$ given
a non-zero element $\alpha\in I$.\nli
c) In the case where $\alpha=\ell(I)$, compare the theoretical and
practical performance of this algorithm with the one given in Exercise 
30.\smallskip
\exno{36.}\quad Let $W=(w_{i,j})_{1\le i,j\le n}$ be the (upper
triangular) $n\times n$ Hermite Normal Form matrix of a prime ideal $\p$
on some integral basis $\om_i$ (so there is no denominator) where we 
assume as usual that $\om_1=1$, let $p$ be the prime number below $\p$ 
and let $f=f(\p/p)$ be the residual index of $\p$.\nli
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$.\nli
b) If $w_{j,j}=1$, we already know that all other elements $w_{j,k}$ of
the same {\it row\/} are equal to zero. Show that if $w_{j,j}=p$, all 
other elements $w_{i,j}$ of the same {\it column\/} are equal to zero
(hint: note that $p\om_j\in\p$ and induct on $i$).\smallskip
\exno{37.}\quad Modify Proposition 4.3.4 so that it is still valid 
when $T(X)\in\Q[X]$ and not necessarily monic.''\smallskip
{\obeylines
p. 218\quad line -3, instead of ``Corollary 4.4.6'' read ``Corollary 4.4.7''
p. 229\quad lines 2-3, instead of ``Appendix C'' read ``Appendix B''
p. 229\quad line 11, instead of ``$-127$, \dots'' read ``$-127$, \dots, $-2683$.''
p. 229\quad line 13, instead of ``$-251$, \dots'' read ``$-251$, \dots, $-5923$.''
p. 229\quad 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\quad line -12, instead of ``enables'' read ``enable''
p. 235\quad line -20, instead of ``whether it is not in'' read ``whether or not it is in''
p. 236\quad line 2 of Step 3, instead of ``go to step 7'' read ``go to step 6''
p. 237\quad line 8, instead of ``lowest'' read ``least''
p. 243\quad line 2 of step 4 of Algorithm 5.4.8, instead of ``step 2'' read ``step 3''
p. 243\quad step 3 of Algorithm PARTEUCL, instead of ``Let $q\gets\lfloor d/v_3\rfloor$ and simultaneously $t_3\gets d\bmod v_3$'' read ``Let $d=qv_3+t_3$ be the Euclidean division of $d$ by $v_3$ with $0\le t_3<|v_3|$''
p. 278\quad line 3, instead of ``$|(b+\sqrt D)/(b-\sqrt D)$'' read ``$|(b+\sqrt D)/(b-\sqrt D)|$''
p. 283\quad line -11, instead of ``the real part of $\Delta_C$ lies in the hyperplane $\sum_ix_i=0$'' read ``the sum of the $r_1+r_2$ components of $\Delta_C$ is an integral multiple of $2i\pi$''
p. 285\quad lines -9 to page 286 line 9, replace completely by the following:
}
\smallskip
``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\le k$ we
have 
$$\delta\left(\bold 1,\prod_{1\le i\le n}f_{p_i}^{a_{i,j}}\right)\equiv a_{n+1,j}\pmod{R(D)}\enspace.$$
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\le j\le k-n$ we will thus have 
$$a_{n+1,j}=\delta(\bold 1,\bold 1)\equiv0\pmod{R(D)}\enspace,$$
in other words $a_{n+1,j}$ is equal to a multiple of the regulator $R(D)$
for $1\le j\le k-n$. 

If $k$ is large enough, it follows that in a certain sense the GCD of the
$a_{n+1,j}$ for $1\le j\le 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\le j\le k-n$ with integral coefficients,
which should be the regulator $R(D)$, or use the ``real GCD'' Algorithm
5.9.3 as described below.''
\smallskip
{\obeylines
p. 290\quad lines 12, instead of ``$55$'' read ``$K$'' and instead of ``$\prod_{p\mid D}$'' read ``$\prod^*_{p\mid D}$''
p. 290\quad 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\quad line -14, instead of ``the similarly'' read ``similarly''
p. 293\quad 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\quad line -1, instead of ``in terms of'' read ``as a function of''
p. 294\quad line 1 of Exercise 11, instead of ``integers'' read ``integers, and assume that at most one of them is equal to zero''
p. 302\quad line 8, instead of ``lowest'' read ``least'', and remove ``(lcm)''
p. 302\quad line 9, instead of ``PID'' read ``PID,''
p. 313\quad line 15, instead of ``lowest'' read ``least''
p. 319\quad middle, replace ``$\Z/3\Z$'' by ``$C_3$'' and ``$(A_3,+)$'' by ``$(C_3,+)$''
p. 328\quad 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\quad 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\quad line 6, instead of ``we take in step 9'' read ``in step 9 we take''
p. 342\quad Corollary 6.4.15, in (3) and in (4), instead of ``If $p\equiv1\pmod3$'' read ``If $p\nmid a$, $p\equiv1\pmod3$'', and in (5) instead of ``If $p=3$'' read ``If $p=3$ and $p\nmid a$''
p. 346\quad line 8, instead of ``are prime ideals'' read ``are distinct prime ideals''
p. 354\quad line 3 of (4), instead of ``$g_i$'' read ``$\ov{g_i}$'' (twice)
p. 355\quad line 2 of Algorithm 6.5.10, instead of ``computes and'' read ``computes an''
p. 356\quad line 2 of Step 9, instead of ``in $K$),'' read ``in $K$). If $I\neq\alpha\Z_K$, output an error message stating that the accuracy is not sufficient to compute $\alpha$. Otherwise, ''
p. 356\quad {\bf Addendum} before Section 6.6, add the following.
}
\smallskip
{\bf 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 $\ov{g_i}$ of order $d_i$ of the class group $Cl(K)$ have been
computed, we can easily compute $\alpha$ and $k_i$ such that 
$I=\alpha\prod_ig_i^{k_i}$ and $0\le k_i<d_i$. The necessary modifications
of the above algorithm are easy and left to the reader.
\smallskip
{\obeylines
p. 357\quad Exercise 7, instead of `` Find also'' read ``. Find also''
p. 357\quad Exercise 10 d), instead of ``essential discriminant divisor'' read ``inessential discriminantal divisor''
p. 359\quad Exercise 26, instead of ``Let $\om_i$'' read ``Let $(\om_i)_{1\le i\le n}$''
p. 385\quad line 1, instead of ``$f_E(it/\sqrt N$'' read ``$f_E(it/\sqrt N)$''
p. 385\quad lines 12 to -11, replace completely the two paragraphs by the following.
}
\smallskip
``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 2-dimensional representation of the Galois group
$\Gal(\ov{\Q}/\Q)$ 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\ge2$. 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.''
\smallskip
{\obeylines
p. 398\quad middle to end, replace completely by the following.
}
\smallskip
``
Another algorithm for computing $a_p$ has been discovered by R. Schoof 
([Scho]). What is remarkable about it is that it is a
{\it polynomial time\/} algorithm, more precisely it runs in time $O(\ln^8p)$.
The initial version did not seem to be very useful in practice, but a lot of 
progress has been done since. 
\smallskip
Schoof's idea, which we will not explain in detail here, is to use the
{\it division polynomials\/} for the Weierstra\ss\ $\wp$ function, 
i.e.~polynomials which express $\wp(nz)$ and $\wp'(nz)$ in terms of $\wp(z)$ 
and $\wp'(z)$ for integer $n$ (in fact a prime number $n$). This gives 
{\it congruences\/} for the $a_p$, and using the Chinese remainder theorem we 
can glue together these congruences to compute the $a_p$.
\smallskip
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 $\ell$. 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.

\smallskip
{\obeylines
p. 410\quad line 2 Exercise 9 a), replace ``a polynomial $g$'' by ``a unique polynomial $g$''
p. 411\quad end of Exercise 9, replace ``[Mes3]'' by ``[Nag]'' and replace ``rank 12'' by ``rank 13''
p. 411\quad line -2, instead of `` express'' read ``, express''
p. 413\quad line -8, instead of ``$1872851947$'' read ``$436273009$''
p. 413\quad line -7, instead of ``$1999066711391$'' read ``$304599508537$, see [Bre3]''
p. 414\quad middle, instead of ``$x^c$ for some $c$ close to $0.1$'' read ``$C\cdot x^{2/7}$ for some positive constant $C$''
p. 415\quad Step 4 of Algorithm 8.2.2, instead of ``{\sans Set}'' read ``{\sans [Repeat test] Set}''
p. 415\quad line -9, instead of ``usuaally'' read ``usually''
p. 421\quad line -8, instead of ``$2^{lgT}-1$'' read ``$2^{\lg T}-1$''
p. 422\quad Step 2 of Algorithm 8.5.2, instead of ``$x\gets x^2+1$'' read ``$x\gets x^2+1\bmod N$''
p. 422\quad line -2, instead of ``[Mon1]'' read ``[Mon2]''
p. 424\quad line -11, instead of ``$2^{\lg(x\sqrt p)}$'' read ``$2^{\lfloor\lg(x\sqrt p)\rfloor}$''
p. 424\quad line -8 to line -3, replace the variable ``$x$'' by the variable name ``$y$'' (12 times)
p. 428\quad line -8, instead of ``theorem 90'' read ``Theorem 90''
p. 432\quad line 14, instead of ``lowest'' read ``least''
p. 433\quad line 6, instead of ``occurs (in step 6)'' read ``occurs in step 6''
p. 436\quad line 1, instead of ``Let $h>1$ be an integer'' read ``Let $h>1$ be an integer such that $h\equiv1\pmod{F_0F_1F_2F_3F_4}$''
p. 439\quad line -4, instead of ``modulo $p$'' read ``modulo $\frak p$''
p. 441\quad line -7, instead of ``$y=tx$'' read ``$x=ty$''
p. 446\quad line 5, -12 (twice) and line -8, instead of ``$n$'' read ``$N$''
p. 448\quad 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\quad line 1, instead of ``{\sans If $p\ge3$}'' read ``{\sans If $p\ge3$ or $p=2$ and $k=2$}''
p. 456\quad line 7, instead of ``$j^2\left(\chi_{2,q}^{2^{k-3}},\chi_{2,q}^{2^{k-3}}\right)$'' read ``$j^2\left(\chi_{2,q}^{2^{k-3}},\chi_{2,q}^{3\cdot2^{k-3}}\right)$''
p. 457\quad line 4, instead of ``$2\delta_N$'' read ``$\delta_N$''
p. 459\quad line 16, instead of ``$Z/N\Z$'' read ``$\Z/N\Z$''
p. 464\quad line -8, instead of ``(resp. 6)'' read ``(resp. six)''
p. 467\quad Step 12, instead of ``{\sans P}'' read ``$P$''
p. 471\quad middle, instead of ``$(V,U,(U^2-D)/(4V)$'' read ``$(V,U,(U^2-D)/(4V))$''
p. 474\quad line 5, instead of ``[Coh-Len1]'' read ``(see Section 5.10.1 and [Coh-Len1])''
p. 497\quad Exercise 8, instead of ``$x\in\Z_K$'' read ``$x=a+b\theta\in\Z_K$'' and at the end replace ``.'' by ``, where $\leg{x}{\p}$ is defined in Exercise 19 of Chapter 4.''
p. 497\quad line 1 of Exercise 9, instead of ``numbers the'' read ``numbers, the''
p. 518\quad in [Bac-Sha], instead of ``in preparation'', read ``{\it Vol. 1: Efficient Algorithms\/}, MIT Press, Cambridge, Mass, 1996''
p. 521\quad after [Sil], insert the following.
}
\smallskip
``[{\bf Sil3}] J.~Silverman, {\it Advanced Topics in the Arithmetic of 
Elliptic Curves\/},  Graduate texts in Math. {\bf 151}, Springer-Verlag, 
New-York, 1994.
\smallskip
The long awaited sequel to [Sil].''
\smallskip
{\obeylines
p. 521\quad in [Arn], instead of ``(to appear)'', read ``{\bf 64} (1995), 335--361''
p. 521\quad after [Arn], insert the following new reference: 
``[{\bf ARW}] S.~Arno, M.~Robinson and F.~Wheeler, {\it Imaginary quadratic fields with small odd class number\/}, to appear.''
p. 522\quad after [Bre2], insert the following new reference:
``[{\bf Bre3}] R.P.~Brent, {\it The first occurence of large gaps between successive primes}, Math. Comp. {\bf 27} (1973), 959--963''
p. 523\quad line -15, in [Coh-Mar3], instead of ``(to appear)'', read ``{\bf 63} (1994), 329--334''
p. 524\quad line 3, before [Duv] insert the following reference:
``[{\bf Duk}] W.~Duke, {\it Hyperbolic distribution functions and half-integral weight Maass forms\/}, Invent. Math. {\bf 92} (1988), 73--90.''
p. 525\quad middle, put the reference to [Mart] in correct alphabetical order between [Mah] and [Maz]
p. 526\quad add the complete references to [Nag] and [Nag-Kou] as follows:
``[{\bf Nag}] K.~Nagao, {\it An example of elliptic curve over $\Q(T)$ with rank $\ge13$\/}, Proc. Japan Acad. {\bf 70} (1994), 152--153.''
``[{\bf Nag-Kou}] K.~Nagao and T.~Kouya, {\it An example of elliptic curve over $\Q$ with rank $\ge21$\/}, Proc. Japan Acad. {\bf 70} (1994), 104--105.''
p. 530\quad insert index entry ``Duke, W.'', 293
p. 530\quad remove entry ``essential discriminantal divisors, 197''
p. 531\quad add entry ``inessential discriminantal divisor, 197, 357''
}
\end