(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvips 5.511 Copyright 1986, 1993 Radical Eye Software %%Title: All.dvi %%CreationDate: Fri Oct 16 16:35:29 1998 %%Pages: 4 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%EndComments %DVIPSCommandLine: dvips -pp 91-94 All.dvi -o /net/blagny/algo/web/seminars/sem97-98/pan.ps %DVIPSSource: TeX output 1998.10.05:1746 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N} B /TR{translate}N /isls false N /vsize 11 72 mul N /@rigin{isls{[0 -1 1 0 0 0] concat}if 72 Resolution div 72 VResolution div neg scale isls{Resolution hsize -72 div mul 0 TR}if Resolution VResolution vsize -72 div 1 add mul TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{ CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N} B /I{cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook} if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255 {IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V{}B /RV statusdict begin /product where{ pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{ gsave transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{p 1 w}B /r{ p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet %%BeginProcSet: special.pro TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N /vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B /@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{/CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{10 div /rwi X /rwiSeen true N}B /@rhi {10 div /rhi X /rhiSeen true N}B /@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale true def end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{ }N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N /txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp{pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray}N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict maxlength dict begin /magscale false def normalscale currentpoint TR /psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts /psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR /showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{ SDict begin /SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial{CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{ rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR}{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath}N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin}N /@fedspecial{end}B /li{lineto}B /rl{ rlineto}B /rc{rcurveto}B /np{/SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X /startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin 39158280 55380996 1000 300 300 (/a/home/pommard/algo/salvy/Tex/Sem/Sem97-98/All.dvi) @start /Fa 8 58 df<01001F00E700070007000700070007000700070007000700070007000700FFF00C 107D8F13>49 D<1FC06070C038E03CE01C003C00380038006000C00300060408043FF87FF8FFF8 0E107E8F13>I<00300030007000F000F0017002700670047008701070107020704070C070FFFF 00700070007000700070007007FF10177F8F13>52 D<30183FF03FE03FC0200020002000200020 0027C0386020300018001C001C001CE01CE01CC0184038403030E00F800E177E8F13>I<01E006 100C1818383038300070006000E000E7C0E860F030F018E018E01CE01CE01C601C601C70183018 3030186007C00E187E9713>I<40007FFE7FFC7FFC400880108020802000400080008001800180 030003000300030007000700070007000700070002000F187E9013>I<07801860303020186018 6018601870103C303E600F8007C019F030F86038401CC00CC00CC00CC00C6008201018600FC00E 187E9713>I<0F80186030306030E018E018E01CE01CE01CE01C603C303C185C0F9C001C001800 18003870307060606021801F000E177E8F13>I E /Fb 7 108 df0 D<70F8F8F87005057C8D0D>I<000000C0000003C000000F0000003C000000F0000003C000 00070000001C00000078000001E00000078000001E00000078000000E0000000780000001E0000 000780000001E0000000780000001C0000000700000003C0000000F00000003C0000000F000000 03C0000000C0000000000000000000000000000000000000000000000000000000007FFFFF80FF FFFFC01A247C9C23>20 DI<003FF800FFF803C0000700000C0000180000300000300000600000600000C00000 C00000C00000FFFFF8FFFFF8C00000C00000C000006000006000003000003000001800000C0000 07000003C00000FFF8003FF8151C7C981E>50 D106 D<4020C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030 C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C0 30C030C030C030C030C030C03040200C2E7BA117>I E /Fc 5 107 df0 D<060F0F0E1E1E1C3C383830707060E0C04008117F910A>48 D<4000C000C000C000C000 C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C0 00C000C000C000C000C000C000C000FF807F8009227A9810>98 D<008001800180018001800180 018001800180018001800180018001800180018001800180018001800180018001800180018001 80018001800180018001800180FF80FF800922809810>I106 D E /Fd 5 91 df13 D81 D88 DI<00000000F00000000188000000039C000000033C000000073C00000007180000000600000000 0E000000000E000000000E000000001E000000001C000000001C000000003C000000003C000000 00380000000038000000007800000000780000000078000000007000000000F000000000F00000 0000F000000000F000000001F000000001E000000001E000000001E000000001E000000003E000 000003C000000003C000000003C000000007C000000007C000000007C000000007800000000F80 0000000F800000000F800000000F800000000F800000001F000000001F000000001F000000001F 000000001F000000003E000000003E000000003E000000003E000000003E000000007C00000000 7C000000007C000000007C000000007C00000000F800000000F800000000F800000000F8000000 00F800000000F000000001F000000001F000000001F000000001E000000001E000000001E00000 0003E000000003C000000003C000000003C000000003C000000007C00000000780000000078000 00000780000000078000000007000000000F000000000F000000000F000000000E000000000E00 0000001E000000001E000000001C000000001C000000003C000000003800000000380000000070 00000000700000006060000000F0E0000000F0C0000000E18000000043000000003E0000000026 657D7F19>I E /Fe 12 123 df<0008001800300030003000600060006000C000C000C0018001 800180030003000600060006000C000C000C00180018001800300030003000600060006000C000 C0000D217E9812>61 D<008000008000008000008000008000008000F087801FFC0007F00001C0 000360000220000630000C18000808001004001110808F12>63 D<001FC000707001C03803001C 06000C0E000E1C000E18000E38000E30000E70000E70000E70000E60001CE0001C600038600038 70007070F0E03109C0190B800F0E0003FC10000C10000C30000C60000FC0000FC0000700171D7F 961C>81 D<7C0018001800180018003000300030003000678068C070406060C060C060C060C060 80C080C08180C10046003C000B177E960F>98 D<003E000C000C000C000C001800180018001807 3018F0307060706060C060C060C06080C080C480C4C1C446C838700F177E9612>100 D<0300038003000000000000000000000000001C002400460046008C000C001800180018003100 3100320032001C0009177F960C>105 D<00180038001000000000000000000000000001C00220 04300430086000600060006000C000C000C000C001800180018001806300E300C60078000D1D80 960E>I<1F0006000600060006000C000C000C000C00181C1866188E190C32003C003F00318060 C060C460C460C8C0C8C0700F177E9612>I<383C0044C6004702004602008E06000C06000C0600 0C0C00180C00180C40181840181880300880300F00120E7F8D15>110 D<1C3C22462382230346 030603060306030C060C060C0C0C081A3019E018001800300030003000FC001014808D12>112 D<071018D0307060706060C060C060C06080C080C080C0C1C04780398001800180030003000300 1FC00C147E8D10>I<07840FCC1878101000200040018002000400080810083C3043E081C00E0E 7F8D10>122 D E /Ff 9 117 df<03FFFFC0003E00F0003C0078003C003C003C003E003C001E00 3C003E0078003E0078003E0078003E0078003E0078003C0078007C00F0007800F000F000F001E0 00F0078000FFFE0000F0000001E0000001E0000001E0000001E0000001E0000001E0000003C000 0003C0000003C0000003C0000003C0000003C000000780000007C00000FFFC00001F227EA121> 80 D86 D<03FC000606000F0300 0F03800601800001C0000380000380007F8003E3800F03801C0380380700780700F00708F00708 F00F08F00F08F017107867A01F83C015157D9418>97 D<00FF000381C00603C00C03C01C018038 0000780000700000F00000F00000F00000F00000F00000E00000F00000F0008070010070010038 06001C180007E00012157C9416>99 D<006000F001F001F000E000000000000000000000000000 00000001C00FC001C001C001C001C0038003800380038003800380070007000700070007000700 0E000F00FFE00C227FA10E>105 D<01C3F01FCC1801D00C01E00E01E00E01C00E03C01C03801C 03801C03801C03801C03801C0700380700380700380700380700380700380E00700F0078FFE7FF 18157F941B>110 D<007E000383800600C00C00E01C0070380070780078700078F00078F00078 F00078F00078E000F0E000F0E000E0F001E07001C07003803807001C1C0007F00015157D9418> I<01C7C01FC8E001D1E001E1E001E0C001C00003C0000380000380000380000380000380000700 000700000700000700000700000700000E00000F0000FFF00013157F9413>114 D<008000800080018001000300030007000F001F00FFF80E000E000E000E000E001C001C001C00 1C001C001C0038103810381038103810382038201C4007800D1F7C9E13>116 D E /Fg 29 123 df<007C0001C3000701810E01C11E00C11C00E23C00E27800E27800E47800E4 F000E8F000F0F000F0F000E0F000E07000E07003E030046118383207C01C18147E931D>11 D<007E01C007000E001C003C003800780078007FF0F000F000F000700070007000300018000C18 07E00F147E9312>15 D<0FFFFC1FFFFC3FFFFC608200C08400808400018400010400010C00030C 00030C00020C00060C00060C000E0C000C0E001C0E001C0E00380F0018060016147E931A>25 D<000F800038C000606000C07001C0700380780380780700780700780700780E00F00E00F00E00 F00E01E01C01C01C01C01E03801E0700390C0038F0003800003800007000007000007000007000 00E00000E00000E00000C00000151E7F9318>I<04000180080003C0100003E0100001E0200000 E0200000E02000004040040040400C0040400C0040800C008080080080C0080180C0180300C038 0600E07C0E00FFEFFC007FCFF8003F87F0001E03C0001B1480931C>33 D<70F8F8F87005057C84 0D>58 D<70F8FCFC74040404080810102040060E7C840D>I<000001C00000078000001E000000 78000001E00000078000000E00000038000000F0000003C000000F0000003C000000F0000000F0 0000003C0000000F00000003C0000000F0000000380000000E0000000780000001E00000007800 00001E0000000780000001C01A1A7C9723>I<000100030003000600060006000C000C000C0018 0018001800300030003000600060006000C000C000C00180018001800300030003000600060006 000C000C000C00180018001800300030003000600060006000C000C000C000102D7DA117>II<00FFF80FF8000F 8003E0000F000380000F000200000F000400001E000800001E002000001E004000001E00800000 3C010000003C040000003C080000003C180000007838000000787C000000793C0000007A3C0000 00F41E000000F81E000000F01E000000F00F000001E00F000001E00F000001E007800001E00780 0003C007800003C003C00003C003C00003C003C00007C003E000FFFC3FFC00251F7E9E27>75 D<0001FC0000070700001C01C0003000E000E0006001C000700380007007800038070000380E00 00381E0000381C0000383C0000383C00003878000078780000787800007878000078F00000F0F0 0000F0F00000E0F00001E0F00001C0F00003C0700003807000070078000F0038001E0038003C00 1C0070000E00E0000783800001FC00001D217E9F23>79 D<0001FC0000070700001C01C0003000 E000E000E001C000700380007007800078070000380F0000381E0000381E0000383C0000383C00 007878000078780000787800007878000078F00000F0F00000F0F00000E0F00001E0F00001C0F0 0003C070000380701C070070600F0038811E0038813C001C8170000E81E0000783808001FD0080 000101800001010000038300000386000003FE000003FC000001F8000000F0001D297E9F24>81 D<00F1800389C00707800E03801C03803C0380380700780700780700780700F00E00F00E00F00E 00F00E10F01C20F01C20703C20705C40308C400F078014147E9318>97 D<07803F800700070007 0007000E000E000E000E001C001C001CF01D0C3A0E3C0E380F380F700F700F700F700FE01EE01E E01EE01CE03CE038607060E031C01F0010207E9F14>I<007C01C207010E0F1E0F1C0E3C047800 78007800F000F000F000F000F00070017002300418380FC010147E9314>I<0000780003F80000 700000700000700000700000E00000E00000E00000E00001C00001C000F1C00389C00707800E03 801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E10F01C20F01C20703C 20705C40308C400F078015207E9F18>I<00007C0000CE00019E00039E00030C00070000070000 0700000700000E00000E00000E0000FFF0000E00000E00001C00001C00001C00001C00001C0000 380000380000380000380000380000700000700000700000700000700000E00000E00000E00000 E00000C00001C000318000798000F300006200003C000017297E9F16>102 D<001E3000713800E0F001C0700380700780700700E00F00E00F00E00F00E01E01C01E01C01E01 C01E01C01E03801E03800E07800E0B8006170001E700000700000700000E00000E00300E00781C 00F038006070003FC000151D809316>I<00E001E001E000C00000000000000000000000000000 0E00130023804380438043808700070007000E000E001C001C001C20384038403840388019000E 000B1F7E9E10>105 D<0000C00001E00001E00001C00000000000000000000000000000000000 00000000001E00006300004380008380010380010380020700000700000700000700000E00000E 00000E00000E00001C00001C00001C00001C000038000038000038000038000070000070003070 0078E000F1C0006380003E00001328819E13>I<01E0000FE00001C00001C00001C00001C00003 80000380000380000380000700000700000701E00706100E08700E10F00E20F00E40601C80001D 00001E00001FC000387000383800383800381C20703840703840703840701880E01880600F0014 207E9F18>I<1E07802318C023A06043C0704380704380708700E00700E00700E00700E00E01C0 0E01C00E01C00E03821C03841C07041C07081C03083803101801E017147E931B>110 D<03C1E004621804741C08781C08701E08701E10E01E00E01E00E01E00E01E01C03C01C03C01C0 3C01C0380380780380700380E003C1C0072380071E000700000700000E00000E00000E00000E00 001C00001C0000FFC000171D819317>112 D<00F0400388C00705800E03801C03803C03803807 00780700780700780700F00E00F00E00F00E00F00E00F01C00F01C00703C00705C0030B8000F38 0000380000380000700000700000700000700000E00000E0000FFE00121D7E9314>I<1E1E0023 210023C38043C7804387804383008700000700000700000700000E00000E00000E00000E00001C 00001C00001C00001C000038000018000011147E9315>I<007C018203010603060706060E0007 8007F803FC01FE001F00077007F006F006E004400820301FC010147E9315>I<03C1C00C622010 34701038F02038F020386040700000700000700000700000E00000E00000E00000E02061C040F1 C040F1C080E2C080446300383C0014147E931A>120 D<01E02003F04007F8C00C1F8008010000 020000040000080000100000600000C0000100000200000400800801001003003F060061FC0040 F80080700013147E9315>122 D E /Fh 1 50 df<0C003C00CC000C000C000C000C000C000C00 0C000C000C000C000C000C00FF8009107E8F0F>49 D E /Fi 33 123 df<00003FE00000E01000 018038000380780003007800070030000700000007000000070000000E0000000E0000000E0000 00FFFFE0000E00E0001C01C0001C01C0001C01C0001C01C0001C03800038038000380380003803 800038070000380700007007000070071000700E2000700E2000700E2000E00E2000E0064000E0 038000E0000000C0000001C0000001C000003180000079800000F3000000620000003C0000001D 29829F1A>12 D<1C3C3C3C3C040408081020204080060E7D840E>44 D<7FF0FFE07FE00C037D8A 10>I<70F8F8F0E005057B840E>I<01FFFFFC001E0038001E0018001E0008001E0008003C000800 3C0008003C0008003C00080078001000780800007808000078080000F0100000F0300000FFF000 00F0300001E0200001E0200001E0200001E0200003C0000003C0000003C0000003C00000078000 000780000007800000078000000F800000FFF800001E1F7D9E1E>70 D<0000FC040007030C001C 00980030007800E0007801C000380380003003800030070000300E0000301E0000201E0000203C 0000003C00000078000000780000007800000078000000F0000000F000FFF0F0000780F0000780 F0000F0070000F0070000F0070000F0070001E0038001E0018003E001C002E000E00CC00038304 0000FC00001E217A9F23>I<01FFF0001F00001E00001E00001E00003C00003C00003C00003C00 00780000780000780000780000F00000F00000F00000F00001E00001E00001E00001E00003C000 03C00003C00003C0000780000780000780000780000F8000FFF800141F7D9E12>73 D<01FFF800001F0000001E0000001E0000001E0000003C0000003C0000003C0000003C00000078 000000780000007800000078000000F0000000F0000000F0000000F0000001E0000001E0000001 E0000001E0008003C0010003C0010003C0030003C00200078006000780060007800C0007801C00 0F007800FFFFF800191F7D9E1D>76 D<0FFFFFF01E0780E0180780201007802020078020200F00 20600F0020400F0020400F0020801E0040001E0000001E0000001E0000003C0000003C0000003C 0000003C00000078000000780000007800000078000000F0000000F0000000F0000000F0000001 E0000001E0000001E0000001E0000003E00000FFFF00001C1F789E21>84 D<00F1800389C00707800E03801C03803C0380380700780700780700780700F00E00F00E00F00E 00F00E20F01C40F01C40703C40705C40308C800F070013147C9317>97 D<07803F800700070007 0007000E000E000E000E001C001C001CF01D0C3A0E3C0E380F380F700F700F700F700FE01EE01E E01EE01CE03CE038607060E031C01F0010207B9F15>I<007E0001C1000300800E07801E07801C 07003C0200780000780000780000F00000F00000F00000F00000F0000070010070020030040018 380007C00011147C9315>I<0000780003F80000700000700000700000700000E00000E00000E0 0000E00001C00001C000F1C00389C00707800E03801C03803C0380380700780700780700780700 F00E00F00E00F00E00F00E20F01C40F01C40703C40705C40308C800F070015207C9F17>I<007C 01C207010E011C013C013802780C7BF07C00F000F000F000F0007000700170023804183807C010 147C9315>I<00007800019C00033C00033C000718000700000700000E00000E00000E00000E00 000E0001FFE0001C00001C00001C00001C00003800003800003800003800003800007000007000 00700000700000700000700000E00000E00000E00000E00000C00001C00001C000018000318000 7B0000F300006600003C00001629829F0E>I<003C6000E27001C1E00380E00700E00F00E00E01 C01E01C01E01C01E01C03C03803C03803C03803C03803C07003C07001C0F001C17000C2E0003CE 00000E00000E00001C00001C00301C00783800F0700060E0003F8000141D7E9315>I<01E0000F E00001C00001C00001C00001C000038000038000038000038000070000070000071E000763000E 81800F01C00E01C00E01C01C03801C03801C03801C0380380700380700380700380E10700E2070 0C20701C20700C40E00CC060070014207D9F17>I<00C001E001E001C000000000000000000000 000000000E003300230043804300470087000E000E000E001C001C001C00384038803080708031 0033001C000B1F7C9E0E>I<03C01FC0038003800380038007000700070007000E000E000E000E 001C001C001C001C0038003800380038007000700070007100E200E200E200E200640038000A20 7C9F0C>108 D<1C0F80F0002630C318004740640C004780680E004700700E004700700E008E00 E01C000E00E01C000E00E01C000E00E01C001C01C038001C01C038001C01C038001C01C0708038 038071003803806100380380E10038038062007007006600300300380021147C9325>I<1C0F80 2630C04740604780604700704700708E00E00E00E00E00E00E00E01C01C01C01C01C01C01C0384 3803883803083807083803107003303001C016147C931A>I<007C0001C3000301800E01C01E01 C01C01E03C01E07801E07801E07801E0F003C0F003C0F003C0F00780F00700700F00700E003018 0018700007C00013147C9317>I<01C1E002621804741C04781C04701E04701E08E01E00E01E00 E01E00E01E01C03C01C03C01C03C01C0380380780380700380E003C1C0072380071E0007000007 00000E00000E00000E00000E00001C00001C0000FFC000171D809317>I<00F0400388C0070580 0E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E00F01C00F01C00 703C00705C0030B8000F380000380000380000700000700000700000700000E00000E0000FFE00 121D7C9315>I<1C1E002661004783804787804707804703008E00000E00000E00000E00001C00 001C00001C00001C000038000038000038000038000070000030000011147C9313>I<00FC0302 06010C030C070C060C000F800FF007F803FC003E000E700EF00CF00CE008401020601F8010147D 9313>I<018001C0038003800380038007000700FFF007000E000E000E000E001C001C001C001C 003800380038003820704070407080708031001E000C1C7C9B0F>I<0E00C03300E02301C04381 C04301C04701C08703800E03800E03800E03801C07001C07001C07001C07101C0E20180E20180E 201C1E200C264007C38014147C9318>I<0E03803307802307C04383C04301C04700C08700800E 00800E00800E00801C01001C01001C01001C02001C02001C04001C04001C08000E300003C00012 147C9315>I<0E00C1C03300E3C02301C3E04381C1E04301C0E04701C060870380400E0380400E 0380400E0380401C0700801C0700801C0700801C0701001C0701001C0602001C0F02000C0F0400 0E13080003E1F0001B147C931E>I<0383800CC4401068E01071E02071E02070C040E00000E000 00E00000E00001C00001C00001C00001C040638080F38080F38100E5810084C60078780013147D 9315>I<0E00C03300E02301C04381C04301C04701C08703800E03800E03800E03801C07001C07 001C07001C07001C0E00180E00180E001C1E000C3C0007DC00001C00001C00003800F03800F070 00E06000C0C0004380003E0000131D7C9316>I<01C04003E08007F1800C1F0008020000040000 08000010000020000040000080000100000200000401000802001002003E0C0063FC0041F80080 E00012147D9313>I E /Fj 10 62 df<0102040C1818303070606060E0E0E0E0E0E0E0E0E0E060 606070303018180C04020108227D980E>40 D<8040203018180C0C0E0606060707070707070707 07070606060E0C0C18183020408008227E980E>I<003000003000003000003000003000003000 003000003000003000003000003000FFFFFCFFFFFC003000003000003000003000003000003000 00300000300000300000300000300016187E931B>43 D<07C018303018701C600C600CE00EE00E E00EE00EE00EE00EE00EE00EE00E600C600C701C30181C7007C00F157F9412>48 D<03000700FF000700070007000700070007000700070007000700070007000700070007000700 07007FF00C157E9412>I<0F8030E040708030C038E0384038003800700070006000C001800300 06000C08080810183FF07FF0FFF00D157E9412>I<0FE030306018701C701C001C001800380060 07E000300018000C000E000EE00EE00EC00C401830300FE00F157F9412>I<00300030007000F0 01F001700270047008701870107020704070C070FFFE0070007000700070007003FE0F157F9412 >I<07C0183030186018E00CE00CE00EE00EE00E601E301E186E0F8E000E000C001C7018701860 3020C01F800F157F9412>57 D61 D E /Fk 15 122 df<00038000000380000007C0000007C0000007C0 00000FE000000FE000001FF000001BF000001BF0000031F8000031F8000061FC000060FC0000E0 FE0000C07E0000C07E0001803F0001FFFF0003FFFF8003001F8003001F8006000FC006000FC00E 000FE00C0007E0FFC07FFEFFC07FFE1F1C7E9B24>65 DI<0FF8001C1E003E0F803E07803E07 C01C07C00007C0007FC007E7C01F07C03C07C07C07C0F807C0F807C0F807C0780BC03E13F80FE1 F815127F9117>97 DI<03FC000E0E001C1F003C1F00781F 00780E00F80000F80000F80000F80000F80000F800007800007801803C01801C03000E0E0003F8 0011127E9115>I<03F8F00E0F381E0F381C07303C07803C07803C07803C07801C07001E0F000E 0E001BF8001000001800001800001FFF001FFFC00FFFE01FFFF07801F8F00078F00078F0007870 00707800F01E03C007FF00151B7F9118>103 DI<1E003F 003F003F003F001E00000000000000000000000000FF00FF001F001F001F001F001F001F001F00 1F001F001F001F001F001F001F00FFE0FFE00B1E7F9D0E>I108 D<01FC000F07801C01C03C01E07800F07800F0F800F8F800F8F8 00F8F800F8F800F8F800F87800F07800F03C01E01E03C00F078001FC0015127F9118>111 DI114 D<1FD830786018E018E018F000FF807FE07FF01FF807FC007CC01CC01CE01CE018F830CFC00E12 7E9113>I<0300030003000300070007000F000F003FFCFFFC1F001F001F001F001F001F001F00 1F001F001F0C1F0C1F0C1F0C0F08079803F00E1A7F9913>I121 D E /Fl 34 122 df<00F0030188070304070604020E1C021C1C041C08081C00103800203BC0D0 3E41081C22081842083C4404778584700784E00308E00008E00008E00010E00010600020700040 3000801C070003F800181A7B991D>38 D45 D<3078F06005047C830C>I<000800180030007001F00E7000E000E000E000E001C001C001C001 C0038003800380038007000700070007000F00FFF00D187C9714>49 D<00002000006000006000 00E00001E00001E000027000027000047000087000087000107000107000207000207000407000 807000FFF00100380100380200380400380400380C00381C0038FF01FF181A7E991D>65 D<000F8200706200C01603801E07000C0E000C1C000C18000C380008300008700000700000E000 00E00000E00000E00000E00020E00020E00020E000406000406000803001001006000C180003E0 00171A7A991B>67 D<01FF8000380000380000380000700000700000700000700000E00000E000 00E00000E00001C00001C00001C00001C000038000038000038000038000070000070000070000 0700000E0000FFE000111A7E990F>73 D<00FFC0000E00000E00000E00001C00001C00001C0000 1C0000380000380000380000380000700000700000700000700000E00000E00000E00000E00061 C000E1C000E180008380004700003C0000121A7C9914>I<03F8001FC00078003C000078003C00 0078005C0000B800B80000B800B800009C013800009C013800011C027000011C027000011C0470 00011C087000021C08E000021C10E000021C10E000021C20E000041C41C000041C41C000041C81 C000041C81C000080F038000080F038000080E038000180C038000380C070000FF083FF000221A 7D9922>77 D<03FFF800701C00700600700700E00700E00700E00700E00701C00E01C00E01C01C 01C03803807003FF800380000380000700000700000700000700000E00000E00000E00000E0000 1C0000FFC000181A7D991A>80 D<003F1000609001807001007003002006002006002006002006 000007000007C00003F80001FE00007F00000F8000038000018000018020018020018060030060 0300600600700C00C8180087E000141A7D9916>83 D<3FFFFC381C0C201C04401C044038048038 0480380480380400700000700000700000700000E00000E00000E00000E00001C00001C00001C0 0001C000038000038000038000038000078000FFF800161A79991B>I86 D<03CC0E2E181C381C301C701CE038E0 38E038E038C072C072C07260F261341E180F107C8F14>97 D<7E000E000E000E001C001C001C00 1C00380038003BC03C307830701870187018E038E038E038E038C070C060C0E060C063801E000D 1A7C9912>I<01F006080C181838301070006000E000E000E000E000E008E010602030C01F000D 107C8F12>I<001F80000380000380000380000700000700000700000700000E00000E0003CE00 0E2E00181C00381C00301C00701C00E03800E03800E03800E03800C07200C07200C0720060F200 6134001E1800111A7C9914>I<01E006181C08380870087010FFE0E000E000E000E000E0086010 602030C01F000D107C8F12>I<000700001980001B80003B000030000030000070000070000070 0000700007FF0000E00000E00000E00000E00000E00001C00001C00001C00001C00001C0000380 00038000038000038000038000070000070000070000660000E40000CC0000700000112181990C >I<00F300038B800607000E07000C07001C0700380E00380E00380E00380E00301C00301C0030 1C00183C0018780007B800003800003800007000607000E0E000C1C0007F000011177E8F12>I< 1F80000380000380000380000700000700000700000700000E00000E00000E7C000F86001E0700 1E07001C07001C0700380E00380E00380E00381C00701C80701C80703880703900E01900600E00 111A7E9914>I<030706000000000000384C4E8E9C9C1C3838707272E2E4643808197C980C>I<3F 0707070E0E0E0E1C1C1C1C3838383870707070E4E4E4E46830081A7D990A>108 D<307C1E00598663009E0783809E0703809C0703809C070380380E0700380E0700380E0700380E 0E00701C0E40701C0E40701C1C40701C1C80E0380C80601807001A107C8F1F>I<307C00598600 9E07009E07009C07009C0700380E00380E00380E00381C00701C80701C80703880703900E01900 600E0011107C8F16>I<01F006180C0C180E300E700E600EE00EE00EE00CE01CE018E030606030 C01F000F107C8F14>I<030F000590C009E0C009C06009C06009C0600380E00380E00380E00380 E00701C00701800703800703000E8E000E78000E00000E00001C00001C00001C00001C0000FF00 001317808F14>I<30F059189E389C189C009C0038003800380038007000700070007000E00060 000D107C8F10>114 D<03E004300830187018601C001F801FC00FE000E00060E060E06080C041 803E000C107D8F10>I<06000E000E000E000E001C001C00FFC01C003800380038003800700070 0070007000E100E100E100E200640038000A177C960D>I<38064C074E0E8E0E9C0E9C0E1C1C38 1C381C381C7039703970393079389A0F0C10107C8F15>I<380C304C0E384E1C388E1C189C1C18 9C1C181C381038381038381038381070702070702070704030704018B8800F0F0015107C8F19> 119 D<078F0008D18010F38020E18020E00020E00001C00001C00001C00001C000038200038200 C38200E78400C5880078F00011107E8F12>I<38064C074E0E8E0E9C0E9C0E1C1C381C381C381C 703870387038307838F00F700070006060E0E1C0C18047003C0010177C8F13>I E /Fm 32 123 df<387CFEFEFE7C3807077C860F>46 D<00E00001E0000FE000FFE000F3E00003 E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003 E00003E00003E00003E00003E00003E00003E00003E00003E000FFFF80FFFF80111D7C9C1A>49 D<07F0001FFE00383F007C1F80FE0FC0FE0FC0FE0FE0FE07E07C07E03807E0000FE0000FC0000F C0001F80001F00003E0000780000F00000E00001C0000380600700600E00601C00E01FFFC03FFF C07FFFC0FFFFC0FFFFC0131D7D9C1A>I<01FC0007FF000E0F801E0FC03F07E03F07E03F07E03F 07E01E0FC0000FC0000F80001F0001FC0001FC00000F800007C00003E00003F00003F83803F87C 03F8FE03F8FE03F8FE03F0FC03F07807E03C0FC01FFF8003FC00151D7E9C1A>I<0000E0000000 00E000000001F000000001F000000001F000000003F800000003F800000006FC00000006FC0000 000EFE0000000C7E0000000C7E000000183F000000183F000000303F800000301F800000701FC0 0000600FC00000600FC00000C007E00000FFFFE00001FFFFF000018003F000018003F000030001 F800030001F800060001FC00060000FC000E0000FE00FFE00FFFE0FFE00FFFE0231F7E9E28>65 DI<0007FC02003FFF0E00FE03DE03F000FE07E0003E0FC0001E 1F80001E3F00000E3F00000E7F0000067E0000067E000006FE000000FE000000FE000000FE0000 00FE000000FE000000FE0000007E0000007E0000067F0000063F0000063F00000C1F80000C0FC0 001807E0003803F0007000FE01C0003FFF800007FC001F1F7D9E26>I70 D76 D78 D<001FF80000FFFF0001F81F80 07E007E00FC003F01F8001F81F0000F83F0000FC7F0000FE7E00007E7E00007EFE00007FFE0000 7FFE00007FFE00007FFE00007FFE00007FFE00007FFE00007FFE00007F7E00007E7F0000FE7F00 00FE3F0000FC3F8001FC1F8001F80FC003F007E007E001F81F8000FFFF00001FF800201F7D9E27 >I<03FC080FFF381E03F83800F8700078700038F00038F00018F00018F80000FC00007FC0007F FE003FFF801FFFE00FFFF007FFF000FFF80007F80000FC00007C00003CC0003CC0003CC0003CE0 0038E00078F80070FE01E0E7FFC081FF00161F7D9E1D>83 D<7FFFFFFC7FFFFFFC7C07E07C7007 E01C6007E00C6007E00CE007E00EC007E006C007E006C007E006C007E0060007E0000007E00000 07E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E000 0007E0000007E0000007E0000007E0000007E00003FFFFC003FFFFC01F1E7E9D24>I<07FC001F FF003F0F803F07C03F03E03F03E00C03E00003E0007FE007FBE01F03E03C03E07C03E0F803E0F8 03E0F803E0FC05E07E0DE03FF8FE0FE07E17147F9319>97 D<01FE0007FF801F0FC03E0FC03E0F C07C0FC07C0300FC0000FC0000FC0000FC0000FC0000FC00007C00007E00003E00603F00C01F81 C007FF0001FC0013147E9317>99 D<0007F80007F80000F80000F80000F80000F80000F80000F8 0000F80000F80000F80000F801F8F80FFEF81F83F83E01F87E00F87C00F87C00F8FC00F8FC00F8 FC00F8FC00F8FC00F8FC00F87C00F87C00F87E00F83E01F81F07F80FFEFF03F8FF18207E9F1D> I<01FE0007FF800F83C01E01E03E00F07C00F07C00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00 007C00007C00003E00181E00180F807007FFE000FF8015147F9318>I<001F8000FFC001F3E003 E7E003C7E007C7E007C3C007C00007C00007C00007C00007C000FFFC00FFFC0007C00007C00007 C00007C00007C00007C00007C00007C00007C00007C00007C00007C00007C00007C00007C00007 C0003FFC003FFC0013207F9F10>I<01FC3C07FFFE0F079E1E03DE3E03E03E03E03E03E03E03E0 3E03E01E03C00F07800FFF0009FC001800001800001C00001FFF800FFFF007FFF81FFFFC3C007C 70003EF0001EF0001EF0001E78003C78003C3F01F80FFFE001FF00171E7F931A>II<1C003E007F007F007F003E001C000000000000 00000000000000FF00FF001F001F001F001F001F001F001F001F001F001F001F001F001F001F00 1F001F00FFE0FFE00B217EA00E>I108 DI< FE0FC0FE3FE01E61F01EC0F81E80F81F00F81F00F81F00F81F00F81F00F81F00F81F00F81F00F8 1F00F81F00F81F00F81F00F81F00F8FFE3FFFFE3FF18147D931D>I<01FF0007FFC01F83F03E00 F83E00F87C007C7C007CFC007EFC007EFC007EFC007EFC007EFC007E7C007C7C007C3E00F83E00 F81F83F007FFC001FF0017147F931A>II114 D<0FE63FFE701E600EE006E006F800FF C07FF83FFC1FFE03FE001FC007C007E007F006F81EFFFCC7F010147E9315>I<01800180018003 800380038007800F803F80FFFCFFFC0F800F800F800F800F800F800F800F800F800F800F860F86 0F860F860F8607CC03F801F00F1D7F9C14>II119 D<3FFFE03FFFE03C07C0380F80701F80603F00603E00607C0000F80001F80003F00003E06007C0 600F80601F80E03F00C03E01C07C03C0FFFFC0FFFFC013147F9317>122 D E /Fn 73 128 df<001F83E000F06E3001C078780380F8780300F03007007000070070000700 700007007000070070000700700007007000FFFFFF800700700007007000070070000700700007 007000070070000700700007007000070070000700700007007000070070000700700007007000 070070000700700007007000070070007FE3FF001D20809F1B>11 D<003F0000E0C001C0C00381 E00701E00701E0070000070000070000070000070000070000FFFFE00700E00700E00700E00700 E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700 E00700E07FC3FE1720809F19>I<001F81F80000F04F040001C07C06000380F80F000300F00F00 0700F00F00070070000007007000000700700000070070000007007000000700700000FFFFFFFF 000700700700070070070007007007000700700700070070070007007007000700700700070070 070007007007000700700700070070070007007007000700700700070070070007007007000700 700700070070070007007007007FE3FE3FF02420809F26>14 D<7038F87CFC7EFC7E743A040204 0204020804080410081008201040200F0E7E9F17>34 D<70F8FCFC74040404080810102040060E 7C9F0D>39 D<0020004000800100020006000C000C001800180030003000300070006000600060 00E000E000E000E000E000E000E000E000E000E000E000E0006000600060007000300030003000 180018000C000C000600020001000080004000200B2E7DA112>I<800040002000100008000C00 060006000300030001800180018001C000C000C000C000E000E000E000E000E000E000E000E000 E000E000E000E000C000C000C001C001800180018003000300060006000C000800100020004000 80000B2E7DA112>I<000600000006000000060000000600000006000000060000000600000006 000000060000000600000006000000060000000600000006000000060000FFFFFFF0FFFFFFF000 060000000600000006000000060000000600000006000000060000000600000006000000060000 00060000000600000006000000060000000600001C207D9A23>43 D<70F8FCFC74040404080810 102040060E7C840D>II<70F8F8F87005057C840D>I<03F0000E1C001C 0E00180600380700700380700380700380700380F003C0F003C0F003C0F003C0F003C0F003C0F0 03C0F003C0F003C0F003C0F003C0F003C0F003C07003807003807003807807803807001806001C 0E000E1C0003F000121F7E9D17>48 D<018003800F80F380038003800380038003800380038003 80038003800380038003800380038003800380038003800380038003800380038007C0FFFE0F1E 7C9D17>I<03F0000C1C00100E00200700400780800780F007C0F803C0F803C0F803C02007C000 07C0000780000780000F00000E00001C0000380000700000600000C0000180000300000600400C 00401800401000803FFF807FFF80FFFF80121E7E9D17>I<03F0000C1C00100E00200F00780F80 780780780780380F80000F80000F00000F00000E00001C0000380003F000003C00000E00000F00 0007800007800007C02007C0F807C0F807C0F807C0F00780400780400F00200E001C3C0003F000 121F7E9D17>I<000600000600000E00000E00001E00002E00002E00004E00008E00008E00010E 00020E00020E00040E00080E00080E00100E00200E00200E00400E00C00E00FFFFF0000E00000E 00000E00000E00000E00000E00000E0000FFE0141E7F9D17>I<1803001FFE001FFC001FF8001F E00010000010000010000010000010000010000011F000161C00180E0010070010078000038000 03800003C00003C00003C07003C0F003C0F003C0E00380400380400700200600100E000C380003 E000121F7E9D17>I<007C000182000701000E03800C07801C0780380300380000780000700000 700000F1F000F21C00F40600F80700F80380F80380F003C0F003C0F003C0F003C0F003C07003C0 7003C07003803803803807001807000C0E00061C0001F000121F7E9D17>I<03F0000C0C001006 003003002001806001806001806001807001807803003E03003F06001FC8000FF00003F80007FC 000C7E00103F00300F806003804001C0C001C0C000C0C000C0C000C0C000806001802001001002 000C0C0003F000121F7E9D17>56 D<03F0000E18001C0C00380600380700700700700380F00380 F00380F003C0F003C0F003C0F003C0F003C07007C07007C03807C0180BC00E13C003E3C0000380 000380000380000700300700780600780E00700C002018001070000FC000121F7E9D17>I<70F8 F8F8700000000000000000000070F8F8F87005147C930D>I<70F8F8F870000000000000000000 0070F0F8F878080808101010202040051D7C930D>I<7FFFFFE0FFFFFFF0000000000000000000 0000000000000000000000000000000000000000000000FFFFFFF07FFFFFE01C0C7D9023>61 D<000100000003800000038000000380000007C0000007C0000007C0000009E0000009E0000009 E0000010F0000010F0000010F00000207800002078000020780000403C0000403C0000403C0000 801E0000801E0000FFFE0001000F0001000F0001000F00020007800200078002000780040003C0 0E0003C01F0007E0FFC03FFE1F207F9F22>65 DI<000FC04000 7030C001C009C0038005C0070003C00E0001C01E0000C01C0000C03C0000C07C0000407C000040 78000040F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000F80000 00780000007C0000407C0000403C0000401C0000401E0000800E000080070001000380020001C0 040000703800000FC0001A217D9F21>IIII<000FE0200078186000E004E0038002E0070001 E00F0000E01E0000601E0000603C0000603C0000207C00002078000020F8000000F8000000F800 0000F8000000F8000000F8000000F8000000F8007FFCF80003E0780001E07C0001E03C0001E03C 0001E01E0001E01E0001E00F0001E0070001E0038002E000E0046000781820000FE0001E217D9F 24>III<0FFFC0007C00003C00003C00003C00003C00003C00003C00003C00003C0000 3C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C0020 3C00F83C00F83C00F83C00F0380040780040700030E0000F800012207E9E17>I76 DII80 D<07E0800C1980100780300380600180600180E00180E00080E000 80E00080F00000F000007800007F00003FF0001FFC000FFE0003FF00001F800007800003C00003 C00001C08001C08001C08001C08001C0C00180C00380E00300F00600CE0C0081F80012217D9F19 >83 D<7FFFFFE0780F01E0600F0060400F0020400F0020C00F0030800F0010800F0010800F0010 800F0010000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F00 00000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F 0000001F800007FFFE001C1F7E9E21>IIII89 D91 D<080410082010201040204020804080408040B85CFC7EFC7E 7C3E381C0F0E7B9F17>II<1FE000303000781800781C00300E00 000E00000E00000E0000FE00078E001E0E00380E00780E00F00E10F00E10F00E10F01E10781E10 3867200F83C014147E9317>97 D<0E0000FE00000E00000E00000E00000E00000E00000E00000E 00000E00000E00000E00000E3E000EC3800F01C00F00E00E00E00E00700E00700E00780E00780E 00780E00780E00780E00780E00700E00700E00E00F00E00D01C00CC300083E0015207F9F19>I< 03F80E0C1C1E381E380C70007000F000F000F000F000F000F00070007000380138011C020E0C03 F010147E9314>I<000380003F8000038000038000038000038000038000038000038000038000 038000038003E380061B801C0780380380380380700380700380F00380F00380F00380F00380F0 0380F003807003807003803803803807801C07800E1B8003E3F815207E9F19>I<03F0000E1C00 1C0E00380700380700700700700380F00380F00380FFFF80F00000F00000F00000700000700000 3800801800800C010007060001F80011147F9314>I<007C00C6018F038F070607000700070007 00070007000700FFF0070007000700070007000700070007000700070007000700070007000700 0700070007007FF01020809F0E>I<0000E003E3300E3C301C1C30380E00780F00780F00780F00 780F00780F00380E001C1C001E380033E0002000002000003000003000003FFE001FFF800FFFC0 3001E0600070C00030C00030C00030C000306000603000C01C038003FC00141F7F9417>I<0E00 00FE00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E3E000E43 000E81800F01C00F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C0FFE7FC16207F9F19>I<1C003E003E003E001C00000000000000 0000000000000E007E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E00FFC00A1F809E0C>I<0E0000FE00000E00000E00000E00000E00000E00000E00000E 00000E00000E00000E00000E0FF00E03C00E03000E02000E04000E08000E10000E30000E70000E F8000F38000E1C000E1E000E0E000E07000E07800E03800E03C00E03E0FFCFF815207F9F18> 107 D<0E00FE000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E00FFE00B20809F0C>I<0E1F01F0 00FE618618000E81C81C000F00F00E000F00F00E000E00E00E000E00E00E000E00E00E000E00E0 0E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00 E00E000E00E00E000E00E00E00FFE7FE7FE023147F9326>I<0E3E00FE43000E81800F01C00F01 C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C0FFE7FC16147F9319>I<01F800070E001C03803801C03801C07000E07000E0F000F0F0 00F0F000F0F000F0F000F0F000F07000E07000E03801C03801C01C0380070E0001F80014147F93 17>I<0E3E00FEC3800F01C00F00E00E00E00E00F00E00700E00780E00780E00780E00780E0078 0E00780E00700E00F00E00E00F01E00F01C00EC3000E3E000E00000E00000E00000E00000E0000 0E00000E00000E0000FFE000151D7F9319>I<03E0800619801C05803C07803803807803807003 80F00380F00380F00380F00380F00380F003807003807803803803803807801C0B800E138003E3 80000380000380000380000380000380000380000380000380003FF8151D7E9318>I<0E78FE8C 0F1E0F1E0F0C0E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFE00F147F 9312>I<1F9030704030C010C010C010E00078007F803FE00FF00070803880188018C018C018E0 30D0608F800D147E9312>I<020002000200060006000E000E003E00FFF80E000E000E000E000E 000E000E000E000E000E000E000E080E080E080E080E080610031001E00D1C7F9B12>I<0E01C0 FE1FC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E03C00603C0030DC001F1FC16147F9319>III<7FC3FC0F01E00701C007018003810001 C20000E40000EC00007800003800003C00007C00004E000087000107000303800201C00601E01E 01E0FF07FE1714809318>II<3FFF380E200E201C403840 78407000E001E001C00380078007010E011E011C0338027006700EFFFE10147F9314>I<1C043F 1863F080E00E047C9D17>126 D<30307878F87C787830300E057C9E17>I E /Fo 23 123 df<60F0F06004047C830C>46 D<000600000006000000060000000F0000000F00 00000F00000017800000178000001780000023C0000023C0000023C0000041E0000041E0000041 E0000080F0000080F0000180F8000100780001FFF80003007C0002003C0002003C0006003E0004 001E0004001E000C001F001E001F00FF80FFF01C1D7F9C1F>65 D73 D<1FC000307000783800781C00301C00001C00001C0001FC000F1C 00381C00701C00601C00E01C40E01C40E01C40603C40304E801F870012127E9115>97 D<07E00C301878307870306000E000E000E000E000E000E00060007004300418080C3007C00E12 7E9112>99 D<003F00000700000700000700000700000700000700000700000700000700000700 03E7000C1700180F00300700700700600700E00700E00700E00700E00700E00700E00700600700 700700300700180F000C370007C7E0131D7E9C17>I<03E00C301818300C700E6006E006FFFEE0 00E000E000E00060007002300218040C1803E00F127F9112>I<00F8018C071E061E0E0C0E000E 000E000E000E000E00FFE00E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E007FE00F1D809C0D>I<00038003C4C00C38C01C3880181800381C00381C00381C00381C 001818001C38000C300013C0001000003000001800001FF8001FFF001FFF803003806001C0C000 C0C000C0C000C06001803003001C0E0007F800121C7F9215>II<18003C003C0018000000000000000000000000000000FC001C001C001C001C001C001C00 1C001C001C001C001C001C001C001C001C001C00FF80091D7F9C0C>I108 DII<03F0000E1C00180600300300700380600180E0 01C0E001C0E001C0E001C0E001C0E001C06001807003803003001806000E1C0003F00012127F91 15>II114 D<1F9030704030C010C010E010F8007F803FE00FF000F880 388018C018C018E010D0608FC00D127F9110>I<04000400040004000C000C001C003C00FFE01C 001C001C001C001C001C001C001C001C001C101C101C101C101C100C100E2003C00C1A7F9910> II<7F8FF00F03800F030007020003840001 C80001D80000F00000700000780000F800009C00010E00020E000607000403801E07C0FF0FF815 12809116>120 DI<7FFC70386038407040F040E041C003C0038007000F040E04 1C043C0C380870087038FFF80E127F9112>I E /Fp 67 128 df<3C42818181423C080776991D> 23 D<00800100020004000C00080018003000300030006000600060006000E000E000E000E000 E000E000E000E000E000E0006000600060006000300030003000180008000C0004000200010000 8009267D9B0F>40 D<8000400020001000180008000C0006000600060003000300030003000380 03800380038003800380038003800380038003000300030003000600060006000C000800180010 0020004000800009267E9B0F>I<000C0000000C0000000C0000000C0000000C0000000C000000 0C0000000C0000000C0000000C0000000C0000000C0000FFFFFF80FFFFFF80000C0000000C0000 000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C00 00191A7E951E>43 D<60F0F07010101020204080040B7D830B>II<60F0 F06004047D830B>I<078018603030303060186018E01CE01CE01CE01CE01CE01CE01CE01CE01C E01CE01CE01C6018601870383030186007800E187E9713>48 D<03000700FF0007000700070007 000700070007000700070007000700070007000700070007000700070007000700FFF00C187D97 13>I<0F80106020304038803CC01CE01C401C003C003800380070006000C00180010002000404 0804100430083FF87FF8FFF80E187E9713>I<0F8010E020706078703820380078007000700060 00C00F8000E000700038003C003CE03CE03CC03C4038407030E00F800E187E9713>I<00300030 007000F000F001700370027004700C7008701070307020704070C070FFFF007000700070007000 70007007FF10187F9713>I<30183FF03FE03FC02000200020002000200027C038602030003800 18001C001C401CE01CE01C80184038403030E00F800E187E9713>I<01E006100C181838303830 0070006000E000E7C0E860F030F018E018E01CE01CE01C601C601C701830183030186007C00E18 7E9713>I<40007FFE7FFC7FFC4008801080108020004000400080018001800100030003000300 030007000700070007000700070002000F197E9813>I<07801860303020186018601860187010 3C303E600F8007C019F030F86038401CC00CC00CC00CC00C6008201018600FC00E187E9713>I< 07801860303070306018E018E018E01CE01CE01C601C603C303C185C0F9C001C00180018003870 307060604021801F000E187E9713>I<60F0F060000000000000000060F0F06004107D8F0B>I<00 0C0000000C0000000C0000001E0000001E0000003F000000270000002700000043800000438000 004380000081C0000081C0000081C0000100E0000100E00001FFE0000200700002007000060078 00040038000400380008001C0008001C001C001E00FF00FFC01A1A7F991D>65 DI<003F0201C0C603002E0E001E1C000E1C0006380006780002700002700002F0 0000F00000F00000F00000F00000F000007000027000027800023800041C00041C00080E000803 003001C0C0003F00171A7E991C>IIII72 DI<1FFC00E000E000E000E000E000E0 00E000E000E000E000E000E000E000E000E000E000E000E000E040E0E0E0E0E041C061801E000E 1A7D9914>I76 DII<007F000001C1C000070070000E0038001C001C003C001E00 38000E0078000F0070000700F0000780F0000780F0000780F0000780F0000780F0000780F00007 80F000078078000F0078000F0038000E003C001E001C001C000E0038000700700001C1C000007F 0000191A7E991E>II<0FC21836200E6006C006C002C002C002E00070007E003F E01FF807FC003E000E00070003800380038003C002C006E004D81887E0101A7E9915>83 D<7FFFFF00701C0700401C0100401C0100C01C0180801C0080801C0080801C0080001C0000001C 0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C000000 1C0000001C0000001C0000001C0000001C0000001C000003FFE000191A7F991C>IIII89 D91 D93 D<3F8070C070E020700070007007F01C70 30707070E070E071E071E0F171FB1E3C10107E8F13>97 DI<07F80C1C381C3008 7000E000E000E000E000E000E0007000300438080C1807E00E107F8F11>I<007E00000E00000E 00000E00000E00000E00000E00000E00000E00000E0003CE000C3E00380E00300E00700E00E00E 00E00E00E00E00E00E00E00E00E00E00600E00700E00381E001C2E0007CFC0121A7F9915>I<07 C01C3030187018600CE00CFFFCE000E000E000E0006000300438080C1807E00E107F8F11>I<01 F0031807380E100E000E000E000E000E000E00FFC00E000E000E000E000E000E000E000E000E00 0E000E000E000E000E007FE00D1A80990C>I<0FCE187330307038703870387038303018602FC0 2000600070003FF03FFC1FFE600FC003C003C003C0036006381C07E010187F8F13>II<18003C003C001800000000000000000000000000FC001C001C001C001C001C001C001C00 1C001C001C001C001C001C001C00FF80091A80990A>I107 DIII<07E01C38300C700E60 06E007E007E007E007E007E0076006700E381C1C3807E010107F8F13>II<03C2000C2600381E00300E 00700E00E00E00E00E00E00E00E00E00E00E00E00E00700E00700E00381E001C2E0007CE00000E 00000E00000E00000E00000E00000E00007FC012177F8F14>II<1F2060E04020C020C020F0007F 003FC01FE000F080708030C030C020F0408F800C107F8F0F>I<0400040004000C000C001C003C 00FFC01C001C001C001C001C001C001C001C001C201C201C201C201C200E4003800B177F960F> IIIIII<7FF86070407040E041C041C00380070007000E081C081C08381070107030FFF00D107F8F11> II<6180F3C0F3C061800A047C9913>127 D E /Fq 20 122 df<000070000000007000000000F800000000F800000000F800000001FC00000001FC00 000003FE00000003FE00000003FE00000006FF000000067F0000000E7F8000000C3F8000000C3F 800000183FC00000181FC00000381FE00000300FE00000300FE00000600FF000006007F00000E0 07F80000FFFFF80000FFFFF800018001FC00018001FC00038001FE00030000FE00030000FE0006 00007F000600007F00FFE00FFFF8FFE00FFFF825227EA12A>65 D<0003FE0080001FFF818000FF 01E38001F8003F8003E0001F8007C0000F800F800007801F800007803F000003803F000003807F 000001807E000001807E00000180FE00000000FE00000000FE00000000FE00000000FE00000000 FE00000000FE00000000FE000000007E000000007E000001807F000001803F000001803F000003 801F800003000F8000030007C000060003F0000C0001F800380000FF00F000001FFFC0000003FE 000021227DA128>67 D80 D<3FFFFFE03FFFFFE03F801FC03E003FC03C003F8038007F007000FF007000FE007001FE006003 FC006003F8006007F8000007F000000FE000001FE000001FC000003FC000007F8000007F000000 FF000000FE006001FC006003FC006003F8006007F800E00FF000E00FE000E01FE001C01FC001C0 3F8003C07F8007C07F003FC0FFFFFFC0FFFFFFC01B227DA122>90 D<07FC001FFF803F07C03F03 E03F01E03F01F01E01F00001F00001F0003FF003FDF01FC1F03F01F07E01F0FC01F0FC01F0FC01 F0FC01F07E02F07E0CF81FF87F07E03F18167E951B>97 D<00FE0007FF800F87C01E01E03E01F0 7C00F07C00F8FC00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00007E00003E0018 1F00300FC07003FFC000FF0015167E951A>101 D<003F8000FFC001E3E003C7E007C7E00F87E0 0F83C00F80000F80000F80000F80000F80000F8000FFFC00FFFC000F80000F80000F80000F8000 0F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F8000 0F80007FF8007FF80013237FA211>I<03FC1E0FFF7F1F0F8F3E07CF3C03C07C03E07C03E07C03 E07C03E07C03E03C03C03E07C01F0F801FFF0013FC003000003000003800003FFF801FFFF00FFF F81FFFFC3800FC70003EF0001EF0001EF0001EF0001E78003C7C007C3F01F80FFFE001FF001821 7E951C>II<1C003E00 7F007F007F003E001C000000000000000000000000000000FF00FF001F001F001F001F001F001F 001F001F001F001F001F001F001F001F001F001F001F001F00FFE0FFE00B247EA310>I108 DII<00FE0007FFC00F83E01E00F03E00F87C007C7C007C7C007CFC007EFC007EFC007EFC007EFC00 7EFC007EFC007E7C007C7C007C3E00F81F01F00F83E007FFC000FE0017167E951C>II114 D<0FF3003FFF00781F00600700E00300E00300F00300FC00007FE0007F F8003FFE000FFF0001FF00000F80C00780C00380E00380E00380F00700FC0E00EFFC00C7F00011 167E9516>I<0180000180000180000180000380000380000780000780000F80003F8000FFFF00 FFFF000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F8180 0F81800F81800F81800F81800F830007C30003FE0000F80011207F9F16>I120 DI E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%PaperSize: A4 %%EndSetup %%Page: 91 1 91 0 bop 272 269 a Fq(Algorithm)16 b(for)j(Appro)n(ximating)e(Complex)g(P)n (olynomial)g(Zeros)858 396 y Ff(Victor)f(P)o(an)734 463 y Fn(Lehman)g (College,)g(CUNY)850 563 y(June)g(8,)e(1998)708 662 y([summary)g(b)o(y)h (Bruno)h(Salvy])884 791 y Fk(Abstract)149 852 y Fo(An)h(algorithm)c(for)j (appro)o(ximating)d(complex)h(p)q(olynomial)f(zeros)k(is)f(presen)o(ted.)27 b(Its)16 b(complexit)o(y)f(is)149 902 y(optimal)d(up)i(to)f(p)q (olylogarithmic)e(factors)j(and)g(holds)g(the)g(curren)o(t)h(record.)50 976 y Fn(Finding)h(ro)q(ots)e(of)h(a)f(complex)i(p)q(olynomial)h(n)o (umerically)g(in)f(a)e(guaran)o(teed)h(w)o(a)o(y)f(with)h(a)g(\014xed)g (prescrib)q(ed)0 1030 y(accuracy)e(is)g(di\016cult)h(when)f(no)g(appro)o (ximation)f(is)i(kno)o(wn)e(in)h(adv)m(ance.)20 b(This)14 b(task)d(cannot)i (b)q(e)g(p)q(erformed)g(in)0 1084 y(a)j(\014xed)g(precision)i(en)o(vironmen)o (t)e(and)h(implemen)o(tations)g(in)g(computer)f(algebra)g(systems)g(\(where)g (arbitrary)0 1138 y(precision)k(is)g(a)o(v)m(ailable\))g(are)f(seldom)g(able) h(to)e(treat)g(p)q(olynomials)i(of)f(degree)g(a)g(few)f(h)o(undreds.)32 b(Ho)o(w)o(ev)o(er,)0 1192 y(p)q(olynomials)16 b(of)e(v)o(ery)g(high)h (degree)g(arise)f(frequen)o(tly)h(when)g(solving)g(a)f(p)q(olynomial)i (system)e(b)o(y)g(elimination.)0 1246 y(The)h(w)o(ork)g(summarized)h(here)f (pro)o(vides)h(an)f(algorithm)g(supp)q(orting)h(the)f(follo)o(wing)h (theorem.)0 1328 y Fm(Theorem)h(1.)22 b Fi(L)n(et)d Fg(p)p Fn(\()p Fg(x)p Fn(\))f Fi(b)n(e)h(a)g(monic)g(p)n(olynomial)g(of)g(de)n(gr)n (e)n(e)g Fg(n)g Fi(and)g Fg(z)1296 1335 y Fj(1)1316 1328 y Fg(;)8 b(:)g(:)g(:)d(;)j(z)1439 1335 y Fe(n)1481 1328 y Fi(its)19 b(zer)n(os,)g(with)h Fb(j)p Fg(z)1816 1335 y Fe(i)1829 1328 y Fb(j)e(\024)g Fn(1)p Fi(,)0 1382 y Fg(i)12 b Fn(=)h(1)p Fg(;)8 b(:)g(:)g(:)d(;)j(n)p Fi(.)20 b(F)m(or)c(a)g(\014xe)n(d)g(p)n(ositive)g Fg(b)p Fi(,)g(appr)n(oximations)h Fg(z)1046 1366 y Fe(?)1044 1395 y(i)1082 1382 y Fi(satisfying)661 1463 y Fb(j)p Fg(z)695 1470 y Fe(i)719 1463 y Fb(\000)11 b Fg(z)788 1444 y Fe(?)786 1474 y(i)808 1463 y Fb(j)h Fg(<)h Fn(2)904 1444 y Fc(\000)p Fe(b)948 1463 y Fg(;)100 b(i)13 b Fn(=)g(1)p Fg(;)8 b(:)g(:)g(:)t(;)g(n)-1289 b Fn(\(1\))0 1549 y Fi(c)n(an)16 b(b)n(e)g(c)n(ompute)n(d)g(at)h(a)g(c)n(ost) e(b)n(ounde)n(d)i(by)768 1537 y Fn(~)758 1549 y Fg(O)q Fn(\()p Fg(n)p Fn(\))f Fi(arithmetic)h(op)n(er)n(ations)f(and)1409 1537 y Fn(~)1398 1549 y Fg(O)q Fn(\()p Fg(n)1479 1532 y Fj(2)1499 1549 y Fn(\()p Fg(b)9 b Fn(+)i Fg(n)p Fn(\)\))16 b Fi(b)n(o)n(ole)n(an)f(op)n (er)n(a-)0 1606 y(tions.)20 b(The)c(notation)416 1595 y Fn(~)405 1606 y Fg(O)i Fi(me)n(ans)d(that)i(factors)f Fn(log)9 b Fg(n)p Fi(,)16 b Fn(log)8 b Fg(b)16 b Fi(or)h(smal)r(ler)f(ar)n(e)g(ne)n(gle)n(cte)n (d.)50 1689 y Fn(Muc)o(h)e(more)g(precise)i(statemen)o(ts,)d(pro)q(ofs)h(and) g(parallel)i(complexit)o(y)g(estimates)e(can)g(b)q(e)h(found)g(in)g([5])f (and)0 1743 y(a)h(p)q(edagogical)h(in)o(tro)q(duction)g(to)f(this)h(area)e (is)i([6)o(].)50 1797 y(The)c(statemen)o(t)f(of)h(the)g(theorem)g(can)g(b)q (e)h(mo)q(di\014ed)h(to)d(accommo)q(date)h(p)q(olynomials)i(whic)o(h)f(are)f (not)f(monic)0 1851 y(\(b)o(y)k(\014rst)g(scaling)i(the)e(co)q(e\016cien)o (ts\))h(or)f(with)h(ro)q(ots)e(of)h(mo)q(dulus)i(larger)e(than)g(1)g(b)o(y)h (computing)g(a)f(b)q(ound)h(on)0 1905 y(the)f(mo)q(duli)i(\(see)e(b)q(elo)o (w\))h(and)f(then)h(scaling)g(the)f(p)q(olynomial.)781 2004 y(1.)26 b Fm(Lo)o(w)o(er)16 b(Bounds)50 2085 y Fn(It)k(is)h(clear)f(that)g (the)g(arithmetical)h(complexit)o(y)961 2074 y(~)951 2085 y Fg(O)q Fn(\()p Fg(n)p Fn(\))e(is)i(optimal,)h(since)f Fg(n)f Fn(co)q(e\016cien)o(ts)h(of)f(the)g(input)0 2143 y(p)q(olynomial)14 b(ha)o(v)o(e)e(to)f(b)q(e)i(treated.)18 b(The)13 b(b)q(o)q(olean)g(complexit) o(y)1113 2131 y(~)1103 2143 y Fg(O)q Fn(\()p Fg(n)1184 2126 y Fj(2)1203 2143 y Fn(\()p Fg(b)t Fn(+)t Fg(n)p Fn(\)\))f(is)g(optimal)h(in)g (the)f(v)o(ery)g(frequen)o(t)0 2197 y(case)j Fg(n)e Fn(=)g Fg(O)q Fn(\()p Fg(b)p Fn(\).)50 2251 y(Actually)l(,)f Fg(O)q Fn(\()p Fg(n)320 2234 y Fj(2)340 2251 y Fg(b)p Fn(\))d(is)i(ev)o(en)g(a)f(lo) o(w)o(er)g(b)q(ound)i(for)d(the)i(computation)f(of)g Fi(one)k Fn(ro)q(ot)9 b(of)h(p)q(olynomials)i(of)e(degree)h Fg(n)p Fn(.)0 2305 y(This)19 b(b)q(ound)g(follo)o(ws)f(from)f(the)h(high)h(susceptibili)q (t)o(y)h(of)e(the)g(ro)q(ots)f(of)h(a)g(p)q(olynomial)h(with)g(resp)q(ect)f (to)g(the)0 2359 y(co)q(e\016cien)o(ts.)k(F)l(or)15 b(instance,)h(the)g(p)q (olynomial)h Fg(x)861 2343 y Fe(n)895 2359 y Fb(\000)11 b Fg(a)k Fn(with)h(a)g(small)g Fg(a)e(>)f Fn(0)j(has)f(for)g(ro)q(ot)g Fg(a)1640 2343 y Fj(1)p Fe(=n)1699 2359 y Fn(.)21 b(If)16 b(this)g(ro)q(ot)0 2413 y(is)h(of)g(order)g(2)245 2397 y Fc(\000)p Fe(b)289 2413 y Fn(,)g(c)o(hanging)g Fg(a)g Fn(to)f(0)h(is)g(a)g(c)o(hange)g(of)f(the)h Fg(nb)p Fn(-th)g(bit)g(of)g(a)g(co)q(e\016cien)o(t)g(that)g(c)o(hanges)f(the) h Fg(b)p Fn(-th)0 2467 y(bit)g(of)f(the)g(ro)q(ot.)23 b(This)16 b(reasoning)h(extends)g(to)e(other)h(co)q(e\016cien)o(ts:)23 b(let)17 b Fg(p)e Fn(=)f Fg(O)q Fn(\()p Fg(n)p Fn(\))i(and)h(consider)g Fg(x)1787 2450 y Fe(n)1821 2467 y Fb(\000)12 b Fg(ax)1918 2450 y Fe(p)1937 2467 y Fn(.)0 2521 y(Then)17 b(again)g(a)g(c)o(hange)g(of)g(a)f (bit)i(at)e(p)q(osition)i Fg(O)q Fn(\()p Fg(nb)p Fn(\))e(mo)q(di\014es)i(the) f Fg(b)p Fn(-th)f(bit)i(of)e(the)h(solution.)26 b(Th)o(us)17 b Fg(b)g Fn(bits)0 2575 y(of)e(the)g(solution)g(dep)q(end)i(on)e Fg(O)q Fn(\()p Fg(nb)p Fn(\))f(bits)h(of)g(eac)o(h)g(of)f Fg(O)q Fn(\()p Fg(n)p Fn(\))h(co)q(e\016cien)o(ts,)g(whence)h(the)f Fg(O)q Fn(\()p Fg(n)1622 2558 y Fj(2)1642 2575 y Fg(b)p Fn(\))f(lo)o(w)o(er)g (b)q(ound.)0 2629 y(This)i(example)g(also)f(illustrates)h(wh)o(y)f(clusters)h (of)f(zeros)g(defeat)g(man)o(y)g(n)o(umerical)h(algorithms.)957 2679 y Fj(91)p eop %%Page: 92 2 92 1 bop 0 22 a Fj(92)657 120 y Fn(2.)26 b Fm(Outline)19 b(of)f(the)f (Algorithm)50 201 y Fn(The)g(algorithm)h(is)g(based)g(on)f(a)g(splitting)i (tec)o(hnique)g(where)e(the)h(p)q(olynomial)h Fg(p)e Fn(is)h(split)h(in)o(to) e(factors)f(of)0 255 y(degree)21 b Fg(k)g Fn(and)f Fg(n)14 b Fb(\000)g Fg(k)21 b Fn(with)f Fg(k)i Fn(=)g Fg(\013n)p Fn(,)f(for)f(some)g Fg(\013)h Fb(2)g Fn(\(1)p Fg(=)p Fn(2)p Fg(;)8 b(\032)p Fn(\),)18 b Fg(\032)i Fn(b)q(eing)i(\014xed.)35 b(Applying)22 b(this)f(pro)q(cess)0 309 y(recursiv)o(ely)l(,)16 b(an)o(y)f(p)q(olynomial)i(can)e(b)q(e)h (completely)h(factored)d(in)i Fg(O)q Fn(\(log)8 b Fg(n)p Fn(\))15 b(steps.)50 363 y(The)g(splitting)i(itself)f(is)g(computed)f(in)h(3)f(steps:) 50 430 y(1.)20 b(Find)c(a)f(\\splitting")h(circle)h(not)d(\\to)q(o)h(close")g (to)g(ro)q(ots)f(of)h Fg(p)g Fn(and)g(con)o(taining)h Fg(\013n)g Fn(of)f(them;)50 484 y(2.)20 b(Compute)15 b(the)g(p)q(olynomial)i(v)m (anishing)g(at)e(these)g Fg(\013n)h Fn(ro)q(ots;)50 538 y(3.)k(Divide)c Fg(p)g Fn(b)o(y)f(this)g(p)q(olynomial)i(to)e(obtain)g(the)g(other)g(factor.) 0 605 y(Eac)o(h)g(of)g(these)g(steps)g(has)g(to)g(b)q(e)h(p)q(erformed)f(in)h Fg(O)q Fn(\()p Fg(n)945 588 y Fj(2)965 605 y Fg(b)9 b Fn(+)i Fg(n)1067 588 y Fj(3)1087 605 y Fn(\))k(b)q(o)q(olean)h(op)q(erations)f(to)g (yield)i(the)e(theorem.)50 659 y(The)j(factors)e Fg(p)319 666 y Fe(k)358 659 y Fn(and)i Fg(p)472 666 y Fe(n)p Fc(\000)p Fe(k)559 659 y Fn(of)f Fg(p)h Fn(are)f(computed)h(n)o(umerically)l(.)29 b(The)18 b(follo)o(wing)g(t)o(w)o(o)f(lemmas)g(sho)o(w)g(ho)o(w)0 713 y(the)d(precision)i(with)f(whic)o(h)g(they)g(are)f(required)h(can)g(b)q (e)g(b)q(ounded)h(b)o(y)e(ensuring)h(that)f Fg(\017)1540 696 y Fe(?)1575 713 y Fn(is)h(su\016cien)o(tly)g(small)0 767 y(in)h(the)f(follo)o (wing)h(inequalit)o(y:)628 846 y Fb(k)p Fg(p)p Fn(\()p Fg(x)p Fn(\))9 b Fb(\000)i Fg(p)814 853 y Fe(k)835 846 y Fn(\()p Fg(x)p Fn(\))p Fg(p)920 853 y Fe(n)p Fc(\000)p Fe(k)989 846 y Fn(\()p Fg(x)p Fn(\))p Fb(k)h(\024)h Fg(\017)1152 827 y Fe(?)1172 846 y Fb(k)p Fg(p)p Fn(\()p Fg(x)p Fn(\))p Fb(k)p Fg(;)-1316 b Fn(\(2\))0 928 y(where)15 b Fb(k)p Fg(q)r Fn(\()p Fg(x)p Fn(\))p Fb(k)f Fn(denotes)i(the)f(sum)g(of)g(the)g(mo)q(duli)i(of)e(the)g(co)q (e\016cien)o(ts)h(of)f(a)g(p)q(olynomial)i Fg(q)r Fn(.)0 1013 y Fm(Lemma)g(1.)23 b Fn([8)o(])16 b Fi(If)657 1054 y Fd(\015)657 1082 y(\015)657 1109 y(\015)657 1136 y(\015)657 1164 y(\015)682 1134 y Fg(p)p Fn(\()p Fg(x)p Fn(\))9 b Fb(\000)840 1077 y Fe(n)822 1091 y Fd(Y)822 1188 y Fe(i)p Fj(=1)887 1134 y Fn(\()p Fg(x)h Fb(\000)g Fg(z)1009 1115 y Fe(?)1007 1145 y(i)1029 1134 y Fn(\))1047 1054 y Fd(\015)1047 1082 y(\015)1047 1109 y(\015)1047 1136 y(\015)1047 1164 y(\015)1085 1134 y Fg(<)j(\017)p Fb(k)p Fg(p)p Fn(\()p Fg(x)p Fn(\))p Fb(k)p Fg(;)0 1257 y Fi(with)k Fb(\000)8 b Fn(log)200 1268 y Fj(2)228 1257 y Fg(\017)13 b Fb(\025)g Fg(bn)d Fn(+)g Fg(n)g Fn(+)h(2)p Fi(,)16 b(the)g(ine)n(qualities)j Fn(\(1\))c Fi(ar)n(e)i(satis\014e)n(d.)0 1342 y Fm(Lemma)g(2.)23 b Fn([8)o(])16 b Fi(L)n(et)f Fg(p)p Fn(\()p Fg(x)p Fn(\))p Fi(,)h Fg(f)528 1349 y Fj(1)548 1342 y Fn(\()p Fg(x)p Fn(\))p Fg(;)8 b(:)g(:)g(:)t(;)g(f)733 1349 y Fe(k)754 1342 y Fn(\()p Fg(x)p Fn(\))15 b Fi(and)i Fg(f)5 b Fn(\()p Fg(x)p Fn(\))p Fg(;)j(g)r Fn(\()p Fg(x)p Fn(\))13 b Fi(b)n(e)j(p)n(olynomials)f(such)i(that) 613 1445 y Fb(k)p Fg(p)p Fn(\()p Fg(x)p Fn(\))9 b Fb(\000)i Fg(f)798 1452 y Fj(1)818 1445 y Fn(\()p Fg(x)p Fn(\))d Fb(\001)g(\001)g(\001) t Fg(f)969 1452 y Fe(k)991 1445 y Fn(\()p Fg(x)p Fn(\))p Fb(k)k(\024)h Fg(\017)1160 1415 y(k)p 1159 1435 28 2 v 1159 1476 a(n)1191 1445 y Fb(k)p Fg(p)p Fn(\()p Fg(x)p Fn(\))p Fb(k)-1314 b Fn(\(3\))697 1528 y Fb(k)p Fg(f)742 1535 y Fj(1)762 1528 y Fn(\()p Fg(x)p Fn(\))10 b Fb(\000)g Fg(f)5 b Fn(\()p Fg(x)p Fn(\))p Fg(g)r Fn(\()p Fg(x)p Fn(\))p Fb(k)11 b(\024)i Fg(\017)1154 1535 y Fe(k)1175 1528 y Fb(k)p Fg(f)1220 1535 y Fj(1)1240 1528 y Fn(\()p Fg(x)p Fn(\))p Fb(k)p Fg(;)-1330 b Fn(\(4\))0 1608 y Fi(then)497 1700 y Fb(k)p Fg(p)p Fn(\()p Fg(x)p Fn(\))9 b Fb(\000)h Fg(f)5 b Fn(\()p Fg(x)p Fn(\))p Fg(g)r Fn(\()p Fg(x)p Fn(\))p Fg(f)856 1707 y Fj(2)874 1700 y Fn(\()p Fg(x)p Fn(\))j Fb(\001)g(\001)g(\001)d Fg(f)1026 1707 y Fe(k)1047 1700 y Fn(\()p Fg(x)p Fn(\))p Fb(k)12 b(\024)h Fg(\017)1215 1669 y(k)f Fn(+)e(1)p 1215 1689 104 2 v 1253 1731 a Fg(n)1324 1700 y Fb(k)p Fg(p)p Fn(\()p Fg(x)p Fn(\))p Fb(k)0 1793 y Fi(holds,)16 b(pr)n(ovide)n(d)760 1896 y Fg(\017)778 1903 y Fe(k)813 1896 y Fb(\024)d Fg(\017)963 1865 y Fb(k)p Fg(p)p Fn(\()p Fg(x)p Fn(\))p Fb(k)p 884 1886 288 2 v 884 1935 a Fg(n)919 1901 y Fd(Q)962 1914 y Fe(k)962 1948 y(i)p Fj(=1)1029 1935 y Fb(k)p Fg(f)1074 1942 y Fe(i)1088 1935 y Fn(\()p Fg(x)p Fn(\))p Fb(k)1177 1896 y Fg(:)50 2018 y Fn(F)l(rom)g(these)h(lemmas)g(follo)o(ws)g(that)g(it)g(is)g(su\016cien)o(t) h(to)e(compute)h(the)g(splitting)i(with)e Fg(\017)1583 2001 y Fe(?)1616 2018 y Fb(\024)f Fg(\017=)p Fn(\()p Fg(n)p Fn(2)1773 2001 y Fe(n)1796 2018 y Fn(\))h(in)g(\(2\))o(,)0 2072 y(where)h Fg(\017)h Fn(comes)f(from)g(Lemma)g(1.)50 2125 y(The)h(splitting)h(circle)g (metho)q(d)f(w)o(as)e(in)o(tro)q(duced)j(b)o(y)f(Sc)o(h\177)-23 b(onhage)16 b([8)o(,)f(9].)20 b(W)l(e)c(no)o(w)f(review)h(the)g(algorithms)0 2179 y(used)g(in)g(steps)f(1)g(and)g(2,)g(together)f(with)i(the)f(recen)o(t)g (progress)g(due)h(to)e(Victor)h(P)o(an.)668 2291 y(3.)26 b Fm(Numerical)18 b(F)l(actorization)50 2371 y Fn(T)l(o)i(simplify)i(the)e (notation,)h(assume)f(the)g(unit)h(circle)h(is)f(a)f(splitting)h(circle)h (for)e(the)g(p)q(olynomial)i Fg(p)p Fn(\()p Fg(x)p Fn(\).)0 2425 y(Let)16 b Fg(p)105 2432 y Fe(k)126 2425 y Fn(\()p Fg(x)p Fn(\))g(b)q(e)g(the)g(monic)h(p)q(olynomial)g(whose)f Fg(k)h Fn(ro)q(ots)e(are)h(those)g(ro)q(ots)f(of)g Fg(p)h Fn(lying)h(inside)h(the)e (circle.)24 b(The)0 2479 y(computation)c(of)f Fg(p)349 2486 y Fe(k)370 2479 y Fn(\()p Fg(x)p Fn(\))g(relies)i(on)f(the)g(follo)o(wing)g (in)o(tegral)g(represen)o(tation)g(of)f(the)h(p)q(o)o(w)o(er)g(sums)f Fg(s)1807 2486 y Fe(j)1845 2479 y Fn(of)h(its)0 2533 y(zeros:)719 2629 y Fg(s)740 2636 y Fe(j)771 2629 y Fn(=)846 2598 y(1)p 824 2618 66 2 v 824 2660 a(2)p Fg(i\031)902 2567 y Fd(Z)928 2670 y Fc(j)p Fe(z)q Fc(j)p Fj(=1)1025 2598 y Fg(p)1048 2582 y Fc(0)1059 2598 y Fn(\()p Fg(z)r Fn(\))p 1025 2618 94 2 v 1031 2660 a Fg(p)p Fn(\()p Fg(z)r Fn(\))1123 2629 y Fg(z)1146 2610 y Fe(j)1172 2629 y Fg(dz)r(:)p eop %%Page: 93 3 93 2 bop 1915 22 a Fj(93)0 120 y Fn(This)18 b(idea)h(originates)e(in)i([2)o (])e(and)h(w)o(as)f(re\014ned)i(b)o(y)e([8)o(])h(to)f(pro)q(duce)h(error)f(b) q(ounds,)i(i.e.,)f(to)f(b)q(ound)h Fg(Q)g Fn(suc)o(h)0 174 y(that)c(the)i Fg(s)198 181 y Fe(j)216 174 y Fn('s)f(can)g(b)q(e)h(computed)g (b)o(y)f(the)g(discretization)720 305 y Fg(s)741 286 y Fe(?)741 317 y(j)773 305 y Fn(=)833 275 y(1)p 826 295 36 2 v 826 336 a Fg(Q)875 246 y Fe(Q)p Fc(\000)p Fj(1)878 262 y Fd(X)880 359 y Fe(q)q Fj(=0)955 305 y Fg(!)985 286 y Fj(\()p Fe(i)p Fj(+1\))p Fe(q)1094 275 y Fg(p)1117 258 y Fc(0)1128 275 y Fn(\()p Fg(!)1176 258 y Fe(q)1195 275 y Fn(\))p 1094 295 119 2 v 1100 336 a Fg(p)p Fn(\()p Fg(!)1171 323 y Fe(q)1189 336 y Fn(\))1218 305 y Fg(:)0 436 y Fn(The)g(v)m(alue)i(of)e Fg(Q)g Fn(dep)q(ends)i(on)e(a)g(lo)o(w)o(er)f (b)q(ound)j(for)d Fb(j)p Fg(p)p Fn(\()p Fg(z)r Fn(\))p Fb(j)g Fn(on)h(the)h(unit)g(circle,)g(whic)o(h)g(in)g(turns)f(is)h(related)g(to)0 489 y(a)h(b)q(ound)h(on)e(the)h(distance)h(from)e(this)i(circle)g(to)f(the)g (closest)g(ro)q(ot)f(of)g Fg(p)p Fn(,)h(hence)h(the)f(need)h(for)e(a)h (circle)i(\\not)0 543 y(to)q(o)c(close")g(to)g(the)g(ro)q(ots)f(in)i(Step)g (1)f(of)f(the)i(algorithm.)50 597 y(E\016ciency)h(is)g(attained)g(at)e(the)i (price)g(of)f(quite)h(tec)o(hnical)g(dev)o(elopmen)o(ts)g([8].)22 b(If)17 b(the)f(closest)h(ro)q(ot)e(to)h(the)0 651 y(circle)21 b(is)f(at)f(distance)h Fg(O)q Fn(\(1)p Fg(=n)p Fn(\),)f(a)g(v)m(alue)h(of)f Fg(Q)h Fn(of)f(order)g Fg(O)q Fn(\()p Fg(n)1126 635 y Fj(2)1145 651 y Fn(\))g(is)h(used)1320 635 y Fj(1)1360 651 y Fn(and)f(the)h(corresp)q (onding)g Fg(p)1854 635 y Fc(0)1866 651 y Fn(\()p Fg(!)1914 635 y Fe(q)1932 651 y Fn(\))0 705 y(and)15 b Fg(p)p Fn(\()p Fg(!)159 689 y Fe(q)177 705 y Fn(\))f(are)g(computed)h(b)o(y)f(a)g(discrete)h (F)l(ourier)g(transform.)j(F)l(rom)c(there,)g(the)g(sums)g Fg(s)1599 689 y Fe(?)1599 718 y(j)1634 705 y Fn(for)f Fg(j)i Fn(=)e(0)p Fg(;)8 b(:)g(:)g(:)d(;)j(K)0 760 y Fn(are)15 b(computed)i(b)o(y)e (DFT,)g Fg(K)k Fn(b)q(eing)e(the)f(smallest)g(p)q(o)o(w)o(er)f(of)h(2)f (larger)h(than)f Fg(k)g Fn(=)f Fg(s)1480 767 y Fj(0)1500 760 y Fn(.)22 b(An)16 b(appro)o(ximation)f(of)0 814 y(the)j(factor)f Fg(p)237 821 y Fe(k)259 814 y Fn(\()p Fg(x)p Fn(\))g(can)h(then)h(b)q(e)f (reco)o(v)o(ered)g(e\016cien)o(tly)i(b)o(y)e(a)g(v)m(arian)o(t)g(of)g (Newton-Hensel's)g(lifting)i(\(see)e([1)o(,)0 868 y(p.)11 b(34]\).)18 b(Then)12 b(the)g(other)f(factor)g(is)h(obtained)g(b)o(y)g(division.)21 b(In)12 b(order)f(to)g(reac)o(h)h(the)g(righ)o(t)f(lev)o(el)i(of)e(complexit) o(y)l(,)0 922 y(it)h(is)g(necessary)g(to)g(compute)g(only)g Fg(O)q Fn(\()p Fg(n)p Fn(\))f(bits)h(for)g(these)g(steps)f(and)h(then)h (re\014ne)f(the)g(factorization)g(b)o(y)f(another)0 976 y(Newton)k(lik)o(e)h (algorithm)f(as)g(follo)o(ws.)20 b(Starting)15 b(from)g(the)g(appro)o(ximate) g(factorization)694 1065 y Fb(k)p Fg(p)p Fn(\()p Fg(x)p Fn(\))9 b Fb(\000)h Fg(p)879 1041 y Fj(\(0\))879 1080 y Fe(k)926 1065 y Fn(\()p Fg(x)p Fn(\))p Fg(p)1011 1041 y Fj(\(0\))1011 1080 y Fe(n)p Fc(\000)p Fe(k)1081 1065 y Fn(\()p Fg(x)p Fn(\))p Fb(k)h(\024)i Fg(\017;)0 1163 y Fn(where)21 b Fg(p)160 1139 y Fj(\(0\))160 1178 y Fe(k)227 1163 y Fn(has)f(degree)h Fg(k)q Fn(,)h(the)e(aim)h(is)g(to)e(\014nd)i(a)g(re\014nemen)o(t)f Fg(p)1199 1139 y Fj(\(1\))1199 1178 y Fe(k)1268 1163 y Fn(=)h Fg(p)1347 1139 y Fj(\(0\))1347 1178 y Fe(k)1408 1163 y Fn(+)14 b Fg(q)1477 1170 y Fe(k)1499 1163 y Fn(,)21 b Fg(p)1556 1139 y Fj(\(1\))1556 1178 y Fe(n)p Fc(\000)p Fe(k)1647 1163 y Fn(=)h Fg(p)1727 1139 y Fj(\(0\))1727 1178 y Fe(n)p Fc(\000)p Fe(k)1811 1163 y Fn(+)14 b Fg(q)1880 1170 y Fe(n)p Fc(\000)p Fe(k)0 1217 y Fn(with)i(deg)8 b Fg(q)200 1224 y Fe(i)227 1217 y Fg(<)13 b(i)p Fn(,)h(impro)o(ving)i(the)f(error.)20 b(Since)351 1306 y Fg(p)10 b Fb(\000)h Fg(p)453 1282 y Fj(\(1\))453 1321 y Fe(k)500 1306 y Fg(p)523 1282 y Fj(\(1\))523 1321 y Fe(n)p Fc(\000)p Fe(k)605 1306 y Fn(=)i(\()p Fg(p)d Fb(\000)g Fg(p)772 1282 y Fj(\(0\))772 1321 y Fe(k)819 1306 y Fg(p)842 1282 y Fj(\(0\))842 1321 y Fe(n)p Fc(\000)p Fe(k)913 1306 y Fn(\))f Fb(\000)i Fg(p)1009 1282 y Fj(\(1\))1009 1321 y Fe(k)1056 1306 y Fg(p)1079 1282 y Fj(\(0\))1079 1321 y Fe(n)p Fc(\000)p Fe(k)1159 1306 y Fb(\000)f Fg(p)1227 1282 y Fj(\(0\))1227 1321 y Fe(k)1274 1306 y Fg(p)1297 1282 y Fj(\(1\))1297 1321 y Fe(n)p Fc(\000)p Fe(k)1378 1306 y Fb(\000)g Fg(p)1446 1282 y Fj(\(1\))1446 1321 y Fe(k)1493 1306 y Fg(p)1516 1282 y Fj(\(1\))1516 1321 y Fe(n)p Fc(\000)p Fe(k)1586 1306 y Fg(;)0 1387 y Fn(the)15 b(Newton)g(iteration)h(is)f (obtained)h(b)o(y)f(satisfying)605 1476 y(\()p Fg(p)10 b Fb(\000)g Fg(p)724 1452 y Fj(\(0\))724 1490 y Fe(k)771 1476 y Fg(p)794 1452 y Fj(\(0\))794 1490 y Fe(n)p Fc(\000)p Fe(k)864 1476 y Fn(\))j(=)g Fg(p)966 1452 y Fj(\(1\))966 1490 y Fe(k)1013 1476 y Fg(p)1036 1452 y Fj(\(0\))1036 1490 y Fe(n)p Fc(\000)p Fe(k)1116 1476 y Fn(+)d Fg(p)1184 1452 y Fj(\(0\))1184 1490 y Fe(k)1231 1476 y Fg(p)1254 1452 y Fj(\(1\))1254 1490 y Fe(n)p Fc(\000)p Fe(k)1324 1476 y Fg(;)-1337 b Fn(\(5\))0 1574 y(whic)o(h)14 b(determines)g Fg(p)379 1550 y Fj(\(1\))379 1589 y Fe(k)439 1574 y Fn(and)f Fg(p)548 1550 y Fj(\(1\))548 1589 y Fe(n)p Fc(\000)p Fe(k)632 1574 y Fn(uniquely)l(.)21 b(These)14 b(p)q(olynomials)g (could)g(b)q(e)g(found)g(b)o(y)f(Euclid's)h(algorithm,)0 1645 y(but)21 b(this)f(is)h(to)q(o)f(exp)q(ensiv)o(e.)37 b(Instead,)22 b(one)e(also)g(computes)h(an)f(in)o(v)o(erse)h Fg(q)1374 1629 y Fj(\()p Fe(i)p Fj(\))1436 1645 y Fn(of)f Fg(p)1516 1621 y Fj(\()p Fe(i)p Fj(\))1516 1660 y Fe(n)p Fc(\000)p Fe(k)1606 1645 y Fn(mo)q(dulo)h Fg(p)1797 1621 y Fj(\()p Fe(i)p Fj(\))1797 1660 y Fe(k)1859 1645 y Fn(b)o(y)f(a)0 1716 y(second,)e(parallel,)h(Newton)e (iteration)h(and)f(then)h Fg(p)915 1692 y Fj(\()p Fe(i)p Fj(\))915 1731 y Fe(k)974 1716 y Fn(is)g(giv)o(en)g(b)o(y)f Fg(q)1230 1700 y Fj(\()p Fe(i)p Fj(\))1271 1716 y Fg(p)g Fn(=)f Fg(q)1384 1700 y Fj(\()p Fe(i)p Fj(\))1426 1716 y Fn(\()p Fg(p)11 b Fb(\000)h Fg(p)1548 1692 y Fj(\()p Fe(i)p Fj(\))1548 1731 y Fe(k)1589 1716 y Fg(p)1612 1692 y Fj(\()p Fe(i)p Fj(\))1612 1731 y Fe(n)p Fc(\000)p Fe(k)1682 1716 y Fn(\))g(mo)q(d)h Fg(p)1835 1692 y Fj(\()p Fe(i)p Fj(\))1835 1731 y Fe(k)1877 1716 y Fn(.)26 b(A)0 1788 y(similar)17 b(form)o(ula)f(giv)o(es)g Fg(p)453 1764 y Fj(\()p Fe(i)p Fj(\))453 1802 y Fe(n)p Fc(\000)p Fe(k)523 1788 y Fn(.)22 b(Then)17 b(the)f(required)h(precision)h(is)e(obtained)h (after)e(a)h(few)g(iteration)g(at)g(a)f(cost)0 1844 y(b)q(ounded)i(b)o(y)e Fg(O)q Fn(\()p Fg(n)8 b Fn(log)f Fg(\017)421 1827 y Fe(?)442 1844 y Fn(\).)662 1959 y(4.)26 b Fm(Finding)19 b(Splitting)g(Circles)50 2040 y Fn(The)g(basic)h(tec)o(hnique)h(to)d(\014nd)i(discs)g(con)o(taining)g (a)f(kno)o(wn)g(n)o(um)o(b)q(er)h(of)e(ro)q(ots)h(of)f(a)h(p)q(olynomial)i (is)f(the)0 2094 y(iteration)c(of)f(Grae\013e's)g(metho)q(d)h(\(see)f([3]\).) 21 b(Starting)15 b(from)g Fg(p)p Fn(\()p Fg(x)p Fn(\))g(of)g(degree)h Fg(n)p Fn(,)g(one)g(p)q(erforms)f(the)h(follo)o(wing)0 2148 y(iteration:)682 2229 y Fg(p)705 2236 y Fe(i)p Fj(+1)764 2229 y Fn(\()p Fg(x)808 2210 y Fj(2)828 2229 y Fn(\))c(=)h(\()p Fb(\000)p Fn(1\))1000 2210 y Fe(n)1023 2229 y Fg(p)1046 2236 y Fe(i)1060 2229 y Fn(\()p Fg(x)p Fn(\))p Fg(p)1145 2236 y Fe(i)1158 2229 y Fn(\()p Fb(\000)p Fg(x)p Fn(\))p Fg(;)0 2310 y Fn(whic)o(h)h(transforms)d(the)i(p)q(olynomial)h Fg(p)683 2317 y Fe(i)697 2310 y Fn(\()p Fg(x)p Fn(\))e(in)o(to)h(a)g(p)q(olynomial)h Fg(p)1152 2317 y Fe(i)p Fj(+1)1211 2310 y Fn(\()p Fg(x)p Fn(\))e(whose)h(ro)q (ots)f(are)g(the)h(squares)g(of)f(the)0 2364 y(ro)q(ots)f(of)g Fg(p)183 2371 y Fe(i)197 2364 y Fn(\()p Fg(x)p Fn(\).)18 b(This)12 b(pro)q(cess)g(emphasizes)h(the)f(di\013erences)g(of)g(mo)q(duli)h(b)q(et)o (w)o(een)f(the)f(ro)q(ots.)18 b(The)12 b(co)q(e\016cien)o(ts)0 2418 y(of)18 b(these)i(iterates)e(are)h(Newton)f(sums)h(from)f(whic)o(h)i (precise)g(information)f(ab)q(out)g(the)g(di\013eren)o(t)g(mo)q(duli)h(of)0 2472 y(the)d(ro)q(ots)g(of)g(the)g(original)i(p)q(olynomial)g(can)e(b)q(e)h (reco)o(v)o(ered)f(at)g(a)g(lo)o(w)g(cost.)26 b(More)17 b(precisely)l(,)j (one)d(gets)g(the)0 2526 y(follo)o(wing)f(lemma.)p 0 2583 250 2 v 50 2613 a Fh(1)67 2629 y Fp(More)d(precise)i(v)n(alues)f(are)f(giv)o(en)h (in)g([8,)e(p.)h(35].)p eop %%Page: 94 4 94 3 bop 0 22 a Fj(94)0 120 y Fm(Lemma)17 b(3.)23 b Fi(L)n(et)e Fg(z)354 127 y Fj(1)373 120 y Fg(;)8 b(:)g(:)g(:)d(;)j(z)496 127 y Fe(n)541 120 y Fi(b)n(e)21 b(the)h(r)n(o)n(ots)f(of)h Fg(p)p Fn(\()p Fg(x)p Fn(\))p Fi(,)g(satisfying)e Fb(j)p Fg(z)1220 127 y Fj(1)1240 120 y Fb(j)i(\024)h(\001)8 b(\001)g(\001)20 b(\024)j(j)p Fg(z)1500 127 y Fe(n)1523 120 y Fb(j)f(\024)h Fn(1)p Fi(.)36 b(Given)22 b Fg(c)g(>)g Fn(0)0 175 y Fi(and)e Fg(d)g Fb(\025)h Fn(0)p Fi(,)g(it)g(is)e(p)n(ossible)h(to)g(c)n(ompute)h Fg(r)p 763 182 22 2 v 785 187 a Fj(1)805 175 y Fg(;)p 826 150 V 8 w(r)847 182 y Fj(1)867 175 y Fg(;)8 b(:)g(:)g(:)t(;)g(r)p 968 182 V 12 x Fe(n)1013 175 y Fg(;)p 1034 150 V 8 w(r)1055 182 y Fe(n)1099 175 y Fi(such)20 b(that)h Fg(r)p 1303 182 V 1325 187 a Fe(k)1367 175 y Fb(\024)f(j)p Fg(z)1456 182 y Fe(k)1477 175 y Fb(j)g(\024)p 1566 150 V 21 w Fg(r)1588 182 y Fe(k)1629 175 y Fn(=)h(\(1)12 b(+)i Fg(c=n)1857 159 y Fe(d)1877 175 y Fn(\))p Fg(r)1916 182 y Fe(k)1936 175 y Fi(,)0 233 y Fg(k)g Fn(=)f(1)p Fg(;)8 b(:)g(:)g(:)t(;)g(n)16 b Fi(with)362 221 y Fn(~)352 233 y Fg(O)q Fn(\()p Fg(n)p Fn(\))g Fi(arithmetic)h(op)n(er)n (ations.)50 314 y Fn(This)e(iteration)f(is)h(applied)i(after)c(ha)o(ving)i (\014rst)f(shifted)h(the)g(origin)g(to)f(the)g(cen)o(ter)g(of)g(gra)o(vit)o (y)g(of)g(the)g(ro)q(ots,)0 368 y(whic)o(h)f(is)f(giv)o(en)g(b)o(y)g(the)g (\014rst)g(t)o(w)o(o)e(co)q(e\016cien)o(ts)j(of)e(the)h(p)q(olynomial.)20 b(When)13 b(it)f(follo)o(ws)g(from)f(this)h(computation)0 422 y(that)f(there)g(is)h(a)f Fg(k)j Fn(=)f Fg(\013n)p Fn(,)f Fg(\013)g Fn(in)g(a)f(\014xed)h(in)o(terv)m(al)h(\()p Fg(\032;)8 b Fn(1)s Fb(\000)s Fg(\032)p Fn(\),)h(with)i(some)g Fg(\032)i(<)g Fn(1)e(suc)o(h)g (that)g Fb(j)p Fg(z)1587 429 y Fe(k)q Fj(+1)1653 422 y Fb(j)p Fg(=)p Fb(j)p Fg(z)1723 429 y Fe(k)1744 422 y Fb(j)h(\025)h Fn(1)s(+)s Fg(c=n)0 476 y Fn(for)k(some)h Fg(c)g Fn(\014xed)g(in)h(adv)m (ance,)g(then)f(this)h(yields)g(a)f(splitting)h(circle)h(and)e(the)g (factoring)f(algorithm)h(of)g(the)0 530 y(previous)e(section)g(can)f(b)q(e)h (applied.)50 584 y(It)g(is)h(when)f(no)h(suc)o(h)f(circle)i(can)e(b)q(e)h (found)g(that)e(progress)h(has)g(b)q(een)h(made)f(b)o(y)g(Victor)h(P)o(an)f (recen)o(tly)l(.)23 b(In)0 638 y(this)c(case,)g(there)g(is)g(an)f(ann)o(ulus) i(cen)o(tered)f(at)f(0)g(whic)o(h)h(con)o(tains)g(most)f(of)g(the)g(ro)q(ots) g(of)g(the)h(p)q(olynomial.)0 692 y(No)o(w)e(the)h(idea)g(is)g(to)f(shift)h (the)g(origin)g(to)f(eac)o(h)h(of)f Fg(r)947 675 y Fc(0)975 692 y Fn(=)g(2)p 1050 666 V Fg(r)1072 701 y Fj(11)p Fe(n=)p Fj(12)1201 692 y Fn(and)h Fg(ir)1330 675 y Fc(0)1341 692 y Fn(,)g(and)g(apply)g(the)g(same)f(metho)q(d.)0 745 y(Then)e(either)h(a)e(go)q (o)q(d)h(splitting)h(circle)g(is)g(found,)e(or)h(there)f(is)i(a)e(small)i (circle)g(whic)o(h)g(is)f(easily)h(computed)f(and)0 799 y(con)o(tains)j(the)f (in)o(tersection)i(of)e(these)h(three)g(ann)o(uli,)h(itself)g(con)o(taining)f (an)g(imp)q(ortan)o(t)f(cluster)h(of)f(zeros)h(\(at)0 853 y(least)13 b(half)g(of)g(the)g(zeros)f(of)h Fg(p)g Fn(if)g Fg(c)f Fn(=)h(1)p Fg(=)p Fn(100\).)18 b(In)13 b(this)g(case,)g(the)g(idea)h(is)f(that)g(one)g (of)f(the)h(zeros)g(of)f(a)h(deriv)m(ativ)o(e)0 910 y(of)19 b Fg(p)g Fn(of)g(high)h(order)f(\(for)f(instance,)j(one)f(can)f(tak)o(e)g Fg(p)969 894 y Fj(\()p Fc(b)p Fe(n=)p Fj(2)p Fc(c)p Fj(+1\))1131 910 y Fn(\))g(is)h(either)g(the)f(cen)o(ter)h(of)e(a)h(go)q(o)q(d)h (splitting)0 964 y(circle)e(or)e(mak)o(es)f(it)i(p)q(ossible)h(to)d(isolate)i (a)f Fi(massive)g(cluster)21 b Fn(of)16 b(zeros,)g(where)g(more)g(than)g (half)h(of)f(the)g(zeros)0 1018 y(of)f Fg(p)g Fn(are)g(at)g(distance)h(less)g (than)f(the)h(desired)g(accuracy)g(2)1034 1002 y Fc(\000)p Fe(b)1078 1018 y Fn(.)k(In)c(b)q(oth)g(cases,)f(the)g(p)q(olynomial)i(can)f (then)f(b)q(e)0 1072 y(factored)i(n)o(umerically)i(and)e(the)h(computation)f (pro)q(ceeds)h(on)f(those)g(factors)f(that)h(do)g(not)g(corresp)q(ond)h(to)e (a)0 1126 y(massiv)o(e)e(cluster.)20 b(Man)o(y)13 b(re\014nemen)o(ts)h(are)g (giv)o(en)g(in)g([5],)f(in)i(particular)f(it)g(is)g(sho)o(wn)g(that)f(it)h (is)g(not)g(necessary)0 1183 y(to)h(compute)g(all)h(the)f(zeros)g(of)g Fg(p)570 1167 y Fj(\()p Fc(b)p Fe(n=)p Fj(2)p Fc(c)p Fj(+1\))733 1183 y Fn(.)850 1275 y Fm(Conclusion)50 1356 y Fn(This)c(summary)e(is)i(a)f (v)o(ery)g(rough)g(sk)o(etc)o(h)g(of)g(a)g(v)o(ery)g(detailed)i(study)e(giv)o (en)h(in)g([5].)18 b(F)l(or)9 b(practical)i(p)q(olynomial)0 1410 y(solving,)17 b(other)g(algorithms)f(are)g(kno)o(wn)h(to)f(p)q(erform)g (extremely)h(w)o(ell,)h(but)e(their)h(complexit)o(y)h(analysis)f(has)0 1464 y(y)o(et)e(to)f(b)q(e)i(done.)50 1518 y(The)f(talk)g(also)h(men)o (tioned)g(extensions)f(to)g(the)g(m)o(ultiv)m(ariate)h(case,)f(this)h(is)g (describ)q(ed)h(in)f([4)o(].)841 1605 y Fk(Bibliograp)o(h)o(y)0 1678 y Fp([1])j(Bini)g(\(Dario\))g(and)f(P)o(an)g(\(Victor)g(Y.\).)f({)h Fl(Polynomial)d(and)i(matrix)h(c)n(omputation)o(s.)d(Vol.)i(1)p Fp(.)f({)i(Birkh\177)-19 b(auser)20 b(Boston)e(Inc.,)60 1724 y(Boston,)13 b(MA,)g Fa(1994)p Fp(,)g Fl(Pr)n(o)n(gr)n(ess)f(in)h(The)n(or)n (etic)n(al)f(Computer)h(Scienc)n(e)p Fp(,)d(xvi+415p.)k(F)m(undamen)o(tal)h (algorithms.)0 1769 y([2])k(Delv)o(es)10 b(\(L.)e(M.\))h(and)g(Lyness)h(\(J.) e(N.\).)g({)h(A)f(n)o(umerical)j(metho)q(d)f(for)f(lo)q(cating)i(the)e(zeros) g(of)g(an)g(analytic)i(function.)f Fl(Mathematics)60 1815 y(of)j(Computation) p Fp(,)d(v)o(ol.)j(21,)g Fa(1967)q Fp(,)g(pp.)g(543{560.)0 1861 y([3])19 b(Henrici)c(\(P)o(eter\).)f({)g Fl(Applie)n(d)e(and)h(c)n (omputational)e(c)n(omplex)i(analysis)p Fp(.)e({)j(Wiley-In)o(terscienc)q(e,) i(New)e(Y)m(ork,)g Fa(1974)p Fp(,)g Fl(Pur)n(e)g(and)60 1906 y(Applie)n(d)d(Mathematics)p Fp(,)f(v)o(ol.)k(V)m(olume)f(1:)k(P)o(o)o(w)o (er)c(series,)h(in)o(tegration,)h(conformal)f(mapping,)g(lo)q(cation)i(of)c (zeros,)h(xv+682p.)0 1952 y([4])19 b(Mourrain)c(\(Bernard\))g(and)f(P)o(an)h (\(Victor)f(Y.\).)e({)i(Asymptotic)h(acceleration)h(of)e(solving)i(m)o(ultiv) n(ariate)g(p)q(olynomial)h(systems)60 1998 y(of)d(equations.)i(In)e Fl(Pr)n(o)n(c)n(e)n(e)n(dings)e(of)i(the)g(Thirtieth)g(A)o(nnual)e(A)o(CM)k (Symp)n(osium)d(on)h(The)n(ory)g(of)g(Computing)p Fp(.)e(pp.)j(488{496.)g({) 60 2043 y(A)o(CM)d(Press,)h Fa(1998)q Fp(.)0 2089 y([5])19 b(P)o(an)13 b(\(V.)g(Y.\).)f({)h(Optimal)i(and)f(nearly)g(optimal)h (algorithms)h(for)d(appro)o(ximating)j(p)q(olynomial)h(zeros.)c Fl(Computers)g(&)h(Math-)60 2135 y(ematics)e(with)h(Applic)n(ation)o(s)p Fp(,)d(v)o(ol.)j(31,)g(n)658 2138 y(\027)687 2135 y(12,)g Fa(1996)q Fp(,)g(pp.)g(97{138.)0 2180 y([6])19 b(P)o(an)13 b(\(Victor\).)g({)g(Solving) j(p)q(olynomials)g(with)e(computers.)f Fl(A)o(meric)n(an)f(Scientist)p Fp(,)e(v)o(ol.)j(86,)g Fa(1998)q Fp(,)f(pp.)i(62{69.)0 2226 y([7])19 b(P)o(an)13 b(\(Victor)f(Y.\).)g({)g(Optimal)i(\(up)f(to)f(p)q (olylog)j(factors\))e(sequen)o(tial)i(and)e(parallel)i(algorithms)g(for)d (appro)o(ximating)j(complex)60 2272 y(p)q(olynomial)h(zeros.)d(In)g Fl(SIAM)g(Journal)f(on)h(Computing)p Fp(.)e(pp.)i(741{750.)h({)f(A)o(CM)f (Press,)h Fa(1995)q Fp(.)0 2317 y([8])19 b(Sc)o(h\177)-19 b(onhage)18 b(\(Arnold\).)f({)g Fl(The)f(fundamental)e(the)n(or)n(em)i(of)g(algebr)n(a)g (in)g(terms)g(of)h(c)n(omputationa)o(l)d(c)n(omplexity)p Fp(.)g({)i(T)m(ec)o (hnical)60 2363 y(rep)q(ort,)d(Mathematisc)o(hes)i(Institut)f(der)f(Univ)o (ersit\177)-19 b(at)15 b(T)q(\177)-20 b(ubingen,)14 b Fa(1982)q Fp(.)f(Preliminary)i(rep)q(ort.)0 2408 y([9])k(Sc)o(h\177)-19 b(onhage)12 b(\(Arnold\).)g({)f(Equation)i(solving)g(in)f(terms)f(of)f (computational)k(complexit)o(y)m(.)f(In)e Fl(Pr)n(o)n(c)n(e)n(e)n(dings)e(of) i(the)g(Internationa)o(l)60 2454 y(Congr)n(ess)h(of)h(Mathematicians)p Fp(,)c(pp.)k(131{153.)h({)f Fa(1987)q Fp(.)f(Berk)o(eley)m(,)i(California,)h (1986.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF