This is TeX, Version 3.14159 (Web2C 7.3.1) (format=latex 2000.7.19) 15 APR 2002 11:51 **\nonstopmode\input main.tex (main.tex (/usr/share/texmf/tex/latex/base/report.cls Document Class: report 1999/09/10 v1.4a Standard LaTeX document class (/usr/share/texmf/tex/latex/base/size10.clo File: size10.clo 1999/09/10 v1.4a Standard LaTeX file (size option) ) \c@part=\count79 \c@chapter=\count80 \c@section=\count81 \c@subsection=\count82 \c@subsubsection=\count83 \c@paragraph=\count84 \c@subparagraph=\count85 \c@figure=\count86 \c@table=\count87 \abovecaptionskip=\skip41 \belowcaptionskip=\skip42 \bibindent=\dimen102 ) (svsing2e.sty LaTeX2e package "svsing2e" (Springer-Verlag Single-Authored). v. 1.3 released M ay 1995 \@crosshairrule=\dimen103 (/usr/share/texmf/tex/generic/misc/psfig.sty \@unused=\write3 \ps@stream=\read1 \p@intvaluex=\dimen104 \p@intvaluey=\dimen105 psfig/tex 1.10-dvips )) (/usr/share/texmf/tex/latex/amsfonts/amsfonts.sty Package: amsfonts 1997/09/17 v2.2e \@emptytoks=\toks14 \symAMSa=\mathgroup4 \symAMSb=\mathgroup5 LaTeX Font Info: Overwriting math alphabet `\mathfrak' in version `bold' (Font) U/euf/m/n --> U/euf/b/n on input line 133. ) (/usr/share/texmf/tex/latex/amsmath/amsmath.sty Package: amsmath 2000/01/15 v2.05 AMS math features \@mathmargin=\skip43 For additional information on amsmath, use the `?' option. (/usr/share/texmf/tex/latex/amsmath/amstext.sty Package: amstext 1999/11/15 v2.0 (/usr/share/texmf/tex/latex/amsmath/amsgen.sty File: amsgen.sty 1999/11/30 v2.0 \@emptytoks=\toks15 \ex@=\dimen106 )) (/usr/share/texmf/tex/latex/amsmath/amsbsy.sty Package: amsbsy 1999/11/29 v1.2d \pmbraise@=\dimen107 ) (/usr/share/texmf/tex/latex/amsmath/amsopn.sty Package: amsopn 1999/12/14 v2.01 operator names ) \inf@bad=\count88 LaTeX Info: Redefining \frac on input line 198. \uproot@=\count89 \leftroot@=\count90 LaTeX Info: Redefining \overline on input line 302. \classnum@=\count91 \DOTSCASE@=\count92 LaTeX Info: Redefining \ldots on input line 376. LaTeX Info: Redefining \dots on input line 379. LaTeX Info: Redefining \cdots on input line 464. \Mathstrutbox@=\box26 \strutbox@=\box27 \big@size=\dimen108 LaTeX Font Info: Redeclaring font encoding OML on input line 563. LaTeX Font Info: Redeclaring font encoding OMS on input line 564. \macc@skew=\dimen109 \c@MaxMatrixCols=\count93 \dotsspace@=\muskip10 \c@parentequation=\count94 \dspbrk@lvl=\count95 \tag@help=\toks16 \row@=\count96 \column@=\count97 \maxfields@=\count98 \andhelp@=\toks17 \eqnshift@=\dimen110 \alignsep@=\dimen111 \tagshift@=\dimen112 \tagwidth@=\dimen113 \totwidth@=\dimen114 \lineht@=\dimen115 \@envbody=\toks18 \multlinegap=\skip44 \multlinetaggap=\skip45 LaTeX Info: Redefining \[ on input line 2594. LaTeX Info: Redefining \] on input line 2595. ) (/usr/share/texmf/tex/latex/amsfonts/amssymb.sty Package: amssymb 1996/11/03 v2.2b ) (/usr/share/texmf/tex/latex/amscls/amsthm.sty Package: amsthm 2000/01/17 v2.03 \thm@style=\toks19 \thm@bodyfont=\toks20 \thm@headfont=\toks21 \thm@notefont=\toks22 \thm@headpunct=\toks23 \thm@preskip=\skip46 \thm@postskip=\skip47 \thm@headsep=\skip48 \dth@everypar=\toks24 ) (/usr/share/texmf/tex/latex/base/makeidx.sty Package: makeidx 1999/09/17 v1.0l Standard LaTeX package ) (/usr/share/texmf/tex/latex/graphics/graphicx.sty Package: graphicx 1999/02/16 v1.0f Enhanced LaTeX Graphics (DPC,SPQR) (/usr/share/texmf/tex/latex/graphics/keyval.sty Package: keyval 1999/03/16 v1.13 key=value parser (DPC) \KV@toks@=\toks25 ) (/usr/share/texmf/tex/latex/graphics/graphics.sty Package: graphics 1999/02/16 v1.0l Standard LaTeX Graphics (DPC,SPQR) (/usr/share/texmf/tex/latex/graphics/trig.sty Package: trig 1999/03/16 v1.09 sin cos tan (DPC) ) (/usr/share/texmf/tex/latex/config/graphics.cfg) Package graphics Info: Driver file: dvips.def on input line 80. (/usr/share/texmf/tex/latex/graphics/dvips.def File: dvips.def 1999/02/16 v3.0i Driver-dependant file (DPC,SPQR) )) \Gin@req@height=\dimen116 \Gin@req@width=\dimen117 ) (/usr/share/texmf/tex/generic/pstricks/pstricks.sty Package: pstricks 1997/03/25 package wrapper for PSTricks pstricks.tex (/usr/share/texmf/tex/generic/pstricks/pstricks.tex `PSTricks' v97 patch 10 <1999/03/24> (tvz) \pst@dima=\dimen118 \pst@dimb=\dimen119 \pst@dimc=\dimen120 \pst@dimd=\dimen121 \pst@dimg=\dimen122 \pst@dimh=\dimen123 \pst@hbox=\box28 \pst@boxg=\box29 \pst@cnta=\count99 \pst@cntb=\count100 \pst@cntc=\count101 \pst@cntd=\count102 \pst@cntg=\count103 \pst@cnth=\count104 \pst@toks=\toks26 (/usr/share/texmf/tex/generic/pstricks/pstricks.con) \psunit=\dimen124 \psxunit=\dimen125 \psyunit=\dimen126 \pslinewidth=\dimen127 \pst@customdefs=\toks27 \pslinearc=\dimen128 \everypsbox=\toks28 \psframesep=\dimen129 \pslabelsep=\dimen130 \theoverlaybox=\box30 )) \@indexfile=\write4 \openout4 = `main.idx'. Writing index file main.idx \@input{macros.aux} \openout2 = `macros.aux'. (macros.tex \c@theorem=\count105 ) (main.aux (chapters/preface.aux) (chapters/introduction.aux) (chapters/primes.aux) (chapters/crypto.aux) (chapters/reciprocity.aux LaTeX Warning: Label `thm:recip' multiply defined. ) (chapters/contfrac.aux LaTeX Warning: Label `prop' multiply defined. ) (chapters/quadform.aux) (chapters/ell.aux) (chapters/ellapp.aux) (chapters/bsd.aux) (chapters/pari.aux) (chapters/solutions.aux)) \openout1 = `main.aux'. LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 39. LaTeX Font Info: ... okay on input line 39. LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 39. LaTeX Font Info: ... okay on input line 39. LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 39. LaTeX Font Info: ... okay on input line 39. LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 39. LaTeX Font Info: ... okay on input line 39. LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 39. LaTeX Font Info: ... okay on input line 39. LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 39. LaTeX Font Info: ... okay on input line 39. LaTeX Font Info: Checking defaults for OT2/cmr/m/n on input line 39. LaTeX Font Info: Try loading font information for OT2+cmr on input line 39. (/usr/share/texmf/tex/latex/cyrillic/ot2cmr.fd File: ot2cmr.fd 1999/06/24 v3.2b Computer Modern Cyrillic font definitions ) LaTeX Font Info: ... okay on input line 39. LaTeX Font Info: Try loading font information for U+msa on input line 41. (/usr/share/texmf/tex/latex/amsfonts/umsa.fd File: umsa.fd 1995/01/05 v2.2e AMS font definitions ) LaTeX Font Info: Try loading font information for U+msb on input line 41. (/usr/share/texmf/tex/latex/amsfonts/umsb.fd File: umsb.fd 1995/01/05 v2.2e AMS font definitions ) [1 ] [2 ] (main.toc Underfull \vbox (badness 2142) has occurred while \output is active [] [3]) \tf@toc=\write5 \openout5 = `main.toc'. [1] \openout2 = `chapters/preface.aux'. (chapters/preface.tex [2 ]) Overfull \hbox (3.1662pt too wide) in paragraph at lines 13--45 \OT1/cmr/m/n/10 [Acknowledgments: A state-ment thank-ing those in-di-vid-u-als who have helped [] [3] \openout2 = `chapters/introduction.aux'. (chapters/introduction.tex [4 ] [5] [6] LaTeX Warning: Reference `' on page 7 undefined on input line 80. Overfull \hbox (1.63869pt too wide) in paragraph at lines 76--81 \OT1/cmr/m/it/10 Dyer Con-jec-ture \OT1/cmr/m/n/10 which gives a sim-ple con-je c-tural cri-te-rion to de-cide whether [] ) [7] \openout2 = `chapters/primes.aux'. (chapters/primes.tex [8 ] 1. Overfull \hbox (3.12543pt too wide) in paragraph at lines 12--16 \OT1/cmr/m/n/10 They are de-noted by $\U/msb/m/n/10 Z$ \OT1/cmr/m/n/10 be-cause the Ger-man word for the in-te-gers is ``\OT1/cmr/bx/n/10 Z\OT1/cmr/m/n/10 ahl en'' [] [9] [10] [11] LaTeX Font Info: Try loading font information for OMS+cmr on input line 196. (/usr/share/texmf/tex/latex/base/omscmr.fd File: omscmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions ) LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <10> not available (Font) Font shape `OMS/cmsy/m/n' tried instead on input line 196. [12] Overfull \hbox (16.00095pt too wide) in paragraph at lines 230--233 []\OT1/cmr/m/n/10 1881988129206079638386972394616504398071635633794173827007 [] Overfull \hbox (16.00095pt too wide) in paragraph at lines 230--233 \OT1/cmr/m/n/10 6335642298885971523466548531906060650474304531738801130339 [] Overfull \hbox (16.00095pt too wide) in paragraph at lines 230--233 \OT1/cmr/m/n/10 6716199692321205734031879550656996221305168759307650257059 [] [13] Underfull \hbox (badness 10000) in paragraph at lines 315--318 [] [14] [15] Overfull \hbox (1.62743pt too wide) in paragraph at lines 584--585 [][] [] [16] Overfull \hbox (48.74675pt too wide) in paragraph at lines 615--615 []\OT1/cmtt/m/n/10 ? for(n=1,10,print(n*1000,"\t",pi(n*1000),"\t",n*1000/(log(n *1000)-1)))[] [] Overfull \hbox (48.74675pt too wide) in paragraph at lines 626--626 []\OT1/cmtt/m/n/10 http://numbers.computation.free.fr/Constants/Primes/Pix/pixp roject.html[] [] [17] Overfull \hbox (32.99689pt too wide) in paragraph at lines 652--652 [] \OT1/cmtt/m/n/10 Li(10^22) = 201467286691248261498.1505... (usin g Maple)[] [] Overfull \hbox (22.11044pt too wide) detected at line 694 \U/msb/m/n/10 Z\OML/cmm/m/it/10 =\OT1/cmr/m/n/10 3\U/msb/m/n/10 Z \OT1/cmr/m/n/ 10 = \OMS/cmsy/m/n/10 ff[] \OML/cmm/m/it/10 ; \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/ 10 3\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 3\OM L/cmm/m/it/10 ; []\OMS/cmsy/m/n/10 g\OML/cmm/m/it/10 ; \OMS/cmsy/m/n/10 f[] \OM L/cmm/m/it/10 ; \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 2\OML/cmm/m/it/10 ; \OT1/cm r/m/n/10 1\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 4\OML/cmm/m/it/10 ; []\OMS/cmsy/m/ n/10 g\OML/cmm/m/it/10 ; \OMS/cmsy/m/n/10 f[] \OML/cmm/m/it/10 ; \OMS/cmsy/m/n/ 10 ^^@\OT1/cmr/m/n/10 1\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 2\OML/cmm/m/it/10 ; \ OT1/cmr/m/n/10 5\OML/cmm/m/it/10 ; []\OMS/cmsy/m/n/10 gg \OT1/cmr/m/n/10 = \OMS /cmsy/m/n/10 f\OT1/cmr/m/n/10 [0]\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 [1]\OML/cmm /m/it/10 ; \OT1/cmr/m/n/10 [2]\OMS/cmsy/m/n/10 g [] [18] Overfull \hbox (2.84154pt too wide) in paragraph at lines 753--757 \OT1/cmr/bx/n/10 Definition 1.24 (Com-plete Set of Residues). \OT1/cmr/m/n/10 A \OT1/cmr/m/it/10 com-plete set of residues [] [19] Underfull \hbox (badness 10000) in paragraph at lines 810--811 [] [20] [21] [22] [23] [24] Overfull \hbox (6.40207pt too wide) in paragraph at lines 1111--1111 [] [] [25] [26] Overfull \hbox (6.74712pt too wide) in paragraph at lines 1241--1241 []\OT1/cmtt/m/n/10 bezout(x,y): gives a 3-dimensional row vector [u,v,d] such t hat[] [] [27] [28] [29] Overfull \hbox (43.4968pt too wide) in paragraph at lines 1393--1393 []\OT1/cmtt/m/n/10 ? x = 094860934869840698340958093485903450983409580934850983 4905809345[] [] Overfull \hbox (38.24684pt too wide) in paragraph at lines 1393--1393 []\OT1/cmtt/m/n/10 %36 = 948609348698406983409580934859034509834095809348509834 905809345[] [] Overfull \hbox (38.24684pt too wide) in paragraph at lines 1393--1393 []\OT1/cmtt/m/n/10 %37 = 948609348698406983409580934859034509834095809348509834 905809399[] [] Overfull \hbox (25.91689pt too wide) in paragraph at lines 1423--1425 []\OT1/cmr/m/n/10 What was the most re-cent prime year? I.e., which of $[] \OML /cmm/m/it/10 ; \OT1/cmr/m/n/10 2002\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 2001\OML/ cmm/m/it/10 ; \OT1/cmr/m/n/10 2000\OML/cmm/m/it/10 ; []$ [] [30]) [31] \openout2 = `chapters/crypto.aux'. (chapters/crypto.tex [32 ] 2. File: graphics/nikita.eps Graphic file (type eps) [33] Overfull \hbox (10.60898pt too wide) in paragraph at lines 40--44 []\OT1/cmr/m/n/10 Meanwhile, hack-ers in The Col-lec-tive see both $\OML/cmm/m/ it/10 g[]\OT1/cmr/m/n/10 ([]\OML/cmm/m/it/10 p\OT1/cmr/m/n/10 )$ and $\OML/cmm/ m/it/10 g[]\OT1/cmr/m/n/10 ([]\OML/cmm/m/it/10 p\OT1/cmr/m/n/10 )$, [] Overfull \hbox (1.49716pt too wide) in paragraph at lines 61--61 [] \OT1/cmtt/m/n/10 IEEE Trans. Information Theory IT-22 (1976), no. 6, 644--65 4.[] [] [34] File: graphics/diffie.eps Graphic file (type eps) File: graphics/hellman.eps Graphic file (type eps) [35] Overfull \hbox (64.49661pt too wide) in paragraph at lines 168--168 []\OT1/cmtt/m/n/10 ? dislog(x,g, s) = s=g; for(n=1,znorder(g),if(x==s, return(n ), s=s*g)); 0;[] [] [36] Overfull \hbox (80.24648pt too wide) in paragraph at lines 197--197 []\OT1/cmtt/m/n/10 ? znlog(a,g) \\ builtin super-optimized version takes about 1/2 second[] [] Overfull \hbox (22.49698pt too wide) in paragraph at lines 229--229 []\OT1/cmtt/m/n/10 We are pleased to announce a new record for the discrete log arithm[] [] Overfull \hbox (22.49698pt too wide) in paragraph at lines 229--229 []\OT1/cmtt/m/n/10 quadri-processors Digital Alpha Server 8400 computer. The ap proach[] [] Overfull \hbox (32.99689pt too wide) in paragraph at lines 229--229 []\OT1/cmtt/m/n/10 that we followed is a careful implementation of the general Function[] [] Overfull \hbox (32.99689pt too wide) in paragraph at lines 229--229 []\OT1/cmtt/m/n/10 Field Sieve as described from a theoretical point of view by Adleman[] [] Overfull \hbox (27.74693pt too wide) in paragraph at lines 229--229 []\OT1/cmtt/m/n/10 As far as we know, the largest such computation previously d one was[] [] Overfull \hbox (38.24684pt too wide) in paragraph at lines 229--229 []\OT1/cmtt/m/n/10 performed in GF(2^401) [GoMc92] using an algorithm due to Co ppersmith[] [] Overfull \hbox (22.49698pt too wide) in paragraph at lines 229--229 []\OT1/cmtt/m/n/10 logarithms in GF(2^521) on a 525 MHz quadri-processor alpha server[] [] Overfull \hbox (32.99689pt too wide) in paragraph at lines 229--229 []\OT1/cmtt/m/n/10 8400 computer is approximatively 12 hours for each, once the sieving[] [] Overfull \hbox (22.49698pt too wide) in paragraph at lines 229--229 []\OT1/cmtt/m/n/10 step (21 days) and the linear algebra step (10 days) is perf ormed.[] [] Overfull \hbox (64.49661pt too wide) in paragraph at lines 229--229 []\OT1/cmtt/m/n/10 Antoine JOUX (DCSSI, Issy les Moulineaux, France, Antoine .Joux@ens.fr),[] [] [37] Overfull \hbox (22.49698pt too wide) in paragraph at lines 261--261 []\OT1/cmtt/m/n/10 ? nextgoodprime(p) = while(!isprime((p-1)\2), p=nextprime(p+ 1)); p[] [] Overfull \hbox (48.74675pt too wide) in paragraph at lines 261--261 []\OT1/cmtt/m/n/10 %26 = Mod(17037287637415625385373411504, 9345098309485093845 0983409611)[] [] Overfull \hbox (43.4968pt too wide) in paragraph at lines 261--261 []\OT1/cmtt/m/n/10 %27 = Mod(2201425894324369970772940547, 93450983094850938450 983409611)[] [] Overfull \hbox (48.74675pt too wide) in paragraph at lines 261--261 []\OT1/cmtt/m/n/10 %28 = Mod(25591938014843312529239952955, 9345098309485093845 0983409611)[] [] Overfull \hbox (48.74675pt too wide) in paragraph at lines 261--261 []\OT1/cmtt/m/n/10 %29 = Mod(25591938014843312529239952955, 9345098309485093845 0983409611)[] [] [38] Overfull \hbox (0.58618pt too wide) in paragraph at lines 330--332 \OT1/cmr/m/n/10 Encode your mes-sage as a se-quence of num-bers mod-ulo $\OML/c mm/m/it/10 n$ \OT1/cmr/m/n/10 (see Sec-tion 2.2.2[]): [] [39] Overfull \hbox (20.79228pt too wide) detected at line 373 [] \OMS/cmsy/m/n/10 $ \OT1/cmr/m/n/10 8 + 27 \OMS/cmsy/m/n/10 ^^A \OT1/cmr/m/ n/10 1 + 27[] \OMS/cmsy/m/n/10 ^^A \OT1/cmr/m/n/10 18 + 27[] \OMS/cmsy/m/n/10 ^ ^A \OT1/cmr/m/n/10 22 + 27[] \OMS/cmsy/m/n/10 ^^A \OT1/cmr/m/n/10 1 + 27[] \OMS /cmsy/m/n/10 ^^A \OT1/cmr/m/n/10 18 + 27[] \OMS/cmsy/m/n/10 ^^A \OT1/cmr/m/n/10 4 = 1808939906 [] Overfull \hbox (49.66197pt too wide) detected at line 399 \OML/cmm/m/it/10 '\OT1/cmr/m/n/10 (\OML/cmm/m/it/10 n\OT1/cmr/m/n/10 ) = \OML/c mm/m/it/10 '\OT1/cmr/m/n/10 (\OML/cmm/m/it/10 p \OMS/cmsy/m/n/10 ^^A \OML/cmm/m /it/10 q\OT1/cmr/m/n/10 ) = \OML/cmm/m/it/10 '\OT1/cmr/m/n/10 (\OML/cmm/m/it/10 p\OT1/cmr/m/n/10 ) \OMS/cmsy/m/n/10 ^^A \OML/cmm/m/it/10 '\OT1/cmr/m/n/10 (\OM L/cmm/m/it/10 q\OT1/cmr/m/n/10 ) = (\OML/cmm/m/it/10 p \OMS/cmsy/m/n/10 ^^@ \OT 1/cmr/m/n/10 1)(\OML/cmm/m/it/10 q \OMS/cmsy/m/n/10 ^^@ \OT1/cmr/m/n/10 1) = \O ML/cmm/m/it/10 pq \OMS/cmsy/m/n/10 ^^@ \OML/cmm/m/it/10 p \OMS/cmsy/m/n/10 ^^@ \OML/cmm/m/it/10 q \OT1/cmr/m/n/10 + 1 = 323 \OMS/cmsy/m/n/10 ^^@ \OT1/cmr/m/n/ 10 17 \OMS/cmsy/m/n/10 ^^@ \OT1/cmr/m/n/10 19 + 1 = 288\OML/cmm/m/it/10 : [] [40] [41] Overfull \hbox (27.74693pt too wide) in paragraph at lines 499--499 []\OT1/cmtt/m/n/10 {alphabet=[" ","A","B","C","D","E","F","G","H","I","J","K"," L","M",[] [] Overfull \hbox (11.99707pt too wide) in paragraph at lines 499--499 [] \OT1/cmtt/m/n/10 "N","O","P","Q","R","S","T","U","V","W","X","Y"," Z"];[] [] Overfull \hbox (17.24702pt too wide) in paragraph at lines 499--499 [] \OT1/cmtt/m/n/10 for(i=1,length(w), n = n + 27^(i-1)*letter_to_number(w[ i]));[] [] Overfull \hbox (27.74693pt too wide) in paragraph at lines 499--499 []\OT1/cmtt/m/n/10 encrypt(message, n, e) = lift(Mod(message_to_number(message) ,n)^e);[] [] Overfull \hbox (22.49698pt too wide) in paragraph at lines 499--499 []\OT1/cmtt/m/n/10 decrypt(secret, n, d) = number_to_message(lift(Mod(secret,n )^d));[] [] Underfull \vbox (badness 3690) has occurred while \output is active [] [42] [43] Underfull \hbox (badness 10000) in paragraph at lines 575--576 [] [44] Overfull \hbox (43.4968pt too wide) in paragraph at lines 698--698 []\OT1/cmtt/m/n/10 %22 = 611165840845056469708563420184597685050990858094998688 9525704...[] [] Overfull \hbox (6.74712pt too wide) in paragraph at lines 698--698 []\OT1/cmtt/m/n/10 ? \p150 \\ set precision of floating-point computatio ns.[] [] Overfull \hbox (11.99707pt too wide) in paragraph at lines 698--698 [] \OT1/cmtt/m/n/10 realprecision = 154 significant digits (150 digits displa yed)[] [] Overfull \hbox (27.74693pt too wide) in paragraph at lines 698--698 []\OT1/cmtt/m/n/10 %30 = 48.000000000000000000000000000000000000000000000000000 000....[] [] [45] Overfull \hbox (32.99689pt too wide) in paragraph at lines 784--784 []\OT1/cmtt/m/n/10 ? \r rsa \\ load the file rsa.gp, available at Lecture 9 w eb page.[] [] Overfull \hbox (11.99707pt too wide) in paragraph at lines 784--784 []\OT1/cmtt/m/n/10 ? for(a=2,20, if(Mod(a,n)^m!=1,print(a))) \\ prints nothin g...[] [] [46] Overfull \hbox (43.4968pt too wide) in paragraph at lines 790--790 [] \OT1/cmtt/m/n/10 http://www.rsasecurity.com/rsalabs/challenges/factoring/nu mbers.html[] [] Overfull \hbox (53.9967pt too wide) in paragraph at lines 800--800 []\OT1/cmtt/m/n/10 188198812920607963838697239461650439807163563379417382700763 356422988859[] [] Overfull \hbox (53.9967pt too wide) in paragraph at lines 800--800 []\OT1/cmtt/m/n/10 715234665485319060606504743045317388011303396716199692321205 734031879550[] [] LaTeX Warning: Reference `' on page 47 undefined on input line 811. [47] [48]) [49] \openout2 = `chapters/reciprocity.aux'. (chapters/reciprocity.tex [50 ] 3. [51] [52] [53] [54] Overfull \hbox (6.84212pt too wide) in paragraph at lines 300--302 \OT1/cmr/bx/n/10 Corollary 3.12. \OT1/cmr/m/it/10 If $\OML/cmm/m/it/10 x[] \OMS /cmsy/m/n/10 ^^Q \OML/cmm/m/it/10 a\OT1/cmr/m/n/10 ([]\OML/cmm/m/it/10 p\OT1/cm r/m/n/10 )$ \OT1/cmr/m/it/10 has no so-lu-tions if and only if $\OML/cmm/m/it/1 0 a[] \OMS/cmsy/m/n/10 ^^Q [] Overfull \hbox (16.97096pt too wide) detected at line 317 \OT1/cmr/m/n/10 1[] = 1\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 2[] = 4\OML/cmm/m/it /10 ; \OT1/cmr/m/n/10 3[] = 9\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 4[] = 5\OML/c mm/m/it/10 ; \OT1/cmr/m/n/10 5[] = 3\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 6[] = 3\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 7[] = 5\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 8[] = 9\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 9[] = 4\OML/cmm/m/it/10 ; \OT1/cmr /m/n/10 10[] = 1\OML/cmm/m/it/10 : [] Overfull \hbox (55.85997pt too wide) detected at line 323 \OT1/cmr/m/n/10 1[] = 1\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 2[] = \OMS/cmsy/m/n/ 10 ^^@\OT1/cmr/m/n/10 1\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 3[] = 1\OML/cmm/m/it /10 ; \OT1/cmr/m/n/10 4[] = 1\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 5[] = 1\OML/c mm/m/it/10 ; \OT1/cmr/m/n/10 6[] = \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 1\OML/c mm/m/it/10 ; \OT1/cmr/m/n/10 7[] = \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 1\OML/c mm/m/it/10 ; \OT1/cmr/m/n/10 8[] = \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 1\OML/c mm/m/it/10 ; \OT1/cmr/m/n/10 9[] = 1\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 10[] = \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 1\OML/cmm/m/it/10 : [] Overfull \hbox (8.46613pt too wide) in paragraph at lines 331--335 \OT1/cmr/m/it/10 Example \OT1/cmr/m/n/10 3.14\OT1/cmr/m/it/10 . \OT1/cmr/m/n/10 De-ter-mine whether or not $3$ is a square mod-ulo $\OML/cmm/m/it/10 p \OT1/cm r/m/n/10 = 726377359$. [] Overfull \hbox (17.24702pt too wide) in paragraph at lines 338--338 []\OT1/cmtt/m/n/10 %5 = Mod(726377358, 726377359) \\ class of -1 modulo 72637 7359.[] [] [55] [56] [57] Overfull \hbox (8.35721pt too wide) detected at line 493 \OT1/cmr/m/n/10 (1\OML/cmm/m/it/10 a\OT1/cmr/m/n/10 ) \OMS/cmsy/m/n/10 ^^A \OT1 /cmr/m/n/10 (2\OML/cmm/m/it/10 a\OT1/cmr/m/n/10 ) \OMS/cmsy/m/n/10 ^^A \OT1/cmr /m/n/10 (3\OML/cmm/m/it/10 a\OT1/cmr/m/n/10 ) \OMS/cmsy/m/n/10 ^^A [] ^^A [] ^^ Q \OT1/cmr/m/n/10 (\OML/cmm/m/it/10 "[] \OMS/cmsy/m/n/10 ^^A \OT1/cmr/m/n/10 1) \OMS/cmsy/m/n/10 ^^A \OT1/cmr/m/n/10 (\OML/cmm/m/it/10 "[] \OMS/cmsy/m/n/10 ^^ A \OT1/cmr/m/n/10 2) [] [] ([]\OML/cmm/m/it/10 p\OT1/cmr/m/n/10 )\OML/cmm/m/it/ 10 ; [] [58] Overfull \hbox (44.77765pt too wide) detected at line 622 \OML/cmm/m/it/10 K \OT1/cmr/m/n/10 = [] \OML/cmm/m/it/10 : [] [59] [60] [61]) [62] \openout2 = `chapters/contfrac.aux'. (chapters/contfrac.tex 4. [63 ] Overfull \hbox (22.244pt too wide) in paragraph at lines 70--70 [] [] Overfull \hbox (0.72789pt too wide) in paragraph at lines 73--76 \OT1/cmr/m/it/10 Exercise \OT1/cmr/m/n/10 4.3\OT1/cmr/m/it/10 . \OT1/cmr/m/n/10 Com-pute $\OML/cmm/m/it/10 p[]$ \OT1/cmr/m/n/10 and $\OML/cmm/m/it/10 q[]$ \OT 1/cmr/m/n/10 for the con-tin-ued frac-tions $[\OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/ 10 3\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1\OM L/cmm/m/it/10 ; \OT1/cmr/m/n/10 1\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1\OML/cmm/m /it/10 ; \OT1/cmr/m/n/10 3]$ [] [64] [65] [66] [67] Overfull \hbox (31.9004pt too wide) detected at line 259 \OML/cmm/m/it/10 x \OT1/cmr/m/n/10 = [\OML/cmm/m/it/10 a[]; a[]; [] ; a[]; []\O T1/cmr/m/n/10 ] = [\OML/cmm/m/it/10 a[]; a[]; [] ; a[]; a[] \OT1/cmr/m/n/10 + \ OML/cmm/m/it/10 t[]\OT1/cmr/m/n/10 ] = [\OML/cmm/m/it/10 a[]; a[]; [] ; a[]; a[ ]; []\OT1/cmr/m/n/10 ]\OML/cmm/m/it/10 : [] [68] Overfull \hbox (1.49716pt too wide) in paragraph at lines 316--316 [] \OT1/cmtt/m/n/10 pp=1; qq=0; p=v[1]; q=1; \\ pp is p_{n-1} and p is p_ n.[] [] [69] Overfull \hbox (38.24684pt too wide) in paragraph at lines 376--376 []\OT1/cmtt/m/n/10 %38 = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2 , 2, ...][] [] Overfull \hbox (22.49698pt too wide) in paragraph at lines 376--376 []\OT1/cmtt/m/n/10 %39 = [3, 22/7, 333/106, 355/113, 103993/33102, 104348/33215 , ...][] [] Overfull \hbox (59.24666pt too wide) in paragraph at lines 376--376 []\OT1/cmtt/m/n/10 ? [c[1]*1.0, c[3]*1.0, c[5]*1.0, c[7]*1.0] \\ odd ones conv erge up to pi[] [] Overfull \hbox (64.49661pt too wide) in paragraph at lines 376--376 []\OT1/cmtt/m/n/10 ? [c[2]*1.0,c[4]*1.0,c[6]*1.0,c[8]*1.0] \\ even ones swo op down on pi.[] [] [70] Overfull \hbox (1.17673pt too wide) in paragraph at lines 423--426 \OT1/cmr/bx/n/10 Proposition 4.16. \OT1/cmr/m/it/10 If $\OML/cmm/m/it/10 x$ \OT 1/cmr/m/it/10 is a ra-tio-nal num-ber then the se-quence $\OML/cmm/m/it/10 a[]; a[]; a[]; []$ [] [71] [72] Overfull \hbox (4.53398pt too wide) in paragraph at lines 514--521 \OT1/cmr/m/n/10 can be ex-pressed as a poly-no-mial in $\OML/cmm/m/it/10 ^^K$ \ OT1/cmr/m/n/10 with ra-tio-nal co-ef-fi-cients, so $[\OML/cmm/m/it/10 a[]; a[]; []\OT1/cmr/m/n/10 ]$ [] [73] Overfull \hbox (32.99689pt too wide) in paragraph at lines 614--614 []\OT1/cmtt/m/n/10 %5 = [1, 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, 1, 10, 2, 1, 4, 1 2, 2, 3,[] [] Overfull \hbox (32.99689pt too wide) in paragraph at lines 614--614 [] \OT1/cmtt/m/n/10 2, 1, 3, 4, 1, 1, 2, 14, 3, 12, 1, 15, 3, 1, 4, 534, 1, 1, 5, 1, 1,[] [] Overfull \hbox (43.4968pt too wide) in paragraph at lines 614--614 [] \OT1/cmtt/m/n/10 121, 1, 2, 2, 4, 10, 3, 2, 2, 41, 1, 1, 1, 3, 7, 2, 2, 9, 4 , 1, 3, 7,[] [] Overfull \hbox (38.24684pt too wide) in paragraph at lines 614--614 [] \OT1/cmtt/m/n/10 6, 1, 1, 2, 2, 9, 3, 1, 1, 69, 4, 4, 5, 12, 1, 1, 5, 15, 1, 4, 1, 1,[] [] [74] Overfull \hbox (3.08392pt too wide) in paragraph at lines 638--641 \OT1/cmr/m/n/10 sim-ple con-tin-ued frac-tion has un-bounded par-tial quo-tient s? Does [] [75] Overfull \hbox (64.49661pt too wide) in paragraph at lines 710--710 []\OT1/cmtt/m/n/10 %16 = [2, 2, 7, 2, 1, 5, 1, 1, 1, 1, 1, 1, 328210621945, 2, 1, 1, 1, 1, 7][] [] Overfull \hbox (69.74657pt too wide) in paragraph at lines 710--710 []\OT1/cmtt/m/n/10 %18 = [2, 2, 7, 2, 1, 5, 1, 1, 1, 1, 1, 1, 18850095183555629 36415046, 1, 4][] [] Overfull \hbox (69.74657pt too wide) in paragraph at lines 710--710 []\OT1/cmtt/m/n/10 ? x*1.0 \\ notice that no repeat is immediately evident in the digits of x[] [] Overfull \hbox (90.74638pt too wide) in paragraph at lines 710--710 []\OT1/cmtt/m/n/10 %19 = 2.4681570054587990642058747075643358461138549519105796 72472056147647517..[] [] Overfull \hbox (6.74712pt too wide) in paragraph at lines 710--710 []\OT1/cmtt/m/n/10 ? \\ in fact, the length of the period of the decimal expans ion[] [] [76] Overfull \hbox (0.14488pt too wide) in paragraph at lines 776--778 \OT1/cmr/bx/n/10 Proposition 4.24. \OT1/cmr/m/it/10 The units of $\U/msb/m/n/10 Z\OT1/cmr/m/n/10 [[]]$ \OT1/cmr/m/it/10 are ex-actly the el-e-ments of norm $\ OMS/cmsy/m/n/10 ^^F\OT1/cmr/m/n/10 1$ [] [77] [78] [79] Overfull \hbox (21.42859pt too wide) in paragraph at lines 950--952 []\OT1/cmr/m/n/10 If $\OML/cmm/m/it/10 c[] \OT1/cmr/m/n/10 = \OML/cmm/m/it/10 p []=q[]$ \OT1/cmr/m/n/10 is the $\OML/cmm/m/it/10 n$\OT1/cmr/m/n/10 th con-ver-g ent of the con-tin-ued frac-tion $[\OML/cmm/m/it/10 a[]; a[]; [] ; a[]\OT1/cmr/ m/n/10 ]$ [] [80] [81]) [82] \openout2 = `chapters/quadform.aux'. (chapters/quadform.tex 5. Underfull \hbox (badness 10000) in paragraph at lines 27--28 [] [83 ] [84] [85] [86] [87] Overfull \hbox (20.56493pt too wide) detected at line 303 \OML/cmm/m/it/10 f\OMS/cmsy/m/n/10 j[] \OT1/cmr/m/n/10 = 458(4\OML/cmm/m/it/10 x \OMS/cmsy/m/n/10 ^^@ \OT1/cmr/m/n/10 3\OML/cmm/m/it/10 y\OT1/cmr/m/n/10 )[] + 214(4\OML/cmm/m/it/10 x \OMS/cmsy/m/n/10 ^^@ \OT1/cmr/m/n/10 3\OML/cmm/m/it/10 y\OT1/cmr/m/n/10 )(\OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 17\OML/cmm/m/it/10 x \O T1/cmr/m/n/10 + 13\OML/cmm/m/it/10 y\OT1/cmr/m/n/10 ) + 25(\OMS/cmsy/m/n/10 ^^@ \OT1/cmr/m/n/10 17\OML/cmm/m/it/10 x \OT1/cmr/m/n/10 + 13\OML/cmm/m/it/10 y\OT1 /cmr/m/n/10 )[] = [] = \OML/cmm/m/it/10 x[] \OT1/cmr/m/n/10 + \OML/cmm/m/it/10 y[]\OT1/cmr/m/n/10 !! [] [88] [89] Underfull \vbox (badness 5036) has occurred while \output is active [] [90] LaTeX Font Info: Try loading font information for U+euf on input line 489. (/usr/share/texmf/tex/latex/amsfonts/ueuf.fd File: ueuf.fd 1995/01/05 v2.2e AMS font definitions ) [91] [92] Overfull \hbox (27.74693pt too wide) in paragraph at lines 661--661 []\OT1/cmtt/m/n/10 \\ and a matrix that transforms the input form to the reduce d form.[] [] Overfull \hbox (53.9967pt too wide) in paragraph at lines 661--661 [] \OT1/cmtt/m/n/10 if(D>=0 || a<0, error("reduce: (a,b,c) must be positive d efinite."));[] [] Overfull \hbox (17.24702pt too wide) in paragraph at lines 661--661 [] \OT1/cmtt/m/n/10 print([a,b,c], " \t(1)"), \\ backslash t means `` tab''[] [] [93] [94] Overfull \hbox (9.62663pt too wide) in paragraph at lines 730--732 \OT1/cmr/bx/n/10 Definition 5.20. \OT1/cmr/m/n/10 A bi-nary quadratic form $(\O ML/cmm/m/it/10 a; b; c\OT1/cmr/m/n/10 )$ is \OT1/cmr/m/it/10 prim-i-tive \OT1/c mr/m/n/10 if $[](\OML/cmm/m/it/10 a; b; c\OT1/cmr/m/n/10 ) = [] Underfull \vbox (badness 10000) has occurred while \output is active [] [95] Overfull \vbox (205.0pt too high) has occurred while \output is active [] [96] Overfull \hbox (53.9967pt too wide) in paragraph at lines 1026--1026 [] \OT1/cmtt/m/n/10 if(D>=0 || a<0, error("reduce: (a,b,c) must be positive d efinite."));[] [] Overfull \hbox (27.74693pt too wide) in paragraph at lines 1026--1026 [] \OT1/cmtt/m/n/10 if (D > 0 || D%4 == 2 || D%4==3, error("Invalid discrimin ant"));[] [] Underfull \vbox (badness 3690) has occurred while \output is active [] [97] Overfull \hbox (27.74693pt too wide) in paragraph at lines 1026--1026 [] \OT1/cmtt/m/n/10 return(eval(forms)); \\ eval gets rid of the annoying quotes.[] [] Overfull \hbox (38.24684pt too wide) in paragraph at lines 1071--1071 []\OT1/cmtt/m/n/10 %23 = [[1, 1, 105], [3, -1, 35], [3, 1, 35], [5, -1, 21], [5 , 1, 21],[] [] [98] Overfull \hbox (6.75522pt too wide) in paragraph at lines 1074--1076 \OT1/cmr/bx/n/10 Theorem 5.22 (Heeg-ner, Stark-Baker, Gold-feld-Gross-Zagier). \OT1/cmr/m/it/10 Sup- [] LaTeX Font Info: Font shape `OMS/cmr/m/it' in size <10> not available (Font) Font shape `OMS/cmsy/m/n' tried instead on input line 1077. Overfull \hbox (15.77776pt too wide) in paragraph at lines 1080--1082 []$\OML/cmm/m/it/10 h[] \OT1/cmr/m/n/10 = 3$ \OT1/cmr/m/it/10 only for $\OML/cm m/m/it/10 D \OT1/cmr/m/n/10 = \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 23\OML/cmm/m/ it/10 ; \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 31\OML/cmm/m/it/10 ; \OMS/cmsy/m/n/ 10 ^^@\OT1/cmr/m/n/10 59\OML/cmm/m/it/10 ; \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 83\OML/cmm/m/it/10 ; \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 107\OML/cmm/m/it/10 ; \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 139\OML/cmm/m/it/10 ; \OMS/cmsy/m/n/10 ^^@\ OT1/cmr/m/n/10 211\OML/cmm/m/it/10 ; \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 283\OM L/cmm/m/it/10 ; \OMS/cmsy/m/n/10 ^^@\OT1/cmr/m/n/10 307\OML/cmm/m/it/10 ;$ [] Overfull \hbox (0.8307pt too wide) in paragraph at lines 1104--1108 \OT1/cmr/bx/n/10 Definition 5.23. \OT1/cmr/m/n/10 Let $\OML/cmm/m/it/10 f[] \OT 1/cmr/m/n/10 = (\OML/cmm/m/it/10 a[]; b[]; c[]\OT1/cmr/m/n/10 )$ and $\OML/cmm/ m/it/10 f[] \OT1/cmr/m/n/10 = (\OML/cmm/m/it/10 a[]; b[]; c[]\OT1/cmr/m/n/10 )$ be two quadratic [] Overfull \hbox (25.63708pt too wide) in paragraph at lines 1110--1115 \OT1/cmr/m/n/10 (obtained by two ap-pli-ca-tions of Eu-clid's al-go-rithm), and let $\OML/cmm/m/it/10 d[] \OT1/cmr/m/n/10 = [](\OML/cmm/m/it/10 d; c[]; c[]; n \OT1/cmr/m/n/10 )$. [] [99] Overfull \hbox (74.99652pt too wide) in paragraph at lines 1148--1148 [] \OT1/cmtt/m/n/10 if(b2^2 - 4*a2*c2 != D, error("Forms must have the same d iscriminant."));[] [] [100]) [101] \openout2 = `chapters/ell.aux'. (chapters/ell.tex [102 ] 6. [103] [104] [105] Overfull \hbox (27.74693pt too wide) in paragraph at lines 213--213 []\OT1/cmtt/m/n/10 K := FieldOfFractions(PolynomialRing(Rationals (),5));[] [] Overfull \hbox (90.74638pt too wide) in paragraph at lines 213--213 []\OT1/cmtt/m/n/10 I := ideal;[] [] [106] Overfull \hbox (64.49661pt too wide) in paragraph at lines 213--213 []\OT1/cmtt/m/n/10 E := EllipticCurve([L| a,b]); // The elliptic curve y^2 = x^3 + a*x + b.[] [] Underfull \vbox (badness 10000) has occurred while \output is active [] [107] Underfull \vbox (badness 10000) has occurred while \output is active [] [108] [109] Overfull \hbox (27.74693pt too wide) in paragraph at lines 1213--1213 []\OT1/cmtt/m/n/10 K := FieldOfFractions(PolynomialRing(Rationals (),5));[] [] Overfull \hbox (1.49716pt too wide) in paragraph at lines 1213--1213 []\OT1/cmtt/m/n/10 // Let P0, P1, and P2 be three distinct "generic" points on E.[] [] Overfull \hbox (17.24702pt too wide) in paragraph at lines 1213--1213 []\OT1/cmtt/m/n/10 // The algebraic formulas for the group law are built into M AGMA.[] [] [110] Overfull \hbox (53.9967pt too wide) in paragraph at lines 1225--1225 []\OT1/cmtt/m/n/10 ? for(x=0,4, for(y=0,4, if((y^2-(x^3+3*x+3))%5==0, print1([x ,y]," "))))[] [] Overfull \hbox (48.74675pt too wide) in paragraph at lines 1243--1243 []\OT1/cmtt/m/n/10 ? ?ellpow \\ type ?5 for a complete list of elliptic-curv e functions[] [] Overfull \hbox (11.99707pt too wide) in paragraph at lines 1243--1243 []\OT1/cmtt/m/n/10 ellpow(e,x,n): n times the point x on elliptic curve e (n in Z).[] [] [111] [112] Overfull \hbox (5.65184pt too wide) in paragraph at lines 1366--1380 [] [] [113] Overfull \hbox (63.91136pt too wide) detected at line 1405 \OML/cmm/m/it/5 y[] \OT1/cmr/m/n/5 + \OML/cmm/m/it/5 xy \OT1/cmr/m/n/5 + \OML/c mm/m/it/5 y \OT1/cmr/m/n/5 = \OML/cmm/m/it/5 x[] \OMS/cmsy/m/n/5 ^^@ \OT1/cmr/m /n/5 120039822036992245303534619191166796374\OML/cmm/m/it/5 x \OT1/cmr/m/n/5 + 504224992484910670010801799168082726759443756222911415116 [] Overfull \hbox (103.1441pt too wide) in paragraph at lines 1434--1434 [] [] Overfull \hbox (59.24666pt too wide) in paragraph at lines 1441--1441 [] \OT1/cmtt/m/n/10 http://listserv.nodak.edu/scripts/wa.exe?A2=ind0005&L=nm brthry&P=R182[] [] [114] Overfull \hbox (51.99828pt too wide) in paragraph at lines 1473--1478 \OT1/cmr/m/n/10 Robin Hood lives) has a web page, \OT1/cmtt/m/n/10 http://www.t om.womack.net/maths/torsion.htm\OT1/cmr/m/n/10 , [] [115] Overfull \hbox (74.99652pt too wide) in paragraph at lines 1515--1515 []\OT1/cmtt/m/n/10 elltors(e,{flag=0}): torsion subgroup of elliptic curve e: o rder, structure,[] [] Overfull \hbox (74.99652pt too wide) in paragraph at lines 1515--1515 []\OT1/cmtt/m/n/10 generators. If flag = 0, use Doud's algorithm; if flag = 1, use Lutz-Nagell.[] [] [116] [117] [118]) [119] \openout2 = `chapters/ellapp.aux'. (chapters/ellapp.tex [120 ] 7. File: graphics/wma.eps Graphic file (type eps) Underfull \vbox (badness 10000) has occurred while \output is active [] [121] File: graphics/notes.eps Graphic file (type eps) Overfull \hbox (0.33392pt too wide) in paragraph at lines 52--58 \OT1/cmr/m/n/10 when they aren't out thwart-ing ter-ror-ists. When Nikita in-st alled Mi-crosoft's [] File: graphics/juno.eps Graphic file (type eps) [122] [123] Overfull \hbox (5.27835pt too wide) in paragraph at lines 128--130 []\OT1/cmr/m/n/10 The fol-low-ing ex-am-ple is based on an ex-am-ple taken from Beale Screamer's [] Overfull \hbox (29.78421pt too wide) detected at line 136 \OML/cmm/m/it/5 rB \OT1/cmr/m/n/5 = (179671003218315746385026655733086044982194 424660\OML/cmm/m/it/5 ; \OT1/cmr/m/n/5 6978343853596863682493012826751418309351 76314718) [] Overfull \hbox (52.28043pt too wide) detected at line 141 \OML/cmm/m/it/5 P \OT1/cmr/m/n/5 + \OML/cmm/m/it/5 r\OT1/cmr/m/n/5 (\OML/cmm/m/ it/5 nB\OT1/cmr/m/n/5 ) = (137851038548264467372645158093004000343639118915\OML /cmm/m/it/5 ; \OT1/cmr/m/n/5 110848589228676224057229230223580815024224875699)\ OML/cmm/m/it/5 : [] Overfull \hbox (69.8944pt too wide) detected at line 150 \OML/cmm/m/it/5 n\OT1/cmr/m/n/5 (\OML/cmm/m/it/5 rB\OT1/cmr/m/n/5 ) = \OML/cmm/ m/it/5 r\OT1/cmr/m/n/5 (\OML/cmm/m/it/5 nB\OT1/cmr/m/n/5 ) = (32890139351873263 7577115650601768681044040715701\OML/cmm/m/it/5 ; \OT1/cmr/m/n/5 586947838087815 993601350565488788846203887988162)\OML/cmm/m/it/5 : [] Overfull \hbox (53.80992pt too wide) detected at line 154 \OML/cmm/m/it/10 P \OT1/cmr/m/n/10 = (14489646124220757767\OML/cmm/m/it/10 ; \ OT1/cmr/m/n/10 669337780373284096274895136618194604469696830074)\OML/cmm/m/it/1 0 : [] [124] Overfull \hbox (64.49661pt too wide) in paragraph at lines 228--228 [] \OT1/cmtt/m/n/10 c := ["0","1","2","3","4","5","6","7","8","9","a","b","c" ,"d","e","f"];[] [] Overfull \hbox (311.24446pt too wide) in paragraph at lines 228--228 []\OT1/cmtt/m/n/10 E := EllipticCurve([3176890812513255034763174764138276932727 46955927, 79052896607878758718120572025718535432100651934]);[] [] Overfull \hbox (258.74492pt too wide) in paragraph at lines 228--228 []\OT1/cmtt/m/n/10 B := E![k|771507216262649826170648268565579889907769254176, 390157510246556628525279459266514995562533196655];[] [] Overfull \hbox (253.49496pt too wide) in paragraph at lines 228--228 []\OT1/cmtt/m/n/10 rB := E![k|179671003218315746385026655733086044982194424660, 697834385359686368249301282675141830935176314718];[] [] Overfull \hbox (263.99487pt too wide) in paragraph at lines 228--228 []\OT1/cmtt/m/n/10 PrnB := E![k|13785103854826446737264515809300400034363911891 5,110848589228676224057229230223580815024224875699];[] [] Overfull \hbox (80.24648pt too wide) in paragraph at lines 228--228 []\OT1/cmtt/m/n/10 (14489646124220757767 : 669337780373284096274895136618194604 469696830074 : 1)[] [] [125] File: graphics/lenstra.eps Graphic file (type eps) Overfull \hbox (48.94202pt too wide) in paragraph at lines 249--263 [][] [] Overfull \hbox (22.49698pt too wide) in paragraph at lines 297--297 []\OT1/cmtt/m/n/10 {ispowersmooth(n, B) = \\ true if and only if n is B-power smooth[] [] [126] Overfull \hbox (19.06853pt too wide) in paragraph at lines 308--313 \OT1/cmr/m/n/10 Assume that fur-ther that $\OML/cmm/m/it/10 p \OMS/cmsy/m/n/10 ^^@ \OT1/cmr/m/n/10 1$ is $\OML/cmm/m/it/10 B$\OT1/cmr/m/n/10 -power-smooth and let $\OML/cmm/m/it/10 m \OT1/cmr/m/n/10 = [](1\OML/cmm/m/it/10 ; \OT1/cmr/m/n/ 10 2\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 3\OML/cmm/m/it/10 ; [] B\OT1/cmr/m/n/10 )$. [] [127] [128] [129] Overfull \hbox (6.74712pt too wide) in paragraph at lines 486--486 [] \OT1/cmtt/m/n/10 if(isprime(p),t++;if(isalmostpowersmooth(p,B),s++,print(" BAD[] [] File: graphics/cohen_lenstra.eps Graphic file (type eps) Overfull \hbox (38.44713pt too wide) in paragraph at lines 504--532 [] [] [] [130] Overfull \hbox (32.99689pt too wide) in paragraph at lines 567--567 [] \OT1/cmtt/m/n/10 ellpow(E,[0,1]*Mod(1,N),m); \\ this fails if and only if we win![] [] Overfull \hbox (17.24702pt too wide) in paragraph at lines 619--619 []\OT1/cmtt/m/n/10 ? N = 5959; \\ This number motivated the ECM last time.[] [] Overfull \hbox (64.49661pt too wide) in paragraph at lines 619--619 []\OT1/cmtt/m/n/10 \\ Recall what happened when we tried to factor 5959 using t he p-1 method.[] [] [131] Overfull \hbox (6.74712pt too wide) in paragraph at lines 619--619 []\OT1/cmtt/m/n/10 [2 4] \\ #E(Z/101) is 16-power-smoo th,[] [] Overfull \hbox (1.49716pt too wide) in paragraph at lines 619--619 []\OT1/cmtt/m/n/10 [2 1] \\ #E(Z/59) is 29-power-smoot h,[] [] Overfull \hbox (59.24666pt too wide) in paragraph at lines 650--650 []\OT1/cmtt/m/n/10 E: y^2 = x^3 + 273687051132207711452727265152539544370874547 x+1, P=[0,1][] [] Overfull \hbox (59.24666pt too wide) in paragraph at lines 650--650 []\OT1/cmtt/m/n/10 E: y^2 = x^3 + 174264237886300715545169749498695137077020788 x+1, P=[0,1][] [] Overfull \hbox (59.24666pt too wide) in paragraph at lines 650--650 []\OT1/cmtt/m/n/10 E: y^2 = x^3 + 652986182461202633808585244537305097270008449 x+1, P=[0,1][] [] Overfull \hbox (59.24666pt too wide) in paragraph at lines 650--650 []\OT1/cmtt/m/n/10 E: y^2 = x^3 + 755060727645891482095225151281965348765197238 x+1, P=[0,1][] [] Overfull \hbox (59.24666pt too wide) in paragraph at lines 650--650 []\OT1/cmtt/m/n/10 E: y^2 = x^3 + 722355978919416556225676818691766898771312229 x+1, P=[0,1][] [] [132] Overfull \hbox (59.24666pt too wide) in paragraph at lines 650--650 []\OT1/cmtt/m/n/10 E: y^2 = x^3 + 124781379199538996805045456359983628056546634 x+1, P=[0,1][] [] Overfull \hbox (59.24666pt too wide) in paragraph at lines 650--650 []\OT1/cmtt/m/n/10 E: y^2 = x^3 + 350310715627251979278144271594744514052364663 x+1, P=[0,1][] [] Overfull \hbox (53.9967pt too wide) in paragraph at lines 650--650 []\OT1/cmtt/m/n/10 E: y^2 = x^3 + 39638500146503230913823829562620410547947307x +1, P=[0,1][] [] Overfull \hbox (69.74657pt too wide) in paragraph at lines 650--650 [] \OT1/cmtt/m/n/10 80061047060165522139279418005808 8102053408423).[] [] Overfull \hbox (53.9967pt too wide) in paragraph at lines 665--665 [] \OT1/cmtt/m/n/10 *** impossible inverse modulo: Mod(1406051123, 100432032 2301182911).[] [] Overfull \hbox (38.24684pt too wide) in paragraph at lines 665--665 [] \OT1/cmtt/m/n/10 79716645459013454877 3760793).[] [] Overfull \hbox (41.76453pt too wide) detected at line 668 \OML/cmm/m/it/10 N \OT1/cmr/m/n/10 = \OML/cmm/m/it/10 N[] \OMS/cmsy/m/n/10 ^^A \OML/cmm/m/it/10 N[] \OMS/cmsy/m/n/10 ^^A \OML/cmm/m/it/10 N[] \OMS/cmsy/m/n/10 ^^A \OML/cmm/m/it/10 N[] \OT1/cmr/m/n/10 = 1406051123 \OMS/cmsy/m/n/10 ^^A \OT 1/cmr/m/n/10 714284357 \OMS/cmsy/m/n/10 ^^A \OT1/cmr/m/n/10 2029256729 \OMS/cms y/m/n/10 ^^A \OT1/cmr/m/n/10 392836669307471617\OML/cmm/m/it/10 ; [] Overfull \hbox (22.49698pt too wide) in paragraph at lines 687--687 [] \OT1/cmtt/m/n/10 Mod(63845045623767003, 39283666930747 1617)][] [] Overfull \hbox (43.4968pt too wide) in paragraph at lines 687--687 [] \OT1/cmtt/m/n/10 *** impossible inverse modulo: Mod(615433499, 3928366693 07471617).[] [] [133] [134] [135] [136] Underfull \hbox (badness 10000) in paragraph at lines 949--950 [] File: graphics/wiles.eps Graphic file (type eps) [137]) [138] \openout2 = `chapters/bsd.aux'. (chapters/bsd.tex 8. [139 ] Overfull \hbox (42.59454pt too wide) in paragraph at lines 53--53 []\OT1/cmtt/m/n/10 http://www.msri.org/publications/ln/hosted/cmi/2000/cmiparis /index-tate.html[] [] Overfull \hbox (9.62416pt too wide) in paragraph at lines 49--55 [] $[]$ [] [140] Overfull \hbox (33.73405pt too wide) in paragraph at lines 211--213 [] [] [141] [142] [143] Overfull \hbox (62.28702pt too wide) in paragraph at lines 400--404 \OT1/cmr/m/it/10 NOT \OT1/cmr/m/n/10 nu-mer-i-cal in-te-gra-tion. In PARI, $ []$ is ap-prox-i-mated by \OT1/cmtt/m/n/10 E.omega[1]*2^(E.disc>0)\OT1/cmr/m/n/ 10 . [] [144] Overfull \hbox (17.24702pt too wide) in paragraph at lines 437--437 []\OT1/cmtt/m/n/10 ? L = (1+eps) * sum(n=1,100, ellak(E,n)/n * exp(-2*Pi*n/sqrt (N)))[] [] [145] Overfull \hbox (1.62125pt too wide) in paragraph at lines 494--494 [] [] [146] Overfull \hbox (74.99652pt too wide) in paragraph at lines 533--533 []\OT1/cmtt/m/n/10 ? r(E,s) = L1=elllseries(E,s); L2=elllseries(E,s^2-s+1); (L2 -L1)/((s-1)*L1);[] [] Overfull \hbox (0.30826pt too wide) in paragraph at lines 544--555 \OT1/cmr/m/n/10 It cer-tainly looks like $[][] \OML/cmm/m/it/10 r\OT1/cmr/m/n/1 0 (\OML/cmm/m/it/10 s\OT1/cmr/m/n/10 ) = 4$. We know for a fact that $[][] \OML /cmm/m/it/10 r\OT1/cmr/m/n/10 (\OML/cmm/m/it/10 s\OT1/cmr/m/n/10 ) \OMS/cmsy/m/ n/10 2 [] Overfull \hbox (74.99652pt too wide) in paragraph at lines 570--570 []\OT1/cmtt/m/n/10 ? r(E,s) = L1=elllseries(E,s); L2=elllseries(E,s^2-s+1); (L2 -L1)/((s-1)*L1);[] [] ) [147] \openout2 = `chapters/pari.aux'. (chapters/pari.tex [148 ] 9. [149] Overfull \hbox (10.74733pt too wide) in paragraph at lines 82--82 []\OT1/cmtt/m/n/10 ? gb(n) = forprime(p=2,n,if(isprime(n-p),return([p,n-p]))); [] [] [150] File: graphics/petros.eps Graphic file (type eps) Underfull \vbox (badness 10000) has occurred while \output is active [] [151] Overfull \hbox (64.49661pt too wide) in paragraph at lines 121--121 [] \OT1/cmtt/m/n/10 http://www.faber.co.uk/faber/million_dollar.asp?PGE=&ORD=f aber&TAG=&CID=[] [] Overfull \hbox (48.74675pt too wide) in paragraph at lines 125--125 [] \OT1/cmtt/m/n/10 http://www.informatik.uni-giessen.de/staff/richstein/ca/Go ldbach.html[] [] Overfull \hbox (1.49716pt too wide) in paragraph at lines 131--131 [] \OT1/cmtt/m/n/10 http://perso.wanadoo.fr/yves.gallot/primes/chrrcds.html#tw in[] [] [152] Overfull \hbox (6.74712pt too wide) in paragraph at lines 220--220 [] \OT1/cmtt/m/n/10 i686 running linux (ix86 kernel) 32-bit vers ion[] [] Overfull \hbox (11.99707pt too wide) in paragraph at lines 220--220 [] \OT1/cmtt/m/n/10 (readline v4.2 enabled, extended help availa ble)[] [] Overfull \hbox (53.9967pt too wide) in paragraph at lines 220--220 []\OT1/cmtt/m/n/10 PARI/GP is free software, covered by the GNU General Public License, and[] [] [153] Overfull \hbox (6.74712pt too wide) in paragraph at lines 220--220 []\OT1/cmtt/m/n/10 Type ?12 for how to get moral (and possibly technical) suppo rt.[] [] Overfull \hbox (11.99707pt too wide) in paragraph at lines 220--220 []\OT1/cmtt/m/n/10 %6 = 1378425503766585493035778406754125077322291549582802091 3935[] [] Overfull \hbox (11.99707pt too wide) in paragraph at lines 220--220 []\OT1/cmtt/m/n/10 845011397194393261309756046226816251290119446623115998366224 1797[] [] Overfull \hbox (17.24702pt too wide) in paragraph at lines 276--276 [] \OT1/cmtt/m/n/10 0: list of user-defined identifiers (variable, alias, func tion)[] [] [154] Overfull \hbox (22.49698pt too wide) in paragraph at lines 276--276 [] \OT1/cmtt/m/n/10 ?? (opens the full user's manual in a dvi prev iewer)[] [] Overfull \hbox (53.9967pt too wide) in paragraph at lines 276--276 [] \OT1/cmtt/m/n/10 ?? keyword (long help text about "keyword" from the us er's manual)[] [] Overfull \hbox (11.99707pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 addprimes bestappr bezout bezoutres bigo mega[] [] Overfull \hbox (32.99689pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 binomial chinese content contfrac cont fracpnqn[] [] Overfull \hbox (1.49716pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 core coredisc dirdiv direuler dirm ul[] [] Overfull \hbox (32.99689pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 divisors eulerphi factor factorback fact orcantor[] [] Overfull \hbox (1.49716pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 factorff factorial factorint factormod ffin it[] [] Overfull \hbox (6.74712pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 fibonacci gcd hilbert isfundamental ispr ime[] [] Overfull \hbox (17.24702pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 moebius nextprime numdiv omega prec prime[] [] Overfull \hbox (27.74693pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 prime primes qfbclassno qfbcompraw qfbh classno[] [] Overfull \hbox (1.49716pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 qfbnucomp qfbnupow qfbpowraw qfbprimeform qfbr ed[] [] Overfull \hbox (11.99707pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 quadclassunit quaddisc quadgen quadhilbert quad poly[] [] Overfull \hbox (1.49716pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 sqrtint znlog znorder znprimroot znst ar[] [] Overfull \hbox (74.99652pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 gcd(x,y,{flag=0}): greatest common divisor of x and y. flag is optional, and[] [] Overfull \hbox (32.99689pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 can be 0: default, 1: use the modular gcd algorithm (x and y must be[] [] Overfull \hbox (80.24648pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 polynomials), 2 use the subresultant algorithm (x and y must be polynomials).[] [] Overfull \hbox (90.74638pt too wide) in paragraph at lines 276--276 []\OT1/cmtt/m/n/10 \\ if set up correctly, brings up the typeset subsection fro m the manual on gcd[] [] Underfull \vbox (badness 10000) has occurred while \output is active [] [155] Overfull \hbox (33.13809pt too wide) in paragraph at lines 305--310 \OT1/cmr/m/n/10 the last file loaded). For ex-am-ple, sup-pose we change \OT1/c mtt/m/n/10 return (lift(Mod(a,p)^n)) [] [156] Overfull \hbox (22.49698pt too wide) in paragraph at lines 365--365 []\OT1/cmtt/m/n/10 %13 = 6 \\ ouch!! what have you done to m y eye![] [] [157] Overfull \hbox (22.49698pt too wide) in paragraph at lines 419--419 []\OT1/cmtt/m/n/10 input(): read an expression from the input file or standard input.[] [] Overfull \hbox (43.4968pt too wide) in paragraph at lines 419--419 []\OT1/cmtt/m/n/10 ? s \\ s is not the string "1+1", as you mi ght expect[] [] Overfull \hbox (74.99652pt too wide) in paragraph at lines 419--419 []\OT1/cmtt/m/n/10 ? type(s) \\ PARI views s as a polynomial in the variable hithere[] [] [158] Overfull \hbox (38.24684pt too wide) in paragraph at lines 474--474 []\OT1/cmtt/m/n/10 qfbclassno(x,{flag=0}): class number of discriminant x using Shanks's[] [] Overfull \hbox (43.4968pt too wide) in paragraph at lines 474--474 []\OT1/cmtt/m/n/10 method by default. If (optional) flag is set to 1, use Euler products.[] [] Overfull \hbox (48.74675pt too wide) in paragraph at lines 474--474 []\OT1/cmtt/m/n/10 ? qfbclassno(-15,1) \\ ALWAYS use flag=1, since ``the autho rs were too[] [] Overfull \hbox (53.9967pt too wide) in paragraph at lines 474--474 []\OT1/cmtt/m/n/10 %32 = 2 \\ lazy to implement Shanks' method com pletely...''[] [] Overfull \hbox (59.24666pt too wide) in paragraph at lines 474--474 []\OT1/cmtt/m/n/10 ? a=-11/9;b=28/27; \\ this is an ``amazing'' point on the curve.[] [] [159] Overfull \hbox (22.49698pt too wide) in paragraph at lines 563--563 []\OT1/cmtt/m/n/10 ? elladd(E,P,[1,0]) \\ nonsense, since [1,0] isn't even o n E!!![] [] [160] Overfull \hbox (50.53555pt too wide) in paragraph at lines 575--575 []\OT1/cmtt/m/n/5 4660645813671121765025590267647300672252945873586541077711389 394563791/920992883734992462745141522111225908861976098219465616585649245395649 ][] [] Overfull \hbox (17.24702pt too wide) in paragraph at lines 605--605 []\OT1/cmtt/m/n/10 ? for(x=0,4, for(y=0,4, if(ellisoncurve(E5,[x,y]),print([x,y ]))))[] [] Overfull \hbox (11.99707pt too wide) in paragraph at lines 605--605 []\OT1/cmtt/m/n/10 ? 5+1 - 9 \\ 8 points above, plus the point at infi nity[] [] [161] Overfull \hbox (33.73405pt too wide) in paragraph at lines 953--954 [] [] [162] Overfull \hbox (33.73405pt too wide) in paragraph at lines 1094--1095 [] [] Overfull \hbox (33.73405pt too wide) in paragraph at lines 1220--1221 [] [] [163] Overfull \hbox (33.73405pt too wide) in paragraph at lines 1438--1439 [] [] Underfull \vbox (badness 10000) has occurred while \output is active [] [164] Overfull \hbox (4.84668pt too wide) in paragraph at lines 1460--1469 \OT1/cmr/m/n/10 MAGMA also of-fers so-phis-ti-cated fea-tures for com-put-ing w ith el-lip-tic curves, [] ) [165] \openout2 = `chapters/solutions.aux'. (chapters/solutions.tex [166 ] 10. [167] [168] Overfull \hbox (10.30612pt too wide) in paragraph at lines 178--183 []\OT1/cmr/m/n/10 Using a com-puter, we find that $5352381469067 = 141307 \OMS/ cmsy/m/n/10 ^^A \OT1/cmr/m/n/10 37877681$, [] [169] [170] [171] [172] Overfull \hbox (7.17534pt too wide) in paragraph at lines 422--428 []\OT1/cmr/m/n/10 First we com-pute $\OML/cmm/m/it/10 ^^K \OT1/cmr/m/n/10 = [[] ]$. This gives $\OML/cmm/m/it/10 ^^K \OT1/cmr/m/n/10 = 1 + [][]$. [] Overfull \hbox (18.38747pt too wide) in paragraph at lines 429--435 []\OT1/cmr/m/n/10 This is $[[]][]$. As above, if $\OML/cmm/m/it/10 ^^K \OT1/cmr /m/n/10 = [[]]$ then $\OML/cmm/m/it/10 ^^K \OT1/cmr/m/n/10 = 1 + [][]$. [] [173] Overfull \hbox (21.24724pt too wide) in paragraph at lines 489--489 [] \OT1/cmtt/m/n/10 [7, 2,1,1,3,18, 5,1,1,6,30, 8,1,1,9,42, 11,1,1,12,5 4,[] [] [174] [175] [176] [177] Overfull \hbox (1.97264pt too wide) in paragraph at lines 721--728 \OT1/cmr/m/n/10 [1\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1\OML/cmm/m/it/10 ; \OT1/c mr/m/n/10 2504]$, and from this we find that $[10\OML/cmm/m/it/10 ; \OMS/cmsy/m /n/10 ^^@\OT1/cmr/m/n/10 5\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 251]$ and $[10\OML /cmm/m/it/10 ; \OT1/cmr/m/n/10 5\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 251]$ [] [178]) [179] (main.bbl [180 ]) No file main.ind. [181] (main.aux (chapters/preface.aux) (chapters/introduction.aux) (chapters/primes.aux) (chapters/crypto.aux) (chapters/reciprocity.aux) (chapters/contfrac.aux) (chapters/quadform.aux) (chapters/ell.aux) (chapters/ellapp.aux) (chapters/bsd.aux) (chapters/pari.aux) (chapters/solutions.aux)) LaTeX Warning: There were undefined references. LaTeX Warning: There were multiply-defined labels. ) Here is how much of TeX's memory you used: 3183 strings out of 20898 32915 string characters out of 196686 137758 words of memory out of 350001 6026 multiletter control sequences out of 10000+15000 21602 words of font info for 81 fonts, out of 400000 for 1000 14 hyphenation exceptions out of 1000 27i,18n,22p,248b,485s stack positions out of 1500i,100n,500p,50000b,4000s Output written on main.dvi (184 pages, 531496 bytes).