% To be compiled with AmsTeX 2.0 or later \documentstyle{amsppt} \magnification=\magstephalf \NoBlackBoxes % \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\al{\alpha} \def\eps{\varepsilon} \def\Gal{\operatorname{Gal}} \def\GF{\operatorname{GF}} \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 Third and Fourth Corrected Printings of} \smallskip \centerline{\bf A Course in Computational Algebraic Number Theory} \smallskip \centerline{by \bf Henri Cohen} \smallskip \centerline{(20001127 version)} \bigskip {\bf Warning.} The errata presented here are of course to be taken into account for the first and second printing, but the page and line numbering given here corresponds to the third and fourth printings and is quite different from that of the preceding printings. \medskip {\obeylines Graduate Texts in Mathematics 138, Springer-Verlag, 1993, Third, Corrected Printing 1996, XX + 545 pages. ISBN 3-540-55640-0 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-55640-0 Springer-Verlag New York Berlin Heidelberg \smallskip \bigskip p. VI\quad at Shanks, add the footnote ``Daniel Shanks died on September 6, 1996'' p. VI\quad middle and p. VII line 11, instead of ``Francois Dress'' read ``Fran\c cois Dress'' p. VI\quad line -1, instead of ``Jean-Francois Mestre, Francois Morain'' read ``Jean-Fran\c cois Mestre, Fran\c cois Morain'' p. 11\quad just before ``Quite a different way'' insert the following long text} \smallskip ``Perhaps surprisingly, we can easily improve on Algorithm 1.2.4 by using a flexible window of size at least $k$ bits, instead of using a window of fixed size $k$. Indeed, it is easy to see that any positive integer $N$ can be written in a unique way as $$N=2^{t_0}(a_0+2^{t_1}(a_1+\cdots+2^{t_e}a_e))$$ where $t_i\ge k$ for $i\ge1$ and the $a_i$ are odd integers such that $1\le a_i\le 2^k-1$ (in Algorithm 1.2.4 we took $t_0=0$, $t_i=k$ for $i\ge1$, and $0\le a_i\le 2^k-1$ odd or even). As before, we can precompute $g^3$, $g^5$, \dots, $g^{2^k-1}$ and then compute $g^N$ by successive squarings and multiplications by $g^{a_i}$. To find the $a_i$ and $t_i$, we use the following immediate sub-algorithm. \proclaim\nofrills{\bf Sub-Algorithm 1.2.4.1}{\rm\ (Flexible Base $2^k$ Digits). }{\sans Given a positive integer $N$ and $k\ge1$, this sub-algorithm computes the unique integers $t_i$ and $a_i$ defined above. We use $[N]_{b,a}$ to denote the integer obtained by extracting bits $a$ through $b$ (inclusive) of $N$, where bit 0 is the least significant bit.\smallskip \stno{1.}\quad [Compute $t_0$] Let $t_0\gets v_2(N)$, $e\gets0$ and $s\gets t_0$.\smallskip \stno{2.}\quad [Compute $a_e$] Let $a_e\gets [N]_{s+k-1,s}$.\smallskip \stno{3.}\quad [Compute $t_e$] Set $m\gets [N]_{\infty,s+k}$. If $m=0$, terminate the sub-algorithm. Otherwise, set $e\gets e+1$, $t_e\gets v_2(m)+k$, $s\gets s+t_e$ and go to step 2.}\endproclaim \medskip The flexible window algorithm is then as follows. \proclaim\nofrills{\bf Algorithm 1.2.4.2}{\rm\ (Flexible Left-Right Base $2^k$ ). }{\sans Given $g\in G$ and $n\in\Z$, this algorithm computes $g^n$ in $G$. We write $1$ for the unit element of $G$.\smallskip \stno{1.}\quad [Initialize] If $n=0$, output $1$ and terminate. If $n<0$ set $N\gets-n$ and $z\gets g^{-1}$. Otherwise, set $N\gets n$ and $z\gets g$. \smallskip \stno{2.}\quad [Compute the $a_i$ and $t_i$] Using the above sub-algorithm, compute $a_i$, $t_i$ and $e$ such that $N=2^{t_0}(a_0+2^{t_1}(a_1+\cdots+2^{t_e}a_e))$ and set $f\gets e$.\smallskip \stno{3.}\quad [Precomputations] Compute and store $z^3$, $z^5$, \dots, $z^{2^k-1}$.\smallskip \stno{4.}\quad [Loop] If $f=e$ set $y\gets z^{a_f}$ otherwise set $y\gets z^{a_f}\cdot y$. Then repeat $t_f$ times $y\gets y\cdot y$.\smallskip \stno{5.}\quad [Finished?] If $f=0$, output $y$ and terminate the algorithm. Otherwise, set $f\gets f-1$ and go to step 4.}\endproclaim \medskip We have used above the word ``surprisingly'' to describe the behavior of this algorithm. Indeed, it is not a priori clear why it should be any better than Algorithm 1.2.4. An easy analysis shows, however, that the average number of multiplications which are not squarings is now of the order of $2^{k-1}+\lg|n|/(k+1)$ (instead of $2^{k-1}+\lg|n|/k$ in Algorithm 1.2.4), see Exercise 33. The optimal value of $k$ is the smallest integer satisfying the inequality $\lg|n|\le (k+1)(k+2)2^{k-1}$. In the above example where $n$ has 100 decimal digits, the flexible base $2^5$ algorithm takes on average $(3/4)332+16+332/6\approx320$ multiplications, another $3\%$ improvement. In fact, using a simple modification, in certain cases we can still easily improve (very slightly) on Algorithm 1.2.4.2, see Exercise 34.'' \smallskip {\obeylines p. 11\quad line -11, instead of ``the $2^k$ algorithm'' read ``the flexible $2^k$ algorithm'' p. 17\quad in Algorithm 1.3.7, remove the initializations ``$A\gets1$, $B\gets0$, $C\gets0$, $D\gets1$'' from step 1 and put them instead at the end of step 2 p. 45\quad add the following exercises. } \smallskip \exno{``33.}\quad Show that, as claimed in the text, the average number of multiplications which are not squarings in the flexible left-right base $2^k$ algorithm is approximately $2^{k-1}+\lg|n|/(k+1)$, and that the optimal value of $k$ is the smallest integer such that $\lg|n|\le (k+1)(k+2)2^{k-1}$. \smallskip \exno{34.}\quad Consider the following modification to Algorithm 1.2.4.2. We choose some odd number $L$ such that $2^{k-1}L-2^{k-1}$. Analyze the resulting algorithm and show that, in certain cases, it is slightly faster than Algorithm 1.2.4.2.'' \smallskip {\obeylines p. 52\quad line -1, instead of ``column'' read ``column, with $k+1\le i\le n$'' p. 69\quad step 4 of Algorithm 2.4.5, instead of ``set $k\gets k+1$ and go to step 5'' read ``set $k\gets k+1$, and if $l>1$ and $i=l$ set $l\gets l-1$, then go to step 5'' p. 72\quad line 4 of step 4 of Algorithm 2.4.8, instead of ``$W_j\gets W_j-q W_i$'' read ``$W_j\gets W_j-q W_i\bmod R$'' p. 73\quad line -3, instead of ``last $n-r+1$'' read ``last $n-r$'' p. 129\quad line 4, instead of ``$p=2$'' read ``$p>2$'' p. 129\quad line -20, instead of ``$U\circ T$'' read ``$U\circ T\bmod A$'' p. 156\quad line -17, instead of ``$A_1(b)<0$ when'' read ``$A_1(b)<0$ if and only if'' p. 157\quad line -8, instead of ``Proposition 4.8.6'' read ``Theorem 4.8.6'' p. 159\quad line -5, instead of ``$r_{i,k}$'' read ``$r_{k,i}$'' p. 159\quad line -4, instead of ``$(r_{0,k},r_{1,k},\dots,r_{n-1,k},1)$'' read ``$(r_{k,0},r_{k,1},\dots,r_{k,n-1},1)$'' and instead of ``$r_{i,k}$'' read ``$r_{k,i}$'' p. 159\quad line -3, instead of ``$r_{i,0}$'' read ``$r_{0,i}$'' p. 160\quad line 10, instead of ``$r_{i,j}$'' read ``$r_{k,i}$'' p. 161\quad middle, instead of ``This will in practice be considered as a $r_1+2r_2=n$-uplet of real numbers. Now operations'' read ``Operations'' p. 168\quad line 8 and 9, instead of ``$p$ is an odd prime'' read ``$p$ is a prime'' p. 176\quad lines 12 to 15, replace the four lines of the end of the proof starting with ``If we set $\gamma...$'' by ``It follows that the vector of the $(P(\beta_i))$ and of the $\al_{\phi(i)}$ are both solutions of the linear system $\sum_{1\le i\le n}v_i\beta_i^h=s_h$, and since the $\beta_i$ are distinct this system has a unique solution, so the vectors are equal, thus proving the proposition.'' p. 179\quad line -3 and p. 180 line -11, instead of ``$a^{m-1}$'' read ``$a^{n-1}$'' p. 184\quad line -8, instead of ``so $M\subset M'$'' read ``so $M$ annihilates $IH/IJ$ hence $M\subset M'$'' p. 193\quad line 11, add ``Note that this is simply the proof of the Chinese remainder theorem for ideals.'' p. 195\quad line 2 of Algorithm 4.7.10, instead of ``$\Z_K$-generators'' read ``$\Z$-genera\-tors'' p. 195\quad line 1 of step 3 of Algorithm 4.7.10, instead of ``$2\le i\le m$'' read ``$2\le i\le k$'' p. 195\quad line 2 of step 4 of Algorithm 4.7.10, instead of ``$j+1\le i\le m$'' read ``$j+1\le i\le k$'' p. 200\quad line 14, instead of ``$e_i=f_i$'' read ``$d_i=e_i$'' p. 201\quad line -5, instead of ``Then $y\notin xR$ and $y\p\subset xR$, hence $a=y/x$'' read ``Since $y\p\subset xR$, the element $a=y/x$'' p. 202\quad line -10, instead of ``$\displaystyle\sum_{1\le\le n}$'' read ``$\displaystyle\sum_{1\le i\le n}$'' p. 204\quad line 3 of step 3, instead of ``{\sans 0}'' read ``$0$'' p. 204\quad line 1 of step 5, instead of ``If $p\nmid A_{n,n}$,'' read ``Using Algorithm 2.4.8, replace $A$ by its HNF. Then, if $p\nmid A_{n,n}$,'' p. 206\quad line -7, instead of ``determinant $d(K)$'' read ``discriminant $d(K)$'' p. 211\quad line -13 and -12, instead of ``where $\Vert x\Vert$ denotes the absolute value of $x$ when $x$ is real and the square of the modulus of $x$ when $x$ is complex'' read ``where $\Vert\sigma(x)\Vert=|\sigma(x)|$ if $\sigma$ is a real embedding and $\Vert\sigma(x)\Vert=|\sigma(x)|^2$ if $\sigma$ is a complex embedding'' p. 216\quad line 1, instead of ``$\dfrac{1}{6}$'' read ``$\dfrac{1}{60}$'' p. 217\quad line -4, instead of ``$A\gets 8b-3a^2$'' read ``$A\gets 3a^2-8b$'' and line -2, instead of ``$(r_1,r_2)=(0,4)$ iff $D>0$ and $AB<0$'' read ``$(r_1,r_2)=(0,2)$ iff $D>0$ and either $A\le 0$ or $B\le 0$'' p. 224\quad line -2, replace 4 times small parentheses by larger ones p. 227\quad line 1, instead of ``$(-b+\sqrt{D})/2a$'' read ``$(-b+\sqrt{D})/(2a)$'' p. 234\quad line -6, instead of ``$H(0)=-1/12$'' read ``$H(N)=-1/12$'' p. 237\quad line -13, instead of ``Let $D$ be a negative fundamental discriminant'' read ``Let $D$ be a negative discriminant (not necessarily fundamental)'' p. 237\quad line -10 and -9, instead of ``entire function satisfying'' read ``entire function. If in addition $D$ is a fundamental discriminant, this function satisfies the functional equation'' p. 240\quad line 4, instead of ``time'' read ``average time'' p. 246\quad line 7, instead of ``$I_i=a_i\Z+\tau_i\Z$'' read ``$I_i=a_i(\Z+\tau_i\Z)$'' p. 246\quad line 9, instead of ``$\tau_3=ua_1\tau_2+va_2\tau_1+w\tau_1\tau_2$'' read ``$\tau_3=(d/d_0)(u\tau_2+v\tau_1+w\tau_1\tau_2)$'' p. 248\quad line 2 of step 3 of Algorithm 5.4.8, instead of ``$c_2=c_2+gd_1$'' read ``$c_2\gets c_2+gd_1$'' p. 249\quad line 2 of step 6 of Algorithm 5.4.9, instead of ``$c_3\gets v_3d+gd_1$'' read ``$c_3\gets v_3f+gd_1$'' p. 250\quad line -16, instead of ``guess that $h(D)$'' read ``guess that, for $D<-4$, $h(D)$'' p. 252\quad line 7, instead of ``[McCur-Haf]'' read ``[Haf-McCur1]'' p. 262\quad line -5, instead of ``reduced form'' read ``quadratic form'' p. 262\quad line -3, after (1) insert ``If $(a,b,c)$ is reduced, then'' p. 262\quad line -2, instead of ``More precisely'' read ``More precisely, if $(a,b,c)$ is reduced'' p. 276\quad line -7, add a white square at the end of the line p. 280\quad line -6, instead of ``positive norm.'' read ``positive norm. By abuse of notation, we will again denote by $\delta(f,g)$ the unique representative belonging to the interval $[0,R^+[$, and similarly for the distance between ideals.'' p. 282\quad line -16, instead of ``very small.'' read ``very small. More precisely, it can be proved (see [Len1]) that $\delta(f,\rho^2(f))>\ln 2$, hence the number of reduction steps is at most $4\ln(D)/\ln 2$.'' p. 289\quad line -19, instead of ``$\delta(\bold 1,f)=(eL\ln 2+\ln R)/2$'' read ``$\delta(f_0,f)=(eL\ln 2+\ln R)/2$ for some fixed form $f_0$ equivalent to $f$'' p. 290\quad line 20, instead of ``$\delta(\bold 1,f)$'' read ``$\delta(\prod_{p\le P}f_p^{e_p},f)$'' p. 290\quad line -6, instead of ``$g=\prod_{p\le P}f_p^{v_p}$'' read ``$g=\prod_{p\le P}f_p^{\eps_pv_p}$'' p. 290\quad line -1, instead of ``$f_{p_i}^{a_{i,j}}$'' read ``$f_{p_i}^{-a_{i,j}}$'' p. 291\quad line 9, instead of ``$a_{n+1,j}=$'' read ``$a_{n+1,j}\equiv$'' p. 304\quad lines -12 and -11, instead of ``again by the binomial theorem'' read ``using this time the multinomial theorem instead of the binomial theorem'' p. 321\quad step 9, instead of ``$s$'' read ``$f$'' (3 times) p. 322\quad step 14, instead of ``$r$'' read ``$s$'' (7 times) and instead of ``$d$'' read ``$r$'' (3 times) p. 340\quad line 3, instead of ``$(\ov{f},\ov{gh})=1$'' read ``$(\ov{f},\ov{g},\ov{h})=1$'' p. 343\quad line 3 of Corollary 6.4.12, instead of ``$\dfrac{-3v\pm u}{6v}$'' read ``$\dfrac{-3v\mp u}{6v}$'' p. 359\quad line 4 of step 5, instead of ``the matrix is not of maximal rank'' read ``one of the matrices $H$ or $C$ is not of maximal rank'' p. 368 and following\quad major correction (oversight in all the previous printings): exchange in most places ``$\om_1$'' and ``$\om_2$'', except p. 415 where the ``$\om_2$'' is correct. In particular, the canonical basis $(\om_1,\om_2)$ for a real elliptic curve is now such that $\om_2$ is real and $\om_1$ is in the upper half plane. Specifically, the corrections are p. 368, p. 370, p. 378, twice p. 395, five times page 396, twice p. 398 and p. 412 replace ``$\om_2/\om_1$'' by ``$\om_1/\om_2$'', twice p. 395 and twice p. 396 replace ``$2\pi/\om_1$'' by ``$2\pi/\om_2$'', twice p. 396 replace ``$c\om_2+d\om_1$'' by ``$c\om_1+d\om_2$'', twice p. 396 and p. 398 replace $z/\om_1$ by $z/\om_2$, three times p. 396, six times p. 398, twice p. 399 and p. 412 replace an isolated ``$\om_1$'' by ``$\om_2$'', twice p. 398 and five times p. 399 (but {\it not\/} p. 415) replace an isolated ``$\om_2$'' by ``$\om_1$''. Although not mathematically necessary, it is then more aesthetic to replace everywhere ``$\Z+\Z\tau$'' by ``$\Z\tau+\Z$''. p. 392\quad line -16, instead of ``$n\ge2$'' read ``$n\le2$'' p. 395\quad line -1, add the following: ``{\bf Warning.} The condition $m\ge1$ in step 3 should in practice be implemented as $m>1-\eps$ for some small $\eps>0$ depending on the current accuracy. If this precaution is not taken the algorithm may loop indefinitely, and the cost is simply that the final $\tau$ may land very close to but not exactly in the standard fundamental domain, and this has absolutely no consequence for practical computations.'' p. 407\quad line 2 of step 3, instead of ``set $c\gets1$'' read ``set $c\gets\nu$'' p. 408\quad line 1 of step 9, instead of ``$a_4andp^3$'' read ``$a_4$ {\sans and} $p^3$'' p. 408\quad line 2 of step 9, instead of ``$a^6$'' read ``$a_6$'' p. 408\quad line 1 of step 11, instead of ``$X^2+a_3/p^2X+a_6/p^4$'' read ``$X^2+a_3/p^2X-a_6/p^4$'' p. 408\quad line -1, instead of ``$c\gets1$ $T\gets II^*$'' read ``$c\gets1$, $T\gets II^*$'' p. 416\quad line -4, instead of ``$f_1(\sqrt D)$'' read ``$f_1(\sqrt{D/4})$'' p. 417\quad line 4 of Exercise 1, instead of ``and $b_2\equiv0$,... respectively'' read ``and $b_2\equiv-c_6\pmod{12}$'' p. 425\quad line 3 of Section 8.4, instead of ``may be factor'' read ``may be a factor'' p. 432\quad line 8, instead of ``Proposition 8.5.3'' read ``Proposition 8.5.4'' p. 435\quad line -3, instead of ``corresponding to $\goth b$'' read ``corresponding to ${\goth b}^{-1}$'' p. 436\quad line 1, instead of ``$\delta(g_1,g)=$'' read ``$\delta(g_1,g^{-1})=$'' p. 440\quad line 19, instead of ``It is also however also'' read ``It is however also'' p. 440\quad line -10, instead of ``We must show how are we going'' read ``We must explain how we are going'' p. 452\quad line -6, instead of ``$\max(e,k+1))$'' read ``$\max(e,k+u))$ where $u$ is as in Lemma 9.1.10'' p. 452\quad line -5, instead of ``Proposition 9.1.8'' read ``Lemma 9.1.8'' p. 453\quad middle, after ``prime $r$ dividing $N$'' insert ``(by Lemma 9.1.10 and our choice of $\ell$)'' p. 454\quad line -16, instead of ``of order'' read ``of order dividing'' p. 462\quad line 3 of the proof of Lemma 9.1.24, instead of ``$j_3(\chi,\chi,\chi)=$'' read ``$j_3(\chi,\chi,\chi)^{\gamma}=$'' p. 474\quad step 4 of Algorithm 9.2.4, instead of ``$(x+3y)$'' read ``$(x+3y)/2$'' (twice) and instead of ``$(x-3y)$'' read ``$(x-3y)/2$'' (twice) p. 476\quad line 3 of Exercise 7. instead of ``$\chi(x)\neq1$'' read ``$\chi(x)\neq0\text{ and }1$'' p. 476\quad Exercise 7, add the following question. `` c) Show that if $\chi$ is a primitive character modulo $q$ which is not necessarily a prime, we still have $|\tau(\chi)|=\sqrt{q}$.'' p. 478\quad line 5, instead of ``$\eps=0$ or $1$'' read ``$\eps_k=0$ or $1$'' p. 480\quad line 2 of the second remark, instead of ``a follows'' read ``as follows'' p. 482\quad lines 4, 14, 16, 19, instead of ``$1/2a$'' read ``$1/(2a)$'' p. 487\quad middle, instead of ``$t=0\pmod N$'' read ``$t\equiv0\pmod N$'' p. 490\quad line -12, instead of ``we note than one can'' read ``we note that one can'' p. 490\quad line -1, instead of ``Pomerance ,'' read ``Pomerance,'' p. 494\quad line -4, instead of ``is $t$ is the'' read ``if $t$ is the'' p. 499\quad line 9, instead of ``${\Cal N}(a+b\theta)$'' read ``$\ln({\Cal N}(a+b\theta))$'' p. 500\quad line 19, instead of ``Let $V$ is the column'' read ``Let $V$ be the column'' p. 528\quad before [Lang1], add the following: ``One can find at the URL \centerline{\tt http://www-cs-faculty.stanford.edu/\~{}\hbox{}knuth/index.html} nearly 350 pages of corrections and additions to [Knu1], [Knu2] and [Knu3], absolutely necessary for those having the older editions of Knuth's books. This has been incorporated in a new 3 volume set which came out in 1996.'' p. 535\quad in [Len-Len2], instead of ``nmber field'' read ``number field'' p. 538\quad instead of ``[{\bf de Weg}] de Weger B.,'' read ``[{\bf deWeg}] B.~de Weger,'' } \end