% To be compiled with AmsTeX 2.0 or later
\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\om{\omega}
\def\eps{\varepsilon}
\def\Z{\Bbb Z}
\def\Q{\Bbb Q}
\def\F{\Bbb F}
\def\fp{\qed}
\def\bb{\bold b}
\def\N{\operatorname{\Cal N}}
\def\ov#1{\overline{\vphantom{T}#1}}
\def\leg#1#2{\fracwithdelims(){#1}{#2}}
\centerline{\bf Errata et Addenda to the Book}
\smallskip
\centerline{\bf A Course in Computational Algebraic Number Theory}
\smallskip
\centerline{by \bf Henri Cohen}
\smallskip
\centerline{(19940513 version)}
\medskip
{\obeylines
Graduate Texts in Mathematics 138, Springer-Verlag, 1993, XXI + 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 line 1 add ``Andrew Odlyzko,'' after ``Nicolas,''
p. X\quad line -7, instead of ``algorithms'' read ``an algorithm''
p. XIII\quad e-mail address, remove ``{\tt ecole.}''
p. XIII\quad end, add the following: 
``In addition, a regularly updated errata file is available by anonymous ftp from
{\tt megrez.ceremab.u-bordeaux.fr (147.210.16.17)}, directory {\tt pub/cohenbook}.''
p. XX\quad 8.4., instead of ``Lehmann'' read ``Lehman''
p. 1\quad line -13, instead of ``is that it is'' read ``that it is''
p. 2\quad line -4, instead of ``easily'' read ``easy''
p. 2\quad line -2 replace ``Cayley/Magma'' by ``Magma'' and insert after ``Macsyma''
p. 3\quad line 16, instead of ``not.'' read ``not).''
p. 4\quad line -2, instead of ``$a*b$'' read ``$a\cdot b$''
p. 10\quad lines 1 and 2, instead of ``$O(\ln m\ln|n|)$ instead of $O(\ln^2m\ln\ln|n|)$ for'' read ``in average up to $1.5$ times faster than''
p. 10\quad step 1 of Algorithm 1.2.4, instead of ``$z\gets g$ and $f\gets e$.'' read ``$z\gets g$. Finally, set $f\gets e$.''
p. 13\quad step 1 of Algorithm 1.3.3, instead of ``simple precision'' read ``single precision''
p. 17\quad step 2 of Algorithm 1.3.7, instead of ``simple precision'' read ``single precision''
p. 20\quad line -4, instead of ``$x_i=$'' read ``$x_i$''
p. 22\quad line 13, instead of ``$\dots]$.'' read ``$\dots]$).''
p. 22\quad replace step 3 of Algorithm 1.3.13 by the following:
}
\smallskip
{\sans\stno{``3.}\quad [Output quotient] Set $a_i\gets q$ and output $a_i$,
then set $i\gets i+1$, $a\gets b$, $b\gets r$, $a'\gets b'$ and $b'\gets r'$.
If $b$ and $b'$ are non-zero, go to step 2. If $b=b'=0$, terminate the 
algorithm. Finally, if $b=0$ set $q\gets\infty$ and 
$q'\gets\lfloor a'/b'\rfloor$ while if $b'=0$ set $q\gets\lfloor a/b\rfloor$
and $q'\gets\infty$.''}
\smallskip
{\obeylines
p. 37\quad line 14, instead of ``custom'' read ``special-purpose''
p. 37\quad steps 1 and 3, instead of ``above'' read ``below''
p. 37\quad replace step 2 by the following:
}
\smallskip
{\sans\stno{``2.}\quad [Small degree?] If $\deg(A)=0$, terminate the 
algorithm.If $\deg(A)=1$, and $A(X)=a_1X+a_0$, output $-a_0/a_1$ and 
terminate the algorithm.
If $\deg(A)=2$ and $A(X)=a_2X^2+a_1X+a_0$, set $d\gets a_1^2-4a_0a_2$, compute
$e\gets\sqrt d$ using Algorithm 1.5.1, output $(-a_1+e)/(2a_2)$ and 
$(-a_1-e)/(2a_2)$, and terminate the algorithm. (Note that $e$ will exist.)''}
\smallskip
{\obeylines
p. 41\quad line 13 to line -1, replace completely by the following:
}
\smallskip
``The idea is to use the following proposition.
\proclaim{\bf Proposition 1.7.4} Let $n=p^k$ be a prime power. Then
\roster\item For any $a$ we have $p\mid (a^n-a,n)$.
\item  If $k\ge2$ and $p>2$, let $a$ be a witness to the compositeness of $n$
given by the Rabin-Miller test 8.2.2, i.e. such that $(a,n)=1$, and if 
$n-1=2^tq$ with $q$ odd, then $a^q\not\equiv1\pmod n$ and for all $e$ such 
that $0\le e\le t-1$ then $a^{2^eq}\not\equiv-1\pmod n$. Then $(a^n-a,n)$ is a 
non-trivial divisor of $n$ (i.e. is different from 1 and $n$).\endroster
\endproclaim

{\it Proof.\/} By Fermat's theorem, we have $a^n\equiv a\pmod p$, hence (1) is
clear. Let us prove (2). Let $a$ be a witness to the compositeness of $n$ as
defined above. By (1), we already know that $(a^n-a,n)>1$. Assume
that $(a^n-a,n)=n$, i.e. that $a^n\equiv a\pmod n$. Since $(a,n)=1$ this is
equivalent to $a^{n-1}\equiv1\pmod n$, i.e. $a^{2^tq}\equiv1\pmod n$. Let
$f$ be the smallest non-negative integer such that $a^{2^fq}\equiv1\pmod n$.
Thus $f$ exists and $f\le t$. If we had $f=0$, this would contradict the
definition of a witness ($a^q\not\equiv1\pmod n$). So $f>0$. But then
we can write $$p^k\mid (a^{2^{f-1}q}-1)(a^{2^{f-1}q}+1)$$and since $p$ is
an odd prime, this implies that $p^k$ divides one of the two factors. But
$p^k\mid (a^{2^{f-1}q}-1)$ contradicts the minimality of $f$, and
$p^k\mid (a^{2^{f-1}q}+1)$ contradicts the fact that $a$ is a witness
(we cannot have $a^{2^eq}\equiv-1\pmod n$ for $e<t$), hence we have a
contradiction in every case thus proving the proposition.\fp
\smallskip
This leads to the following algorithm.

\proclaim\nofrills{\bf Algorithm 1.7.5}{\rm\ (Prime Power Test). }{\sans Given a positive
integer $n>1$, this algorithm tests whether or not $n$ is of the form $p^k$
with $p$ prime, and if it is, outputs the prime $p$.\smallskip
\stno{1.}\quad [Case $n$ even] If $n$ is even, set $p\gets2$ and go to 
step 4. Otherwise, set $q\gets n$.\smallskip
\stno{2.}\quad [Apply Rabin-Miller] By using Algorithm 8.2.2 show that either
$q$ is a probable prime or exhibit a witness $a$ to the compositeness of $q$.
If $q$ is a probable prime, set $p\gets q$ and go to step 4.\smallskip
\stno{3.}\quad [Compute GCD] Set $d\gets(a^q-a,q)$. If $d=1$ or $d=q$, then
$n$ is not a prime power and terminate the algorithm. Otherwise set
$q\gets d$ and go to step 2.\smallskip
\stno{4.}\quad [Final test] (Here $p$ is a divisor of $n$ which is almost
certainly prime.) Using a primality test (see Chapters 8 and 9) prove that
$p$ is prime. If it is not (an exceedingly rare occurence), set $q\gets p$
and go to step 2. Otherwise, by dividing $n$ by $p$ repeatedly, check whether
$n$ is a power of $p$ or not. If it is not, $n$ is not a prime power, otherwise
output $p$. Terminate the algorithm.}\endproclaim
\medskip
We have been a little sloppy in this algorithm. For example in step 4,
instead of repeatedly dividing by $p$ we could use a binary
search analogous to the binary powering algorithm. We leave this as an
exercise for the reader (Exercise 4).''
\smallskip
{\obeylines
p. 48\quad line 1 of step 5 of Algorithm 2.2.1, instead of ``$k>l$'' read ``$k>j$''
p. 51\quad replace the last two lines of Proposition 2.2.5 by the following:
``Finally, let $c_n=a_{n,n}^{(n-1)}$. Then all the divisions by $c_{k-1}$ are exact; we have $\det(M_k)=c_k^{n-k-1}\det(M_0)$, and in particular $\det(M_0)=c_n$.''
p. 51\quad line -15, instead of ``$k+1\times k+1$'' read ``$(k+1)\times(k+1)$''
p. 51\quad line -4 instead of ``$sM_{n,n}$'' read ``$sm_{n,n}$''
p. 55\quad line 20, instead of ``$p_m(X)=...$'' read ``$p_m(X)\gets...$''
p. 59\quad line -2 instead of ``a $m\times r$'' read ``an $m\times r$''
p. 59\quad line -2 instead of ``$r\le n\le m$'' read ``$n\le m$''
p. 59\quad line -1 instead of ``a $n\times r$'' read ``an $n\times r$''
p. 60\quad line 3, instead of ``$X'_i$'' read ``$M'_i$, $X'_i$'' and instead of ``$X$)'' read ``$M$, $X$)''
p. 61\quad lines 5 to 8, replace step 4 by the following:
}
\smallskip
{\sans\stno{``4.}\quad [Modify basis and eliminate] Set $B_t\gets B_s$ (if 
$t\neq s$), then set $B_s\gets M_s$. Then for $j=s+1$,\dots,$k$, do as follows.
Exchange $m_{s,j}$ and $m_{t,j}$ (if $t\neq s$). Set $m_{s,j}\gets dm_{s,j}$.
Then for all $i\neq s$ and $i\neq t$, set 
$m_{i,j}\gets m_{i,j}-m_{i,s}m_{s,j}$. Finally, go to step 2.''}
\smallskip
{\obeylines
p. 61\quad line 2 of Algorithm 2.3.7, instead of ``column'' read ``columns''
p. 71\quad lines -6 to -1, replace step 4 by the following:
}
\smallskip
{\sans\stno{``4.}\quad [Next row] Using Euclid's extended algorithm, find
$(u,v,d)$ such that $ua_{i,k}+vR=d=\gcd(a_{i,k},R)$. Set 
$W_i\gets uA_k\bmod R$ (here taken in the interval $[0,R-1]$). If 
$w_{i,i}=0$ set $w_{i,i}\gets R$. For $j=i+1,\dots,m$ set 
$q\gets\lfloor w_{i,j}/w_{i,i}\rfloor$ and $W_j\gets W_j-qW_i$.
If $i=1$, output the matrix $W=(w_{i,j})_{1\le i,j\le m}$
and terminate the algorithm. Otherwise, set $R\gets R/d$, $i\gets i-1$,
$k\gets k-1$, $j\gets k$, and if $a_{i,k}=0$ set $a_{i,k}\gets R$.
Go to step 2.''}
\smallskip
{\obeylines
p. 73\quad line 2 of step 4  of Algorithm 2.4.10, instead of ``step 6'' read ``step 5''
p. 79\quad line 1, instead of ``for all'' read ``for all non-zero''
p. 82\quad line 4, instead of ``exists'' read ``exist''
p. 87\quad line 6, instead of ``set'', read ``set (in this order)''
p. 87\quad line 6, just before ``$B_k\gets B_{k-1}B_k/B$'' insert ``$\bb\gets\bb_{k-1}^*$, $\bb_{k-1}^*\gets\bb_k^*+\mu\bb$, 
$\bb_k^*\gets -\mu_{k,k-1}\bb_k^*+(B_k/B)\bb$, ''
p. 88\quad line 11, instead of ``Gram-Schmidt'' read ``Gram''
p. 88\quad line 13, instead of ``so that statements ... removed'' read ``and the updating of the vectors $\bb_i$ done in Sub-algorithms RED and SWAP must be done directly on the Gram matrix''
p. 89\quad line 13, instead of ``to be LLL'' read ``from being LLL''
p. 93\quad line 3 of Algorithm REDI, after ``$H_k\gets H_k-qH_l$,'' insert `` $\bb_k\gets \bb_k-q\bb_l$,''
p. 93\quad line 1 of Algorithm SWAPI, after ``$H_k$ and $H_{k-1}$,'' insert `` exchange $\bb_k$ and $\bb_{k-1}$,''
p. 93\quad line 4 of Algorithm SWAPI, instead of ``$t+\lambda\lambda_{i,k}/B$'' read ``$(Bt+\lambda\lambda_{i,k})/d_k$''
p. 94\quad line 2 of step 2, instead of ``$\mu_{k,j}=0$'' read ``$\mu_{k,j}\gets0$''
p. 94\quad just before step 1, instead of ``$\bold r\cdot\bb_i=0$ for all $i$'' read ``$\sum_{1\le i\le n}r_i\bb_i=0$''
p. 94\quad line -5, after ``echange $B_k$ and $B_{k-1}$'', insert ``, exchange $\bb_k^*$ and $\bb_{k-1}^*$''
p. 94\quad line -3, after ``$B_{k-1}\gets B$'', insert ``, $\bb_{k-1}^*\gets\mu\bb_{k-1}^*$''
p. 94\quad line -1, after ``$\mu_{k,k-1}\gets\mu t$'' insert ``$\bb\gets\bb_{k-1}^*$, $\bb_{k-1}^*\gets\bb_k^*+\mu\bb$, $\bb_k^*\gets -\mu_{k,k-1}\bb_k^*+(B_k/B)\bb$, ''
p. 95\quad line 10, instead of ``it itself'' read ``is itself''
p. 101\quad line 7, instead of ``$n+1\times n$'' read ``$(n+1)\times n$''
p. 106\quad Exercise 28, instead of ``In'' read ``in''
p. 106\quad line -3, instead of ``accordingly'' read ``accordingly.''
p. 107\quad line 2, instead of ``Chapter 3.)'' read ``Chapter 3).''
p. 108\quad line 3, instead of ``[Knu1]'' read ``[Knu2]''
p. 110\quad last line of Algorithm 3.1.1, instead of ``got to'' read ``go to''
p. 114\quad line -4, instead of ``$s=\prod_p p^{v_p(s)}$'' read ``$s=u\prod_p p^{v_p(s)}$''
p. 114\quad line -3, instead of ``where'' read ``where $u$ is a unit,''

p. 117\quad lines 12 to 16, replace the two sentences starting with ``We can still divide'' and ending with ``algorithm.'' by
}
\smallskip
``We could still try to divide $A$ and $B$ by their content from time to time 
(say every 10 iterations), but this would usually be a very bad idea (see 
Exercise 4).''
\smallskip
{\obeylines
p. 117\quad end of step 1, instead of ``, $h\gets1$ and $c\gets 0$.'' read `` and $h\gets1$.
p. 117\quad replace completely step 3 by
}
\smallskip
{\sans\stno{``3.}\quad [Reduce remainder] Set $A\gets B$, $B\gets R/(gh^\delta)$,
$g\gets\ell(A)$, $h\gets h^{1-\delta}g^\delta$ and go to step 2.
(Note that all the divisions which may occur in this step give
a result in the ring $\Cal R$.)}''
\smallskip
{\obeylines
p. 120\quad line 13, instead of ``$\ell(A)^{2m-2}$'' read ``$\ell(A)^{m-1+\deg(A')}$''
p. 120\quad line -8, instead of ``$a^{2m-1}$'' read ``$a^{m+\deg(A')}$''
p. 120\quad line -7, instead of ``proposition.'' read ``proposition. Note that we have $\deg(A')=m-1$ except when the characteristic of $R$ is non-zero and divides $m$.''
p. 121\quad lines 1 to 3, suppress the two sentences ``Contrary to ... Exercise 4).''
p. 124\quad lines -10 and -9, replace the sentence ``For $k\ge2$,...$T_k=T_{k-1}/V_k$.'' by
``For $k\ge1$, set $V_{k+1}=(T_k,V_k)$ if $p\nmid k$, $V_{k+1}=V_k$ if $p\mid k$, and $T_{k+1}=T_k/V_{k+1}$.''
p. 125\quad line 1, instead of ``$A=\in\F_p[X]$'' read ``$A\in\F_p[X]$''
p. 125\quad line -6, instead of `` and go to step 2'' read ``. Go to step 2.''
p. 126\quad line 3, instead of ``(see Knu2])'' read ``(see [Knu2])''
p. 128\quad lines 1 and 2 of step 2, instead of ``Set $C\gets T$ \dots $C\gets C+D$.'' read ``Set $C\gets T$ and then repeat $d-1$ times $C\gets T+C^2\bmod A$.''
p. 128\quad line -21 to -19, instead of ``Knuth gives \dots power of 2'' read ``Knuth gives $C\gets C+C^2\bmod A$, but this should be instead, as above, $C\gets T+C^2\bmod A$''
p. 131\quad line 3 of Step 1, add ``$\pmod{A(X)}$'' at the end of the formula
p. 132\quad line 2, instead of ``degree $n$,'' read ``degree $n$ (with $p\ge3$),''
p. 132\quad line 2 of step 4 of Algorithm 3.4.11, instead of ``$\deg(D)>1$'' read ``$\deg(D)>0$''
p. 132\quad line 3 of step 4 of Algorithm 3.4.11, instead of ``computations'' read ``computation''
p. 132\quad end of Algorithm 3.4.11, put the ``3'' on the same line as ``go to step'' (this is not a misprint, but an important \TeX nical change)
p. 135\quad line -15, instead of ``any factor of $A$'' read ``up to sign, any factor of $A$''
p. 136\quad line -9, instead of ``$S\equiv(VD\bmod A_e)\pmod p$ and $T\equiv(UD\bmod B_e)\pmod p$'' read ``$S\equiv VD+WA_e\pmod p$ and $T\equiv UD-WB_e\pmod p$ for some polynomial $W$''
p. 137\quad line -12, instead of ``find'' read ``finds''
p. 143\quad line 1, instead of ``$n$'' read ``$m$''
p. 143\quad line 4, instead of ``$1\le j\le n$'' read ``$1\le j\le m$''
p. 143\quad line 14, instead of ``$N_i^n$'' read ``$N_i^m$''
p. 143\quad line 14, instead of ``$N_i^{n'}$'' read ``$N_i^{m'}$''
p. 143\quad line 15, instead of ``$n'\le n$'' read ``$m'\le m$''
p. 147\quad replace Exercise 4 by the following.
}
\smallskip
\exno{``4.}\quad Modify Algorithm 3.3.1 so that $A$ and $B$ are divided by 
their respective contents every 10 iterations. Experiment and convince 
yourself that this modification leads to polynomials $A$ and $B$ having much
larger coefficients later on in the Algorithm, hence that this is a bad idea.''
\smallskip
{\obeylines
p. 147\quad Exercise 5, instead of ``$r\times(A,B)$'' read ``$r\cdot(A,B)$''
p. 154\quad line 7, instead of ``More generally, for'' read ``For''
p. 155\quad line 17, instead of ``a polynomial'' read ``an irreducible polynomial''
p. 162\quad line -13, instead of ``$Z$'' read ``$\Z$''
p. 163\quad line -9, instead of ``independent'' read ``dependent''
p. 185\quad middle, instead of ``$N_{K/\Bbb Q}(x)$'' read ``${\Cal N}_{K/\Bbb Q}(x)$''
p. 189\quad {\bf Addendum.} Line -9, replace the 4 lines starting with ``We can always assume'' and ending with ``(see Exercise 17).'' by the following.
}
\smallskip
``We do however have the following corollary:
\proclaim{\bf Corollary 4.7.6.5} Let $R$ be an order in $K$
containing $\t$, let $\om_1$,\dots,$\om_n$ be the HNF basis of $R$ 
with respect to $\t$, and let $d_1=1$, $d_2$,\dots,$d_n$ be the
integers defined in the preceding corollary.
Further, let $M$ be an $R$-module of rank $n$
over $\Z$ and let $(A,d)$ be its HNF with respect to the basis
$\om_1$,\dots,$\om_n$, where $d$ is the denominator and $A=(a_{i,j})$
is an integral matrix in upper triangular HNF. Then for every $i$ and
$j$ with $i\le j$, $a_{j,j}$ divides $a_{i,j}$ and 
$a_{j,j}$ divides $\dfrac{d_j}{d_i}a_{i,i}$. In other words, the HNF
basis of $M$ has the form
$$\alpha_j=\frac{z_j}d\left(\om_j+\sum_{1\le i<j}h_{i,j}\om_i\right)
\enspace,$$
where the $z_j$ are positive integers such that 
$z_j\mid\dfrac{d_j}{d_i}z_i$ for $i<j$ and the $h_{i,j}$ satisfy
$0\le h_{i,j}<z_i/z_j$ for $i<j$. Furthermore, $z_1$ is the smallest
positive element of $dM\cup\Z$.\endproclaim
{\it Proof.\/} Let $M_R$ be the HNF matrix of $R$ on the powers of $\t$, and
$(B,d)$ be the HNF matrix of the module $M$ on the powers of $\t$.
It is clear that we have $A=M_R^{-1}B$, and the corollary follows
immediately by expanding the matrix product and using Theorem 
4.7.5 and Corollary 4.7.6.\fp''
\smallskip
{\obeylines
p. 197\quad line 18, instead of ``$\goth p_i=p\Z_K+T_i(\theta)$'' read $\goth p_i=p\Z_K+T_i(\theta)\Z_K$''
p. 197\quad line -11, instead of ``$Z_K$'' read ``$\Z_K$''
p. 198\quad line -11, instead of ``$\goth p_i=p\Z_K+T_i(\theta)$'' read $\goth p_i=p\Z_K+T_i(\theta)\Z_K$''
p. 205\quad middle, instead of ``in the case of quadratic fields in Chapter 5.'' read
``for quadratic fields in Chapter 5 and for general number fields in Chapter 6.''
p. 208\quad line 6, instead of ``$R$'' read ``$\Bbb R$''
p. 211\quad line 8, instead of ``Although more ... preferred.'' read ``Although Algorithm 4.9.10 is more pleasing to the mind, Algorithm 4.9.9 is considerably faster and should therefore be preferred in practice.''
p. 211\quad line -1, instead of ``$r_1$'' read ``$r_1+r_2$''
p. 216\quad lines -9 to -7, instead of ``If $x\in\Z_K$\dots $x-y\in p\Z_K$'' read ``If $x\in\Z_K$, show that there exists a unique $\eps\in\{-1,0,+1\}$ such that $$x^{(\N\p-1)/2}\equiv\eps\pmod \p,$$ where we write $x\equiv y\pmod\p$ if $x-y\in\p$''
p. 217\quad Exercise 25 line 4, instead of ``$\alpha$'' read ``$\alpha^k$''
p. 217\quad {\bf Addendum.} Add the following exercise.
}
\smallskip
\exno{``28.}\quad Let $\goth p$ be a (non-zero) prime ideal in $\Z_K$ for some 
number field $K$, let $e=e(\goth p/p)$ be its ramification index, let 
$\goth p=p\Z_K+\alpha\Z_K$ be a two-element representation of $\goth p$, and
finally let $v=v_{\goth p}(\alpha)$. Let $a\ge1$ and $b\ge1$ be integers. 
By computing $\goth q$-adic valuations for each prime ideal $\goth q$, show 
that $$p^a\Z_K+\alpha^b\Z_K=\goth p^{\min(ae,bv)}\enspace.$$Deduce from this
formulas for computing explicitly $\goth p^k$ for any $k\ge1$.''
\smallskip
{\obeylines
p. 225\quad middle, replace ``$\longmapsto$'' by ``$\longrightarrow$'' four times
p. 225\quad line -6, instead of ``${}\le0$'' read ``${}\le1$''
p. 226\quad line -9, instead of ``i.e'' read ``i.e.''
p. 226\quad line -7, instead of ``to $f$'' read ``to $(a,b,c)$''
p. 226\quad line -5, instead of ``$[-\frac12,\frac12)$'' read ``$[-\frac12,\frac12[$''
p. 226\quad line -3, instead of ``class of'' read ``class of positive definite''
p. 227\quad line 1 of Lemma 5.3.4, instead of ``is a'' read ``be a''
p. 229\quad line 8, instead of ``occurs for'' read ``occurs only for''
p. 230\quad line -9, insert ``For $D=-N$, '' before ``Algorithm''
p. 230\quad line -7, instead of ``adapted'' read ``adapted to compute $H(N)$ itself, ''
p. 236\quad step 6 of Algorithm 5.4.1, replace by:
}
\smallskip
{\sans\stno{``6.}\quad [Initialize order] Set $n\gets hn$.\smallskip
\stno{7.} [Compute the order of $g$ mod $L\cdot S$] (Here we know that
$g^n\in L\cdot S$). For each prime $p$ dividing $n$, do the
following: set $S_1\gets g^{n/p}\cdot S$ and sort $S_1$. If there
exists a $z\in L$ such that $z\in S_1$, set $n\gets n/p$ and go to 
step 7.''}
\smallskip
{\obeylines
p. 236\quad line -7, instead of ``{\sans 7.}'' read ``{\sans 8.}''
p. 236\quad line -6, instead of ``$q\gets\lfloor\sqrt n\rfloor$'' read ``$q\gets\left\lceil\sqrt n\right\rceil$''
p. 236\quad line -4, instead of ``Note that the'' read ``The''
p. 236\quad line -1, instead of ``step 7'' read ``step 8''
p. 237\quad line 3, remove ``in that case''
p. 237\quad line 4, instead of ``step 7'' read ``step 8''
p. 237\quad line -20, instead of ``and step 6'' read ``and step 7''
p. 238\quad lines 6 and 7, instead of ``step 6'' read ``step 7''
p. 243\quad line -11, instead of ``involves'' read ``involve''
p. 246\quad line 3, instead of ``mod $p$ using'' read ``mod $4p$ by a simple modification of''
p. 246\quad step 1, instead of ``Using Algorithm 1.5.1\dots $\leg Dp=1$.'' read ``For the first $b$ values of $p$ such that $\leg Dp=1$, compute $b_p$ such that $b_p^2\equiv D\pmod{4p}$ using Algorithm 1.5.1 (and modifying the result to get the correct parity).''
p. 247\quad line 9, instead of ``[Buc-Dul]'' read ``[Buc-D\"ul]''
p. 249\quad line 4, instead of ``[McCur-Haf]'' read ``[Haf-McCur1]''
p. 249\quad line -3 and -2, instead of ``[Buc-Dul]'' read ``[Buc-D\"ul]''
p. 253\quad line 14, instead of ``[Buc-Dul]'' read ``[Buc-D\"ul]''
%p. 259\quad line -1, replace ``one-to-one.\fp'' by ``one-to-one.
%Finally, from the results of Section 5.7 it follows that $\rho$ acts transitively on the set of reduced forms equivalent to $f$.\fp''
p. 265\quad line 1 after Algorithm 5.7.1, instead of ``note that the'' read ``the''
p. 274\quad line 18, instead of ``Shanks'' read ``Shanks's''
p. 274\quad line 18, instead of ``an algorithm in $O(D^{1/4+\epsilon})$'' read ``a $O(D^{1/4+\epsilon})$ algorithm''
p. 275\quad line 1, instead of ``{\it distance}'' read ``distance''
p. 282\quad line 11, instead of ``any number field'' read ``the representation of algebraic numbers (and not only units), and to any number field''
p. 283\quad middle, instead of
$$L_C(x)=(\ln\sigma_1(x),\dots,\ln\sigma_{r_1}(x),\ln\sigma_{r_1+1}(x),\dots,\ln\sigma_{r_1+r_2}(x))\enspace,$$
read
$$L_C(x)=(\ln\sigma_1(x),\dots,\ln\sigma_{r_1}(x),2\ln\sigma_{r_1+1}(x),\dots,2\ln\sigma_{r_1+r_2}(x))\enspace,$$
p. 283\quad line -11, instead of ``and it is easy to check that this distance $\Delta_C$ belongs to one of the hyperplanes $\sum_ix_i=2ik\pi$ for $k\in\Z$'' read ``and it is clear that the real part of $\Delta_C$ lies in the hyperplane $\sum_ix_i=0$''
p. 291\quad lines 10 and 13 instead of ``$C$'' read ``$A$''
p. 292\quad line -4 instead of ``$C$'' read ``$A$''
p. 292\quad line -3, instead of ``$m(Z/5\Z)$'' read ``$m(\Z/5\Z)$''
p. 294\quad suppress Exercise 24 (it is solved in the text)
p. 296\quad {\bf Addendum.} End of Exercise 27, add the following:
}
\smallskip
\indent ``c) Using the Polya-Vinogradov inequality (see Exercise 8 of
Chapter 9), give a better explicit upper bound for $h(D)$, asymptotic to
$\frac1{2\pi}\sqrt f\ln f$.''
\smallskip
{\obeylines
p. 304\quad line -10, instead of ``$\gamma_i$'' read ``$\ov{\gamma_i}$''
p. 304\quad line -5, instead of ``$\gamma_j$'' read ``$\ov{\gamma_j}$''
p. 305\quad step 3 of Algorithm 6.1.8, instead of ``$\om_i$,'' read ``$\om_i$ (which will be the inverse of an integer by Corollary 4.7.6),''
p. 305\quad step 3 of Algorithm 6.1.8, instead of ``$d\gets D/G^2$'' read ``$d\gets D\cdot G^2$''
p. 313\quad line 2, instead of ``{\it (deterministic)\/}'' read ``{\it probabilistic\/}''
p. 313\quad lines -2 and -1, instead of ``The details are left to the reader'' read
``This will be done in the algorithm given below.''
p. 316\quad replace steps 13 to 15 of Algorithm 6.2.9 by the following.
}
\smallskip
{\sans\stno{``13.}\quad [Factor $m(X)$] (We know that $m(X)$ is a squarefree 
product of linear polynomials.) By using one of the final splitting methods
described in Section 3.4, or simply by trial and error if $p$ is small, factor
$m(X)$ into linear factors as $m(X)=m_1(X)\cdots m_k(X)$.\smallskip
\stno{14.}\quad [Split $H$] Let $d=\dim_{\F_p}(\ov{H})$. For $r=1$,
\dots, $k$ do as follows. Set $\beta_r\gets m_r(\alpha)$, let $M_r$ be the
$n\times(d+n)$ matrix over $\F_p$ whose first $d$ columns give the basis of
$\ov{H}$ and the last $n$ express $\om_i\beta_r$ on the integral basis. 
Finally, let $\ov{H_r}$ be the image of $M_r$ computed using Algorithm 2.3.2.
\smallskip
\stno{15.}\quad [Update list] Remove $\ov{H}$ and add $\ov{H_1}$,\dots,
$\ov{H_k}$ to the list $\Cal L$, set $c\gets c+k-1$ and go to step 8.}''
\smallskip
{\obeylines
p. 316\quad line 13, add: ``The validity of steps 14 and 15 of the algorithm is left as an exercise for the reader (Exercise 27).''
p. 323\quad line -7, instead of ``The one'' read ``The algorithm''
p. 327\quad line 10, instead of ``7, 8, 9 and 10'' read ``7, 8, 9, 10 and 11''
p. 332\quad line 5, instead of ``$b_k+2a_k$'' read ``$m_k+2l_k$''
p. 341\quad line 1, instead of ``we cannot'' read ``when $3\mid m$ we cannot'' 
p. 341\quad line 7, instead of ``prime'' read ``primes''
p. 344\quad line -6, instead of ``$,(\om-b(2+a^2)/3)\Z$'' read ``$+(\om-b(2+a^2)/3)\Z$''
p. 345\quad line 5, instead of ``$\p_1\in\p_1p_2$'' read ``$\p_1\subset\p_2$''
p. 345\quad line 16, instead of ``$a^2b^4\equiv1\mod27$'' read ``$a^2b^4\equiv1\pmod{27}$''
p. 348\quad line 3, instead of ``an ideal'' read ``a vector $v$ as above and an ideal''
p. 348\quad line 3, instead of `` this'' read ``, this''
p. 349\quad line 7, instead of ``a $(r_1+$'' read ``an $(r_1+$''
p. 349\quad line 15, instead of ``$\goth p_i^{e_i}$'' read ``$\goth p_i$''
p. 349\quad line 22, instead of ``the zero vector'' read ``$v$ equal to the zero vector''
p. 349\quad line -5, instead of ``step 5'' read ``step 4''
p. 350\quad line 18, instead of ``step 10'' read ``step 9''
p. 350\quad line 20, instead of ``$MC$'' read ``$M_C$''
p. 354\quad middle, instead of ``Hermite reductions'' read ``Smith reduction matrices''
p. 356\quad line 2 of Step 7, instead of ``$r_1\le i\le r_u$'' read ``$r_1<i\le r_u$''
p. 356\quad replace Exercise 3 by the following:
}
\smallskip
\exno{``3.}\quad (F. Diaz y Diaz.) With the notations of Theorem 6.1.4,
show that a restatement of the Dedekind criterion is the following.
Let $r_i(X)$ be the remainder of the Euclidean division of $T(X)$ by
$t_i(X)$. We have evidently $r_i\in p\Z[X]$. Set $d_i=1$ if $e_i\ge2$
and $r_i\in p^2\Z[X]$, $d_i=0$ otherwise. Then in (3) we can take
$U(X)=\prod_{1\le i\le k}t_i^{e_i-d_i}$. In particular, $\Z[\theta]$
is $p$-maximal if and only if $r_i\notin p^2\Z[X]$ for every $i$ such
that $e_i\ge2$.''
\smallskip
{\obeylines
p. 357\quad Exercise 10, question c) should be on the next line
p. 359\quad add the following exercise:
}
\smallskip
\exno{``27.}\quad Let $m(X)=m_1(X)\cdots m_k(X)$ be the decomposition of
$m(X)$ obtained in step 13 of Algorithm 6.2.9. For $1\le r\le k$, let $e_r$
be a lift to $\Cal O$ of $m_r(\alpha)$, and set $H_r=H+e_r\Cal O$. Show that
$H=H_1\cdots H_r$, and hence that steps 14 and 15 of Algorithm 6.2.9 are
valid. (Note: the $e_r$ are {\it not} orthogonal idempotents.)''
\smallskip
{\obeylines
p. 369\quad line 6, instead of ``[Kam]'' read ``([Kam])''
p. 369\quad lines 6-7, instead of ``and it is possible\dots fields'' read ``and finally for all number fields in 1994 by Merel ([Mer])''
p. 373\quad line -14, instead of ``{\it There exists a unique isogeny $\hat\phi$\/}'' read ``{\it Let $\phi$ be an isogeny from $E$ to $E'$. There exists a unique isogeny $\hat\phi$ from $E'$ to $E$\/}''
p. 376\quad lines 16 and 17, instead of the given formula for $j((1+i\sqrt{15})/2)$ read
}
\smallskip
$$\alignat3 j((1+i\sqrt{15}))/2)&=\dfrac{-191025-85995\sqrt5}{2}\cr
&=\dfrac{1-\sqrt5}{2}\left(\dfrac{75+27\sqrt5}{2}\right)^3=
1728-3\left(\dfrac{273+105\sqrt5}{2}\right)^2\cr
\endalignat$$
\smallskip
{\obeylines
p. 384\quad line 3, instead of ``{\it $f$ is equal to $(2\pi)^{-s}\Gamma(s)L(E,s)=N^{-s/2}\Lambda(E,s)$\/}'' read ``{\it $f(it/\sqrt{N})$ is equal to $\Lambda(E,s)$\/}''
p. 384\quad line 14, instead of ``tables).'' read ``tables.)''
p. 384\quad line -1 and 385 line 1, instead of ``{\it $f_E(\tau)=\sum_{n\ge1}a_nq^n$ the inverse Mellin transform of $(2\pi)^{-s}\Gamma(s)L(E,s)$\/}'' read ``{\it let $f_E(\tau)=\sum_{n\ge1}a_nq^n$, so that the Mellin transform of $f_E(it/\sqrt{N})$ is equal to $\Lambda(E,s)$\/}''
p. 385\quad the 2 middle paragraphs must of course be completely rewritten in view of Wiles's proof of the Taniyama-Weil conjecture in the semistable case
p. 387\quad lines 11 to 15 instead of ``J.-F.~Mestre \dots (see
[Fer])'' read ``Using a construction of J.-F.~Mestre (see [Mes3] and Exercise 9), Mestre and Nagao have obtained infinite families of curves of rank greater or equal to 13 (see [Mes5] and [Nag]), and using Mestre's construction, several authors have obtained individual curves of much higher rank, the current record being rank 21 by Nagao and Kouya (see [Mes4], [Fer] and [Nag-Kou])''
p. 389\quad middle, instead of ``[Sil]'' read ``the first printing of [Sil]''
p. 394\quad line -3, instead of ``$\lambda X+A$'' read ``$\lambda X+B$''
p. 395\quad step 1 line 3, replace ``The assignments\dots values).'' by the following: ``The assignments given in this algorithm for these maps and for $g$ are formal, i.e.~we assign polynomials or rational functions, not values. In addition, it is understood that the modifications of $g$ imply the modifications of the coefficients $s_i$.)''
p. 395\quad replace the first five lines of step 2 by the following:
}
\smallskip
{\sans\stno{``2.}\quad \stno{2.} [Send $P_0$ to $(0:0:1)$] If $w_0\neq0$, set
$(m_1,m_2,m_3)\gets(w_0m_1-u_0m_3,w_0m_2-v_0m_3,w_0m_3)$, 
$(n_1,n_2,n_3)\gets(w_0n_1+u_0n_3,w_0n_2+v_0n_3,w_0n_3)$,
$g\gets g(w_0U+u_0W,w_0V+v_0W,w_0W)$ and go to step 3.
Otherwise, if $u_0\neq0$, set
$(m_1,m_2,m_3)\gets(u_0m_3,u_0m_2-v_0m_1,u_0m_1)$,
$(n_1,n_2,n_3)\gets(u_0n_3,u_0n_2+v_0n_3,u_0n_1)$,
$g\gets g(u_0W,u_0V+v_0W,u_0U)$ and go to step 3. Finally, if''}
\smallskip
{\obeylines
p. 395\quad replace lines -2 and -1 by the following: ``$(m_1,m_2,m_3)\gets (c_3m_1+c_2m_3,c_3m_2+\lambda c_2m_3,c_3m_3)$, $(n_1,n_2,n_3)\gets(c_3n_1-c_2n_3,c_3n_2-\lambda c_2n_3,c_3n_3)$, $g\gets g(c_3 U-c_2 W,c_3V-\lambda c_2 W,c_3 W)$ and go to step 5.''
p. 396\quad lines 4 and 5, replace by ``$(m_3,m_2-\lambda m_1,m_1)$, $(n_1,n_2,n_3)\gets(n_3,n_2+\lambda n_3,n_1)$ $g\gets g(W,V+\lambda W,U)$, then set $\lambda\gets0$.
p. 396\quad line 10, instead of ``$c_2(m_1,m_2)m_3$'' read  ``$c_2(m_1,m_2)m_3)$''
p. 397\quad middle instead of  ``$p>19$'' read ``$p>457$''
p. 397\quad line 2 of Algorithm 7.4.12 instead of ``$p\ge 13$'' read ``$p>457$''
p. 398\quad line 14, instead of ``$100$, say'' read ``$457$. Note that one can prove that $457$ is best possible, but it is easy to modify slightly the algorithm so that it works for much lower values of $p$.''
p. 398\quad line -2 and -1, replace the last sentence by ``Using recent new ideas of Elkies, Atkin has been able to deal with a 200-digit prime. Finally, combining this with an idea of Couveignes and Morain, Morain has dealt with a 250-digit prime.''
p. 400\quad line -1, instead of ``$t1$'' read ``$t_1$''
p. 401\quad line 1, instead of ``$r_1*a_1$'' read ``$r_1a_1$''
p. 401\quad line 3 of step 15, instead of ``goto step 1'' read ``goto step 2''
p. 408\quad line 10, instead of ``{\sans , $a\gets b$, and if $a\le1$, set $a\gets1$ and go to step 4.}'' read ``{\sans and $a\gets\max(b,1)$.}''
p. 409\quad Exercise 1, replace the first sentence by ``Given $c_4$ and $c_6$ computed by Formulas (7.1), we would like to recover the $b_i$ and $a_i$, where we assume that the $a_i$ are in $\Z$.''
p. 415\quad line -9, instead of ``possible'' read ``usually possible''
p. 415\quad line -8, instead of ``finite set'' read ``reasonably small finite set''
p. 418\quad lines 8, 16, 19 and -6, instead of ``Lehmann'' read ``Lehman''
(the last three corrections are not necessary if the big change below is made)
p. 418\quad line -8, instead of ``{\it (*)\/}'' read ``{\it $(*)$\/}''
(not necessary if the big change below is made)
p. 418\quad {\bf Addendum.} Line 14 to the end of Section 8.4, replace completely by:
}
\smallskip
``Although several methods were introduced to improve trial division (which is,
we recall, a $O(N^{1/2+\epsilon})$ algorithm), the first method which has
a running time which could be proved to be substantially lower was introduced 
by Lehman (see [Leh1]). Its execution time is at worst 
$O(N^{1/3+\epsilon})$, and it is indeed faster than trial division already 
for reasonably small values of $N$. The algorithm is as follows.
\smallskip
\proclaim\nofrills{\bf Algorithm 8.4.1}{\rm\ (Lehman). }{\sans Given an integer
$N\ge3$, this algorithm finds a non-trivial factor of $N$ if $N$ is
not prime, or shows that $N$ is prime.\smallskip
\stno{1.}\quad [Trial division] Set $B\gets\lfloor N^{1/3}\rfloor$. Trial divide
$N$ up to the bound $B$ using Algorithm 8.1.1. If any non-trivial factor is
found, output it and terminate the algorithm. Otherwise set $k\gets0$.
\smallskip
\stno{2.}\quad [Loop on $k$] Set $k\gets k+1$. If $k>B$, output the fact that $N$
is prime and terminate the algorithm. Otherwise, set $r=1$  and $m=2$ if $k$
is even, $r=k+N$ and $m=4$ if $k$ is odd.\smallskip
\stno{3.}\quad [Loop on $a$] For all integers $a$ such that $4kN\le a^2\le 4kN+B^2$
and $a\equiv r\pmod m$ do as follows. Set $c\gets a^2-4kN$. Using Algorithm
1.7.3, test whether $c$ is a square. If it is, let $c=b^2$, output
$\gcd(a+b,N)$ (which will be a non-trivial divisor of $N$) and terminate the
algorithm. Otherwise, use the next value of $a$ if any. If all possible
values of $a$ have been tested, go to step 2.}\endproclaim
\smallskip
{\it Proof.\/} (D. Zagier) If no factors are found during step 1, this means
that all the prime factors of $N$ are greater than $N^{1/3}$ hence $N$ has at 
most two prime factors. 

Assume first that $N$ is prime. Then the test in step 3 can never succeed.
Indeed, if $a^2-4kN=b^2$ then $N\mid a^2-b^2$ hence $N\mid (a-b)$ or 
$N\mid(a+b)$ so $a+b\ge N$, but this is impossible since the given inequalities
on $k$ and $a$ imply that $a<2N^{2/3}+1$ and $b<N^{1/3}$ so $N\le 13$. An easy
check shows that for $3\le N\le 13$, $N$ prime the test in step 3 does not
succeed (note that for $N=2$, $k=1$ and $a=3$ it does).

Assume now that $N$ is composite, so that $N=pq$ with $p$ and $q$ not
necessarily distinct primes. We may assume that $p\le q$, hence 
$N^{1/3}<p\le q$, or in other words $1\le q/p<N^{1/3}$. Consider the
continued fraction expansion of $q/p$. The successive convergents $u_n/v_n$
are such that $u_n$ and $v_n$ form an increasing sequence. Let $n$ be the
unique index such that $u_nv_n<N^{1/3}<u_{n+1}v_{n+1}$ (since $pq>N^{1/3}$
such an $n$ exists), and set $r=u_n$, $s=v_n$, $r'=u_{n+1}$, $s'=v_{n+1}$.
Then, using the elementary properties of continued fractions, we have
$$\left|\dfrac qp-\dfrac rs\right|\le\left|\dfrac{r'}{s'}-\dfrac rs\right|=
\dfrac{1}{ss'}\enspace,$$but also, since $s/r$ and $s'/r'$ are successive 
convergents to $p/q$, we have
$$\left|\dfrac pq-\dfrac sr\right|\le\left|\dfrac{s'}{r'}-\dfrac sr\right|=
\dfrac{1}{rr'}\enspace.$$
Thus we obtain $|pr-qs|\le p/s'$ from the first inequality, $|pr-qs|\le q/r'$
from the second, and taking the geometric mean this gives
$$|pr-qs|\le\sqrt{\dfrac{pq}{r's'}}<N^{1/3}\enspace.$$ If we set $k=rs$ and
$a=ps+qr$, we have $a^2-4kN=(ps-qr)^2$. The congruences for $a$ are easily
checked, and so we see that step 3 succeeds with these values, thus proving
the validity of the algorithm.\fp

For each value of $k$ there are at most 
$1/2(\sqrt{4kN+N^{2/3}}-\sqrt{4kN})\approx N^{1/6}k^{-1/2}/8$ values of $a$,
and since $\sum_{k\le x} k^{-1/2}\approx 2x^{1/2}$, the running time of the
algorithm is indeed $O(N^{1/3+\epsilon})$ as claimed.

We refer to [Leh1] for ways of fine tuning this algorithm, which is now only
of historical interest.''
\smallskip
{\obeylines
p. 419\quad lines 10, 13 and -7, replace ``Lehmann'' by ``Lehman''
(the first two are not necessary if the big change above is made)
p. 424\quad lines 1 and middle, replace ``(*)'' by ``$(*)$''
p. 431\quad line 11 instead of ``step 8'' read ``step 9''
p. 432\quad middle, remove the sentence ``We also use ... time to time''
p. 432\quad step 1 of Algorithm 8.8.2, suppress ``$P\gets1$, ''
p. 432\quad step 2 and step 4 of Algorithm 8.8.2, instead of $(P,N)$ read $(x-1,N)$
p. 432\quad step 3 of Algorithm 8.8.2, suppress ``$P\gets P\cdot(x-1)\bmod N$, ''
p. 432\quad step 3 of Algorithm 8.8.2, instead of ``$c<20$'' read ``$c<200$''
p. 440\quad lines 13 and -11, instead of ``$x\neq1\pmod q$'' read ``$x\not\equiv1\pmod q$''
p. 445\quad line -14, instead of ``$l_p(r,\max(k_1,k_2)$'' read ``$l_p(r,\max(k_1,k_2))$''
p. 457\quad line -12, instead of ``Otherwise,'' read ``Otherwise'' and line -11 instead of ``, then output'' read ``, output''
p. 458\quad line 14, instead of ``$s>n^{1/3}$'' read ``$s>N^{1/3}$''
p. 461\quad line 5, instead of ``i.e'' read ``i.e.''
p. 462\quad line 3 of step 7, instead of ``i.e'' read ``i.e.''
p. 463\quad line -13, instead of ``Miller'' read ``Elkies''
p. 467\quad line -2, instead of ``$p$ is prime'' read ``$p$ is an odd prime''
p. 468\quad {\bf Addendum.} Add the following exercises:
}
\smallskip
\exno{``7.}\quad Let $\chi$ be a character modulo $q$, where $q$ is not
necessarily prime. We will say that $\chi$ is {\it primitive\/} if for all
divisors $d$ of $q$ such that $d<q$, there exists an $x$ such that 
$x\equiv1\pmod d$ and $\chi(x)\neq1$. Set $\zeta=e^{2i\pi/q}$, and
$\psi(a)=\sum_{x\in(\Z/q\Z)^*}\chi(x)\zeta^{ax}$.
\newline\indent a) Let $a$ be such that $d=(a,q)=1$. Show that 
$\psi(a)=\ov{\chi}(a)\tau(\chi)$.
\newline\indent b) Assume that $\chi$ is a primitive character and that
$d=(a,q)>1$. Show that there exists a $u\in(\Z/q\Z)^*$ such that $au=d$. Deduce
from this that $\psi(a)=0$, and hence that the formula 
$\psi(a)=\ov{\chi}(a)\tau(\chi)$ is still valid.\smallskip
\exno{8.}\quad Let $\chi$ be a primitive character modulo $q$, as defined
in the preceding exercise, and set $S(x)=\sum_{n\le x}\chi(n)$.
\newline\indent a) Using the preceding exercise, give an explicit formula for
$\tau(\chi)S(x)$.
\newline\indent b) Deduce that 
$$\sqrt{q}\,|S(x)|\le\sum_{1\le m<q,\ m\neq q/2}\dfrac1{\sin{\frac{\pi m}{q}}}\enspace.$$
\newline\indent c) Show finally the {\it Polya-Vinogradov inequality\/}
$$|S(x)|=\left|\sum_{1\le n\le x}\chi(x)\right|\le\sqrt q\log q\enspace.''$$\smallskip
{\obeylines
p. 470\quad line -15, instead of ``$kN$'' read ``$\sqrt{kN}$''
p. 482\quad line -10, instead of ``this'' read ``this (see [Chu])''
p. 482\quad line -5, instead of ``1993'' read ``1994''
p. 484\quad middle, instead of ``simple precision'' read ``single precision''
p. 487\quad line 4, before ``The basic idea'' insert ``For complete details I refer to [Len-Len2]''
p. 495\quad line 3 of step1, instead of ``$A(X^2)=S(X)S(-X)$'' read ``$A(X^2)=\pm S(X)S(-X)$''
p. 495\quad step 2, remove the sentence ``If $R(X)$ is \dots algorithm.''
p. 497\quad line 3 of Exercise 10, instead of ``$A(X^2)=S(X)S(-X)$'' read ``$A(X^2)=\pm S(X)S(-X)$''
p. 498\quad the second paragraph has been rewritten and now reads as follows:
}
\smallskip
``Most general-purpose symbolic algebra packages have been written primarily
for applied mathematicians, engineers and physicists, and are not always
well suited for number theory. These packages roughly fall into two 
categories. In the first category one finds computer algebra
systems developed in the 1970's, of which the main representatives are 
Macsyma and Reduce.
Because of their maturity, these systems have been extensively tested and
have probably less bugs than more recent systems. In addition they are 
very often mathematically more robust. In the second category,
I include more recent packages developed in the 1980's of which the most
common are Mathematica, by Wolfram Research, Inc., Maple, by the
University  of Waterloo, Canada, and more recently Axiom, developed by
IBM and commercialized by NAG. These second-generation systems being
more recent have more bugs and have been less tested. They are also often
more prone to mathematical errors. On the other hand
they have been aggressively commercialized and as a consequence have
become more popular. However, the older systems have also been improved,
and in particular recently Macsyma was greatly improved in terms of speed,
user friendliness and efficiency and now compares very favorably to more
recent packages. 
Mathematica has a very nice user interface, and its plotting capabilities,
for example on the Macintosh, are superb. Maple is faster and often simpler
to use, and has my preference. Axiom is a monster (in the same sense that
ADA is a monster as a programming language). It certainly has a large
potential for developing powerful applications, but I do not believe that
there is the need for such power (which is usually obtained at the expense 
of speed) for everyday (number-theoretic) problems.''
\smallskip
{\obeylines
p. 499\quad middle, instead of ``Cayley/Magma, GAP, Kant'' read ``GAP, Kant, Magma, Simath''
p. 499\quad middle, replace the description of the Cayley system by the following:
}
\smallskip
``The Magma system  is designed to support fast computations in  algebra
(groups, modules, rings, polynomial rings over various kinds of coefficient
domains), number theory and finite geometry. It includes general machinery
for classical number theory (for example the ECM program of A.K.~Lenstra),
finite fields and cyclotomic fields and facilities for computing in a
general algebraic number field. It will eventually include a MPQS
factoring  algorithm, a Jacobi sum-type primality test and
a general purpose elliptic curve calculator. According to the
developers, it should eventually include ``just about all of the
algorithms of this book''. Simath, developed at the university of
Saarbrucken, is another system for number-theoretic computations which
is quite fast and has a nice user interface called simcalc.''
\smallskip
{\obeylines
p. 500\quad middle and p. 501 line 1, replace ``Symbolics Macsyma'' by ``Macsyma''
p. 500\quad line -17, instead of ``Cayley'' read ``Magma''
p. 501\quad line 5, instead of ``Symbolics version'' read ``commercial version''
p. 501\quad lines 7 to 10, replace the Macsyma ordering information by the following: ``Macsyma Inc., 20 Academy Street, Suite 201, Arlington MA 02174-6436, phone (617) 646-4550 or 1-800-MACSYMA (free from the U.S.), fax (617) 646-3161, e-mail {\tt info-macsyma\@macsyma.com}.''
p. 501\quad line -12, instead of ``forthcoming'' read ``also available''
p. 502\quad lines 1, 3 and 11, replace ``Cayley'' by ``Magma''
p. 502\quad line 4, instead of ``Appolo'' read ``HP, Appolo''
p. 502\quad For Kant, change address to ``{\tt pohst\@math.tu-berlin.de} and {\tt daberkow\@math.tu-berlin.de}''
p. 502\quad middle, add ``You can obtain Simath by anonymous ftp from {\tt ftp.math.uni-sb.de}'' 
p. 502\quad middle, add ``You can obtain Kant by anonymous ftp from {\tt ftp.math.tu-berlin.de} directory /pub/algebra/Kant''
p. 502\quad add ``{\tt ftp.math.uni-sb.de} (134.96.32.23)'' to the list of sites from where you can get Simath
p. 502\quad add ``{\tt megrez.ceremab.u-bordeaux.fr} (147.210.16.17)'' to the list of sites from where you can get Pari by anonymous ftp
p. 502\quad line -2, instead of ``128.146.7.200'' read ``128.146.110.30''
p. 502\quad line -1, instead of ``Ubasic, CC4, Frenz-Calc'' read ``Most packages''
p. 517\quad in [H-W], instead of ``{\it 5-th ed.\/}'' read ``5-th ed.''
p. 517-528\quad replace where necessary ``ed'' by ``ed.'' and ``eds'' by ``eds.''
p. 521-528\quad due to a \TeX{} mistake on my part, a number of dates and page numbers which were in the \TeX{} source have not been printed. They are as follows:
In [Arn] ``(1991)''; in [Atk1] ``(1990)''; in [Atk2] ``(1991)''; in [Bre1] ``(1985)'';
in [Buc-Dul] ``(1991) pp. 53--72''; in [Ford3] ``(1991) pp. 129--138''; in [LLMP] ``(1991)'';
in [Mor1] ``(1989)''; in [Poh4] ``(1991) pp. 173--182''; in [Pom] ``(1983) pp. 89--139''
p. 520\quad remove the four lines concerning [{\bf Len-Poh}], and insert after the paragraph concerning [Poh-Zas] the following:
``[{\bf Poh5}] M. Pohst, {\it Computational Algebraic Number Theory\/}, DMV Seminar {\bf 21}, Birkh\"auser, Boston, 1993.
\smallskip
Writeup of a course given by the author in 1990. This can be considered as an update to parts of [Poh-Zas].''
\smallskip
p. 521\quad in [Was], after the title add ``Graduate texts in Math. {\bf 83}, ''
p. 521\quad in [Adl-Hua] change title to ``Primality testing and Abelian varieties over finite fields''
p. 521\quad in [APR], instead of ``Ann of Math.'' read ``Ann. of Math.''
p. 521\quad in [AGP], instead of ``in preparation'' read ``{\it There are infinitely many Carmichael numbers\/}, Ann. of Math. (1994), to appear
p. 521\quad replace the reference [Arn] by
``[{\bf Arn}] F. Arnault, {\it The Rabin-Miller primality test: composite numbers which pass it\/}, Math. Comp., to appear.''
p. 521\quad in [Atk-Mor], instead of ``(to appear)'' read ``{\bf 61} (1993), 29--68''
p. 522\quad instead of ``[Buc-Dul]'' read ``[Buc-D\"ul]''
p. 522\quad replace the entry for [BFP] by 
``[{\bf BFP}] J.~Buchmann, D.~Ford and M.~Pohst, {\it Enumeration of quartic fields of small discriminant\/}, Math. Comp. {\bf 61} (1993), 873--879.''
p. 525\quad replace the entry for [Kam] by
``[{\bf Kam}] S.~Kamienny, {\it Torsion points on elliptic curves and $q$-coefficients of modular forms\/}, Invent. Math. {\bf 109} (1992), 221--229.''
p. 525\quad replace the entry for [LaM-Odl] by
``[{\bf LaM-Odl}] B.~LaMacchia and A.M.~Odlyzko, {\it Solving large sparse linear systems over finite fields\/}, in Advances in cryptology: Crypto 90, A. Menezes and S. Vanstone (eds.), LN in Comp. Sci. {\bf 537}, Springer-Verlag (1991), 109--133''
p. 525\quad in [Leh1] instead of ``Lehmann'' read ``Lehman''
p. 525\quad instead of ``[Len-Len]'' read ``[Len-Len1]''
p. 525\quad after [Len-Len] insert
``[{\bf Len-Len2}] A.~K.~Lenstra and H.~W.~Lenstra (eds.), {\it The development of the number field sieve\/}, LN in Math. {\bf 1554}, Springer-Verlag, Berlin, Heidelberg, New-York, 1993.''
p. 525\quad in [LLMP], replace ``manuscript'' by ``in [Len-Len2], pp. 11--42
p. 525\quad after [McKay] insert
``[{\bf Mer}] L.~Merel, {\it in preparation\/}''
p. 525\quad after [Mes4] add the following reference:
``[{\bf Mes5}] J.-F.~Mestre, private communication.''
p. 525\quad in [Mol-Wil], replace ``(to appear)'' by ``{\bf 41} (1992) 259--308''
p. 526\quad after [Mor-Nic], add the following references: 
``[{\bf Nag}] K.~Nagao, {\it An example of elliptic curve over $\Q(T)$ with rank $\ge13$\/}, to appear''
``[{\bf Nag-Kou}] K.~Nagao and T.~Kouya, {\it An example of elliptic curve over $\Q$ with rank $\ge21$\/}, to appear''
p. 526\quad in [Nic], instead of ``A. Lenstra'' read ``A.~K.~Lenstra''
p. 527\quad in [Schn-Euch], add `` {\bf 529}'' after ``Sci.'', and replace ``(to appear)'' by ``(1991), 68--85''
p. 527\quad replace reference [Sey2] by the following:
``[{\bf Sey2}] M.~Seysen, {\it Simultaneous reduction of a lattice basis and its reciprocal basis\/}, Combinatorica {\bf 13} (1993), 363--376.''
p. 527\quad in [Star] add ``(1973)''
p. 529-534\quad add index entries for ``Chinese remainder theorem, 19'', ``continued fraction, 260, 264, 418'', ``Elkies, N., 463'', ``Fermat's little theorem, 414, 432, 442'', ``Fermat's last theorem, 150, 451'', ``Newton's method, 38, 44'', ``$p$-adic factorization, 357'', ``powering algorithms, 42, 458'', ``prime number theorem, 212'', ``prime ideal theorem, 212'', ``pseudo-prime, 414'', ``square root, in $\Z$, 38, modulo $p$, 31'', ``Weil conjectures, 380'', ``Wieferich congruence, 451''
p. 531\quad instead of ``Lehmann, S.'' read ``Lehman, S.''
p. 532\quad instead of ``Manin, Y'' read ``Manin, Y.''
p. 532\quad remove page 463 to the entry for Miller, V.
}
\end