On computations of Hurwitz-Hodge integrals

Fourteen Easy Lessons in Density Functional TheoryJOHN P.PERDEW,ADRIENN RUZSINSZKYDepartment of Physics and Quantum Theory Group,Tulane University,New Orleans,LA70118Received1April2010;accepted5May2010Published online in Wiley InterScience().DOI10.1002/qua.22829ABSTRACT:Density functional theory(DFT)is now the most commonly usedmethod of electronic structure calculation in both condensed matter physics andquantum chemistry,thanks in part to the focus it has received over the first50years ofthe Sanibel Symposium.We present a short history,and review fourteen short and easybut important lessons about nonrelativistic DFT,with some partiality but with aminimum of technical complication.V C2010Wiley Periodicals,Inc.Int J Quantum Chem000:000–000,2010Key words:density functional theory;exchange–correlation energy;electronicstructure theory;Kohn–Sham theoryIntroduction and Short History of Density Functional TheoryT his article summarizes a talk given at the 50th anniversary Sanibel Symposium on Quantum Chemistry.Its original title,‘‘Some Things We have Learned About Exchange and Correlation in the Last Fifty Years,’’was some-what too restrictive in both subject matter and time frame.It presents14easy lessons in nonrela-tivistic density functional theory(DFT)at a quali-tative level.The selection of lessons is partial in both senses of the word:it is incomplete,and it reflects our own biases about what is most impor-tant and interesting(or at least most familiar). The same can be said of the short history we present.Our subject is appropriate to the occa-sion,since the Sanibel Symposium has played a major role in the development of modern elec-tronic structure theory,including but not limited to DFT.Possible companion pieces to this article are our short discussion[1]of‘‘perplexing’’issues in DFT and a detailed review[2]of the exact theory and its approximations.Often we need to predict the ground-state properties of an atom,molecule,solid,nanostruc-ture,or other system.We might need the equilib-rium geometry or structure,vibrational frequen-cies,electron density,total energy,and various total energy differences such as atomization and surface energies,as well as the linear and nonlin-ear responses to external static probes.One way to find the needed properties is to solve theCorrespondence to:J.P.Perdew;e-mail:*****************Contract grant sponsor:National Science Foundation.Contract grant number:DMR-0854769.International Journal of Quantum Chemistry,Vol.000,000–000(2010) V C2010Wiley Periodicals,Inc.N -electron Schroedinger equation for the N -elec-tron ground-state wavefunction.This approach is potentially accurate and complete (providing all the information that can be known),but it is com-putationally inefficient and impractical for large N .A second way is to solve for more limited in-formation,as provided by a Green’s function,density matrix,or electron density.This approach may be less accurate and complete,but it can achieve a useful computational efficiency even for large N .Kohn–Sham DFT [2,3]uses spin orbitals to predict the ground-state electron density,total energy,and related important properties.It pro-vides an often useful and improvable compromise between accuracy and computational efficiency.Thus,it is now the most widely used method of electronic structure calculation in both condensed matter physics and quantum chemistry,two sub-jects that have long been intertwined at the Sani-bel Symposia.However,other methods [4],including full wavefunction methods,continue to improve in accuracy and efficiency,providing for selected systems a benchmark of accuracy.Orbital-free DFT began in the 1920s with the Thomas–Fermi theory [5,6],which expresses the total energy E approximately in terms of the elec-tron density n ð~r Þ,where n ð~r Þd 3r is the average number of electrons in volume element d 3r at position ~r ,using the simplest density functional that makes sense.The density is then varied atfixed electron number N ¼R d 3rn ð~r Þto minimize the energy functional.This approach gives simple and useful estimates for the density and total energy of an atom (defined as minus the mini-mum work to strip all the electrons from the nu-cleus)but it is far too crude for chemistry.In fact,Teller [7]proved that in Thomas–Fermi theory,atoms do not bind together to form molecules and solids.Without the exchange–correlation energy,‘‘nature’s glue’’[8],chemical bonds are ei-ther absent or far too long and weak.However,orbital-free methods continue to improve;see recent work by Trickey and others [9–11].Spin orbitals or fictitious one-electron wave-functions w i ð~r ;r Þwere introduced in the 1930s by Hartree,Fock,and Slater [12].The energy (includ-ing sometimes exchange but not Coulomb correla-tion)was expressed in terms of these orbitals and their occupation numbers f i (1or 0,since electrons are fermions),and minimized with respect to them.This approach binds atoms into molecules and solids,although usually too weakly [8],andgenerally improves the total energy E and elec-tron density n ð~r Þ¼P i r f i r w i r ð~r Þj j 2over orbital-free methods.The Hartree and Hartree-Fock methods were not easy to implement on early computers and omitted important correlation effects.In the 1950s,Slater combined the orbital and density functional approaches by creating a local density approxima-tion (LDA)for the exchange–correlation energy and potential (which he called the X a approxima-tion [12]).He found that it could be easily imple-mented self-consistently on the computer and that it included a rough but useful estimate of correla-tion.After retiring from MIT in 1966,Slater joined the Quantum Theory Project at the University of Florida,Gainesville,which held the first Sanibel Symposium in 1961.In 1964–1965,the Hohenberg–Kohn [13]and Kohn–Sham [3]theorems,the twin pillars of mod-ern DFT,were published.These theorems showed that,given the right density functionals,one can find the exact ground-state density and energy of an N -electron system in an external scalar poten-tial using either the total density or the orbitals as variational objects.Kohn and Sham also proposed an LDA for the exchange–correlation energy,which,unlike Slater’s,is exact for an electron gas of uniform or slowly varying density.Kohn–Sham theory was not widely known until around 1970,when condensed matter physi-cists started to find that this theory in the LDA gives a remarkably realistic description of bulk solids and their surfaces.Since then,DFT has dominated electronic structure calculations for solids.For the surface energy [14,15]of a solid,density functionals proved to be more accurate than early correlated wavefunction calculations.The densities of many solids,especially simple metals,are sufficiently like those of uniform elec-tron gases for the LDA to work well.However,it did not work so well for atoms and molecules.In particular,the atomization energies of molecules were strongly overestimated (although they were still better than those of Hartree-Fock theory).In the period 1970–1986,DFT in chemistry had only a few prophets,including notably Parr [16],Jones and Gunnarsson [17],and Levy [18].This was however a time when theoretical work by Langreth and Per-dew [19,20],and by Gunnarsson and Lundqvist [21],explained why the local approximation worked as well as it did and suggested approaches to improve it.The new approaches included generalized gradient approximations and hybridPERDEW AND RUZSINSZKY2INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY DOI 10.1002/qua VOL.000,NO.000functionals,which greatly increased the accuracy of atomization energies and thus the relevance of the theory to chemistry.Since about1992,DFT has swept chemistry,as it earlier swept condensed matter physics.This development was led notably by Becke[22],who proposed many creative approaches to functional construction,and by John Pople and Nick Handy.Since the1920s,many important lessons have been learned about DFT.We summarize14of these lessons below.Lesson1:Density vs.Correlated WavefunctionThe electron density nð~rÞhas a lower dimen-sionality than the N-electron wavefunction Wð~r1;r1;…;~r N;r NÞ.Using n instead of W as thebasic variational object makes electronic structure calculations much faster but typically much less accurate.This lesson comes from Thomas[5]and Fermi [6].In his lecture for the1998Nobel Prize in Chemistry[23],Walter Kohn explained this fact in a clear if oversimplified way,which we para-phrase here:suppose we use a mesh of points in real space,with10points along each of the x,y, and z axes.Then we can compute and store the density on the mesh as103numbers.A one-elec-tron wavefunction can also be represented by 103numbers,but a10-electron correlated wave-function must be represented by(103)10¼1030 numbers.There are of course cleverer ways[4] to compute a10-electron wavefunction,but the fact remains that the effort to compute an N-electron wavefunction scales up very rapidly with N.Lesson2:Orbitals vs.Correlated WavefunctionWhile too much accuracy can be lost by using the density nð~rÞas the basic variational object, considerable accuracy can be restored by using also the occupied orbitals or fictitious one-electron wavefunctions w1ð~r;rÞ…w Nð~r;rÞ.This lesson comes from Hartree and Fock in the1920s and from Slater in the1950s[12].In our example from Lesson1,an orbital description of the10-electron system requires computing and storing only10Â103¼104numbers.Lesson3:Something Proved to Exist That Cannot be FoundIn principle,we can find the exact ground-state energy and density of N electrons in an external potential vð~rÞa.by solving an Euler equation for the densitynð~rÞas proved by Hohenberg and Kohn[13],orb.by solving self-consistent one-electronSchroedinger equations for the orbitals asproved by Kohn and Sham[3].In approach(b),the functional derivative d E xc=d nð~rÞserves as the exchange–correlation contribu-tion v xcð~rÞto the effective one-electron orKohn–Sham potential v KSð~rÞ.In practice,the exact density functional E v[n] for the total energy needed for approach(a),and the exact density functional E xc[n]for the exchange–correlation energy needed for approach (b),are not accessible in any practical way and must be approximated.Although the Hohenberg–Kohn–Sham theo-rems are only existence theorems,the knowledge that exact density functionals exist has strongly driven the quest for better and more accurate approximations.Lesson4:From Uniform ElectronGas to Atoms,Molecules,and SolidsThe local density approximation(LDA)E LDAxc½n ¼Zd3rnð~rÞe unifxcðnð~rÞÞ;(1)or better the local spin density approximation (LSDA)E LSDAxc½n";n# ¼Zd3rnð~rÞe unifxcðn"ð rÞ;n#ð~rÞÞ;(2)which start from e unifxc,the exchange–correlation energy per particle of a uniform electron gas,areFOURTEEN EASY LESSONS IN DENSITY FUNCTIONAL THEORY VOL.000,NO.000DOI10.1002/qua INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY3accurate enough for useful calculations on solids and solid surfaces but not accurate enough for atoms and molecules.LDA comes from Kohn and Sham[3]and LSDA from von Barth and Hedin[24].The accu-racy of these local approximations for solids and surfaces was established by Lang and Kohn[25] and by Moruzzi et al.[26].Jones and Gunnarsson [17]found good structures but overestimated atomization energies for molecules.For open-shell or magnetic systems,in the ab-sence of an external magnetic field,one can use either the total density or the separate spin den-sities in principle,but in practice LSDA is more accurate than LDA because it inputs more infor-mation about the system[27].This was the first indication of a possible ladder of density func-tional approximations for the exchange–correla-tion energy to be discussed in Lessons9and10 below.All rungs of the ladder are actually imple-mented on the spin densities,but we will use the total density below to simplify the notation. Lesson5:The Electron Digs a HoleThe exact exchange–correlation energy is[19–21]the electrostatic interaction between the elec-tron density nð~rÞand the density n xcð~r;r0Þat r0of the exchange–correlation hole around an electronat~r:E xc¼ð1=2ÞZd3rnð~rÞZd3r0n xcð~r;~r0Þ=~r0À~rj j:(3)The exchange–correlation hole n xc¼n xþn c is the sum of the separate exchange and correlation holes.The exchange hole is the same as in Har-tree–Fock theory,with the Hartree–Fock orbitals replaced by Kohn–Sham orbitals,and the correla-tion hole is an average of an expectation value over the coupling constant for the electron–elec-tron interaction at fixed electron density.The exact holes satisfy the constraintsn x<0;Zd3r0n xð~r;~r0Þ¼À1;Zd3r0n cð~r;~r0Þ¼0:(4)These constraints are also satisfied by the LDA hole(that of a uniform gas)and this fact explains why LDA works as well as it does.The con-straints can also be imposed to develop other approximations that can improve over LDA by satisfying additional exact constraints.This lesson comes from Langreth and Perdew [19,20]and from Gunnarsson and Lundqvist [21].Lesson6:Searching Over Wavefunctions for theDensity FunctionalThe original proof of the Hohenberg–Kohn the-orem[13]was by reductio ad absurdum and thus not a constructive proof.Alternatively,the vari-ous density functionals,including E xc[n],can be defined by searches over N-electron wavefunc-tions constrained to yield a given electron density [18].Thus,the functionals can be intuitively understood and their exact properties can be derived.This lesson comes from Levy[18].It is an im-portant one because the derived exact properties (e.g.,Refs.[28,29])can be used to constrain the needed approximations.Lesson7:After the Local Density Comes its GradientSecond-order gradient expansionsE GEAxc½n ¼E LDAxc½n þZd3rC xcðnÞr nj j2=n4=3(5)improve on LDA for very slowly varying den-sities but are typically less accurate than LDA for realistic densities[30,31],because[31]the sec-ond-order gradient expansion of the hole violates the exact hole constraints of Lesson5.However, generalized gradient approximations or GGAs [30–35]E GGAxc½n ¼Zd3rn e GGAxcðn;r nÞ(6)can be derived with or without nonempirical parameters,and are more accurate than LDA for the separate exchange and correlation energies of atoms and for the atomization energies of mole-cules and solids.Nonempirical constructions often impose exact constraints on(1)the hole[33],or(2)the energyPERDEW AND RUZSINSZKY4INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY DOI10.1002/qua VOL.000,NO.000functional[35],or(3)the coupling constant de-pendence[36].This lesson comes from Ma and Brueckner[30], Langreth and Perdew[31],Langreth and Mehl [32],Perdew and Wang[33],Becke[34,22],Per-dew et al.[35],and Seidl et al.[36].It was the main development that made DFT of interest to chemists.Lesson8:What is a Fractionof an Electron?The exact density functional E v[n]for the energy can be defined for an open system with noninteger average electron number N[37]by extending the constrained search of Lesson6from wavefunctions to ensembles.The energy E varies linearly between adjacent integer electron num-bers,with derivative discontinuities at the inte-gers.This explains why neutral molecules dissoci-ate to integer-charged atoms,and why the fundamental band gap[38,39]in the exact Kohn–Sham band structure is unphysical.This lesson comes from Perdew et al.[37], Perdew and Levy[38],and Sham and Schlueter [39].Lesson9:The More Information Input,the More Accuratethe OutputWe can make more accurate functionals by adding ingredients to the exchange–correlation energy density beyond n and!n:a.Meta-GGAs add the orbital kinetic energydensitysð~rÞ¼ð1=2ÞXi rf i r r w i rð~rÞj j2;(7)as proposed by Becke[40]with other non-empirical constructions by Perdew et al.[41–43].b.Hyper-GGAs or hybrid functionals addexact exchange information,such as the exact exchange energy or the exact exchange hole,as proposed by Becke[44]and refined by Savin[45],Vydrov and Scuseria[46],etc.Most hyper-GGAs do not properly scale to exact exchange under uniform density scal-ing to the high-density limit but some do[47].c.Random phase approximation(RPA)-likefunctionals add the unoccupied orbitals asdeveloped by Furche[48,49],Harl andKresse[50],etc.Lesson10:We are ClimbingJacob’s LadderThere is a five-rung Jacob’s ladder of common density functional approximations(LSDA,GGA, meta-GGA,hyper-GGA,and RPA-like functionals), as proposed by Perdew and Schmidt[51]and explained in Lesson9.All rungs except the hyper-GGA rung now have nonempirical constructions. Accuracy tends to increase up the puta-tional cost increases modestly from LSDA to GGA to meta-GGA(the three semilocal rungs)but can increase considerably on ascent to higher rungs.The Perdew-Burke-Ernzerhof(PBE)GGA[35] provides a moderately accurate description of atoms,molecules,and solids but is too simple to achieve high accuracy for all three kinds of sys-tems.The optimum GGA for solids has a weaker gradient dependence than the optimum GGA for atoms and molecules,as argued by Perdew and coworkers[52–54].However,a single nonempirical meta-GGA(revTPSS)can work well for the equi-librium properties of atoms,molecules,and solids, as shown by Perdew et al.[43].A meta-GGA can provide different GGA descriptions for solids(especially metals),which have important regions of strong orbital overlap where sð~rÞ)s Wð~rÞ r nj j2=ð8nÞ,and for atoms and mol-ecules,which have important regions where a sin-gle orbital shape dominates the density(as in an electron-pair bond),making sð~rÞ%s Wð~rÞ.Lesson11:Where Semilocal Functionals Fall DownSemilocal functionals(LSDA,GGA,and meta-GGA)necessarily fail(and thus full nonlocality is needed)when the exact exchange–correlation hole has a long-range tail,because semilocal function-als know nothing about the electron density far from an electron.This failure occurs when long-FOURTEEN EASY LESSONS IN DENSITY FUNCTIONAL THEORY VOL.000,NO.000DOI10.1002/qua INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY5range van der Waals interactions between sepa-rating systems are important;the needed correc-tion is present in RPA-like functionals[48–50]but neither in semilocal functionals nor in hyper-GGAs.The failure also occurs when electrons are shared across stretched bonds between distant centers(as in certain transition states and dissoci-ation limits).Semilocal functionals cannot describe such stretched bonds,but hyper-GGAs and RPA-like functionals can do so by displaying more or less the right derivative discontinuities of Lesson8.Dramatic stretched-bond effects have been dis-cussed by Ruzsinszky et al.[55,56],Vydrov et al.[57],Tsuchimochi and Scuseria[58],and Yang and coworkers[59].Lesson12:Elaborate Functionals Need Corrections TooThe RPA,which uses the unoccupied orbitals in the simplest way that makes sense for all sys-tems,is not quite good enough for chemistry.It underestimates atomization energies of molecules by about the same amount that the PBE GGA overestimates them as discovered by Furche[48]. For this property,RPA is far less accurate than meta-and hyper-GGAs.RPA uses exact exchange but makes the correlation energy too negative by roughly0.02hartree/electron.Thus,a correction to RPA is needed.The needed correction to RPA is semilocal(de-scribable by LSDA or GGA)in atoms and at solid surfaces[60]but it is fully nonlocal in molecules [61].An accurate nonempirical nonlocal correction remains to be found.Lesson13:The Kohn–ShamPotential Shapes UpStarting from an orbital functional,the exact Kohn–Sham potential v KSð~rÞof Lesson3can be constructed by the optimized effective potential method of Talman and Shadwick[62,63].Starting from the correlated N-electron wave-function,we can directly construct the energy and electron density.However,it is also computation-ally practical to construct therefrom the exact Kohn–Sham potential and so to study its features. This can be done in two different ways:(1)The Zhao et al.[64]approach first constructs the den-sity and then numerically varies the Kohn–Shampotential to reproduce this density in a system of N noninteracting electrons.(2)Another approach due to Sahni[65]and others constructs the Kohn–Sham potential from expectation values computed from the correlated N-electron wavefunction.Lesson14:After Statics Comes DynamicsDFT can be extended(exactly in principle and approximately in practice)to time-dependent and excited states.The essential idea is to solve time-dependent one-electron Schroedinger equations in which the time-dependent exchange–correlation potential v xcð~r;tÞis a functional of the electron density nð~r0;t0Þ.Poles of the frequency-dependent linear density response function then yield the ex-citation energies.This lesson comes from Runge and Gross[66] and from others[67].ACKNOWLEDGMENTSThe authors thank Sam Trickey for the invita-tion to speak at the50th Sanibel Symposium,and Kieron Burke and Jianwei Sun for suggestions on the manuscript.References1.Perdew,J.P.;Ruzsinszky,A.;Constantin,L.A.;Sun,J.;Csonka,G.I.J Chem Theory Comput2009,5,902.2.Perdew,J.P.;Kurth,S.In A Primer in Density FunctionalTheory;Fiolhais,C.,Nogueira,F.,Marques,M.,Eds.;Lecture Notes in Physics;Springer:Berlin,2003;Vol.620,p1.3.Kohn,W.;Sham,L.J.Phys Rev1965,140,A1133.4.Shavitt,I.;Bartlett,R.J.Many Body Methods in Chemistryand Physics:MBPT and Coupled-Cluster Theory;Cambridge University Press:Cambridge,2009.5.Thomas,L.H.Proc Cambridge Philos Soc1926,23,542.6.Fermi,E.Zeit fuer Physik1928,48,73.7.Teller,E.Rev Mod Phys1962,34,627.8.Kurth,S.;Perdew,J.P.Int J Quantum Chem2000,77,819.9.Perdew,J.P.;Constantin,L.A.Phys Rev B2007,75,155109.10.Karasiev,V.V.;Jones,R.S.;Trickey,S.B.;Harris,F.E.Phys Rev B2009,80,245120.11.Huang,C.;Carter,E.A.Phys Rev B2010,81,045206.12.Slater,J. C.The Self-Consistent Field for Molecules andSolids;McGraw-Hill:New York,1974.13.Hohenberg,P.;Kohn,W.Phys Rev1964,136,B864.PERDEW AND RUZSINSZKY6INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY DOI10.1002/qua VOL.000,NO.00014.Fiolhais,C.;Perdew,J.P.Phys Rev B1992,45,6207.15.Constantin,L. A.;Pitarke,J.M.;Dobson,J. F.;Garcia-Lekue,A.;Perdew,J.P.Phys Rev Lett2008,100,036401. 16.Parr,R.G.;Yang,W.Density Functional Theory of Atomsand Molecules;Oxford University Press:Oxford,1989.17.Jones,R.O.;Gunnarsson,O.Rev Mod Phys1989,61,689.18.Levy,M.Proc Nat Acad Sci USA1979,76,6062.ngreth,D.C.;Perdew,J.P.Solid State Commun1975,17,1425.ngreth,D.C.;Perdew,J.P.Phys Rev B1977,15,2884.21.Gunnarsson,O.;Lundqvist,B.I.Phys Rev B1976,13,4274.22.Becke,A.D.Phys Rev A1988,38,3098.23.Kohn,W.Rev Mod Phys1999,71,1253.24.von Barth,U.;Hedin,L.J Phys C:Solid State Phys1972,5,1629.ng,N.D.;Kohn,W.Phys Rev B1970,1,4555.26.Moruzzi,V.L.;Janak,J.F.;Williams,A.R.Calculated Elec-tronic Properties of Metals;Pergamon:New York,1978. 27.Gunnarsson,O.;Lundqvist,B.I.;Wilkins,J.W.Phys Rev B1974,10,1319.28.Levy,M.;Perdew,J.P.Phys Rev A1985,32,2010.29.Oliver,G.L.;Perdew,J.P.Phys Rev A1979,20,397.30.Ma,S.-K.;Brueckner,K.A.Phys Rev1968,165,18.ngreth,D.C.;Perdew,J.P.Phys Rev B1980,21,5469.ngreth,D.C.;Mehl,M.J.Phys Rev B1983,20,1809.33.Perdew,J.P.;Wang,Y.Phys Rev B1986,33,8800;Erratum:Perdew,J.P.;Wang,Y.Phys Rev B1989,40, 3399.34.Becke,A.D.J Chem Phys1986,84,4524.35.Perdew,J.P.;Burke,K.;Ernzerhof,M.Phys Rev Lett1996,77,3865;Erratum:Perdew,J.P.;Burke,K.;Ernzerhof,M.Phys Rev Lett1997,78,1396.36.Seidl,M.;Perdew,J.P.;Kurth,S.Phys Rev Lett2000,84,5070.37.Perdew,J.P.;Parr,R.G.;Levy,M.;Balduz,J.L.Phys RevLett1982,49,1691.38.Perdew,J.P.;Levy,M.Phys Rev Lett1983,51,1884.39.Sham,L.J.;Schlueter,M.J.Phys Rev Lett1983,51,1888.40.Becke,A.D.;Roussel,M.R.Phys Rev A1989,39,3761,and references therein.41.Perdew,J.P.;Kurth,S.;Zupan,A.;Blaha,P.Phys Rev Lett1999,82,2544;Erratum:Perdew,J.P.;Kurth,S.;Zupan,A.;Blaha,P.Phys Rev Lett1999,82,5179.42.Tao,J.;Perdew,J.P.;Staroverov,V.N.;Scuseria,G.E.Phys Rev Lett2003,91,146401.43.Perdew,J.P.;Ruzsinszky,A.;Csonka,G.I.;Constantin,L.A.;Sun,J.Phys Rev Lett2009,103,026403.44.Becke,A.D.J Chem Phys1993,98,5648.45.Savin, A.In Recent Developments and Applications ofModern Density Functional Theory;Seminario,J.M.,Ed.;Elsevier:Amsterdam,1996;p327.46.Vydrov,O.A.;Scuseria,G.E.J Chem Phys2006,125,234109.47.Perdew,J.P.;Staroverov,V.N.;Tao,J.;Scuseria,G.E.Phys Rev A2008,78,052513.48.Furche,F.Phys Rev B2001,64,195120.49.Furche,F.J Chem Phys2008,129,114105.50.Harl,J.;Kresse,G.Phys Rev Lett2009,103,056401.51.Perdew,J.P.;Schmidt,K.In Density Functional Theoryand Its Applications to Materials;Van Doren,V.E.,Van Alsenoy,K.,Geerlings,P.,Eds.;American Institute of Physics:Melville,NY,2001;p1.52.Perdew,J.P.;Constantin,L.A.;Sagvolden,E.;Burke,K.Phys Rev Lett2006,97,223002.53.Csonka,G.I.;Vydrov,O.A.;Scuseria,G.E.;Ruzsinszky,A.;Perdew,J.P.J Chem Phys2007,126,244107.54.Perdew,J.P.;Ruzsinszky,A.;Csonka,G.I.;Constantin,L.A.;Zhou,X.;Vydrov,O.A.;Scuseria,G.E.;Burke,K.PhysRev Lett2008,100,136406;Erratum:Perdew,J.P.;Ruz-sinszky, A.;Csonka,G.I.;Constantin,L. A.;Zhou,X.;Vydrov,O.A.;Scuseria,G.E.;Burke,K.Phys Rev Lett 2009,102,039902.55.Ruzsinszky,A.;Perdew,J.P.;Csonka,G.I.;Vydrov,O.A.;Scuseria,G.E.J Chem Phys2006,125,194112.56.Ruzsinszky,A.;Perdew,J.P.;Csonka,G.I.;Vydrov,O.A.;Scuseria,A.J Chem Phys2007,126,104102.57.Vydrov,O.A.;Scuseria,G.E.;Perdew,J.P.J Chem Phys2007,126,154109.58.Tsuchimochi,T.;Scuseria,G.E.J Chem Phys2009,131,121102.59.Cohen,A.J.;Mori-Sanchez,P.;Yang,W.Science2008,321,792.60.Yan,Z.;Perdew,J.P.;Kurth,S.Phys Rev B2000,61,16430;Erratum:Yan,Z.;Perdew,J.P.;Kurth,S.Phys Rev B2010,81,169902.61.Ruzsinszky,A.;Perdew,J.P.;Csonka,G.I.J Chem TheoryComput2010,6,127.62.Talman,J.D.;Shadwick,W.F.Phys Rev A1976,14,36.63.Kuemmel,S.;Perdew,J.P.Phys Rev Lett2003,90,043004.64.Zhao,Q.;Morrison,R.C.;Parr,R.G.Phys Rev A1994,50,2138.65.Sahni,V.Quantal Density Functional Theory;Springer:Berlin,2004,and references therein.66.Runge,E.;Gross,E.K.U.Phys Rev Lett1984,52,997.67.Marques,M.A.L.;Ullrich,C.A.;Nogueira,F.;Rubio,A.;Burke,K.;Gross,E.K.U.,Eds.Time-Dependent Density Functional Theory;Springer Lecture Notes in Physics;Springer:Berlin,2006;Vol.706.FOURTEEN EASY LESSONS IN DENSITY FUNCTIONAL THEORY VOL.000,NO.000DOI10.1002/qua INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY7。

a rX iv:mat h /11233v1[mat h.AG ]29Ja n21Hurwitz Equivalence in Braid Group B 3T.Ben-Itzhak and M.Teicher 1ABSTRACT.In this paper we prove certain Hurwitz equivalence proper-ties of B n .In particular we prove that for n =3every two Artin’s factoriza-tions of ∆23of the form H i 1···H i 6,F j 1···F j 6(with i k ,j k ∈{1,2})where {H 1,H 2},{F 1,F 2}are frames,are Hurwitz equivalent.The proof provided here is geometric,based on a newly defined frame type.The results will be applied to the classification of algebraic surfaces up to deformation.It is already known that there exist surfaces that are diffeomor-phic to each other but are not deformations of each other (Manetti example).We are constructing a new invariant based on Hurwitz equivalence class of factorization,to distinguish among diffeomorphic surfaces which are not de-formation of each other.The precise definition of the new invariant can be found at [4]or [5].The main result of this paper will help us to compute the new invariant.1Basic Definitions In this section we recall some basic definitions and statements from [3]:Let D be a closed disk on R 2,K ⊂D finite set,u ∈∂D .Any diffeo-morphism of D which fixes K and is the identity on ∂D acts naturally on Π1=Π1(D −K,u ).We say that two such diffeomorphisms of D (which fix K and equal identity on ∂D )are equivalent if they define the same au-tomorphism on Π1(D −K,u ).This equivalence relation is compatible with composition of diffeomorphism and thus the equivalence classes form a group.Definition1.1Braid Group B n[D,K].Let D,K be as above,n=#K,and let B be the group of all diffeomor-phismsβof D such thatβ(K)=K,β|∂D=Id∂D.Forβ1,β2∈B we say thatβ1is equivalent toβ2ifβ1andβ2define the same automorphism of Π1(D−K,u).The quotient of B by this equivalence relation is called the Braid group B n[D,K].Equivalently,if we take the canonical homomorphismψ:B→Aut(Π1(D−K,u))then B n[D,K]=Im(ψ).The elements of B n[D,K]are called braids.Lemma1.2If K′⊂D′in another pair as above with#K′=#K=n then B n[D′,K′]is isomorphic to B n[D,K].This gives rise to the definition of B n:Definition1.3B n=B n[D,K]for some D,K with#K=n.Definition1.4H(σ),half-twist defined byσ.Let D and K be defined as above.Let a,b∈K,K a,b=K\{a,b}andσbe a simple path(without a self intersection)in D\∂D connecting a with b such K={a,b}.Choose a small regular neighborhood U ofσsuch that thatσU=φ,and an orientation preserving diffeomorphismψ:R2→C1 K a,bsuch thatψ(σ)=[−1,1]={z∈C1|Re(z)∈[−1,1],Im(z)=0}andψ(U)= {z∈C1||z|<2}.Letα(r),r≥0,be a real smooth monotone function such thatα(r)=1for r∈[0,3/2]andα(r)=0for r≥2.Define a diffeomor-phism h:C1→C1as follows:for z∈C1,z=re iφlet h(z)=re i(φ+α(r)π). It is clear that the restriction of h to{z∈C1||z|≤3/2}coincides with the 180◦positive rotation,and that the restriction to{z∈C1||z|≥2}is the identity map.The diffeomorphismψ−1◦h◦ψis inducing a braid called half-twist and denoted by H(σ)Definition1.5Frame of B n[D,K]2Let K ={a 1,...,a n }and σ1,...,σn −1be a system of simple smooth paths in D −∂D such that σi connects a i with a i +1and L = σi is a simple smooth path.The ordered system of half-twists (H 1,...,H n −1)defined by {σi }n −1i =1is called a frame of B n [D,K ]Theorem 1.6Let (H 1,...,H n −1)be a frame of B n [D,K ]then:B n [D,K ]is generated by {H i }n −1i =1and the following is a complete list of relations:H i H j =H j H i if |i −j |>1(Commutative relation)H i H j H i =H j H i H j if |i −j |=1(Triple relation)Proof can be found for example in [3].This theorem provides us with Artin’s algebraic definition of Braid group.2Properties of Hurwitz MovesIn this section we define Hurwitz Move and Hurwitz Equivalence and prove a certain theorem on the Hurwitz Equivalence of words in the Braid group which is correct for any Braid group of arbitrary order.Definition 2.1Hurwitz move on G m (R k ,R −1k )Let G be a group,−→t =(t 1,...,t m )∈G m .We say that −→s =(s 1,...,s m )∈G mis obtained from −→t by the Hurwitz move R k (or −→t is obtained from −→s by the Hurwitz move R −1k )ifs i =t i for i =k,k +1,s k =t k t k +1t −1k ,s k +1=t k .Definition 2.2Hurwitz move on factorizationLet G be a group and t ∈G .Let t =t 1···t m =s 1···s m be two factorized expressions of t .We say that s 1···s m is obtained from t 1···t m by the Hur-witz move R k if (s 1,...,s m )is obtained from (t 1,...,t m )by Hurwitz the move R k .3Definition2.3Hurwitz equivalence of factorizationThe factorizations s1···s m,t1···t m are Hurwitz equivalent if they are ob-tained from each other by afinite sequence of Hurwitz moves.The notation is t1···t m HE∽s1···s m.Definition2.4Word in B nA word inB n is a representation of braid as a sequence of the frame elements and their inverses.We will need a certain result of Garside:Claim2.5(Garside):Every two positive words(all generators with posi-tive powers)which are equal are transformable into each other through afinite sequence of positive words,such that each word of the sequence is positive and obtained from the proceeding one by a direct application of the commutative relation or the triple relation.Proof:[1].The following is obvious,never the less we give a short proof for clarification:Claim2.6G is a group g1,g2∈G:1.If g1g2=g2g1then g1·g2HE∽g2·g12.If g1g2g1=g2g1g2then g1·g2·g1HE∽g2·g1·g2Proof:1.g1·g2R1→g1g2g−11·g1=g2·g1.2.g1·g2·g1R2→g1·g2g1g−12·g2R1→g1g2g1g−12g−11·g1·g2but g1g2g1=g2g1g2 so g1g2g1g−12g−11=g2and we get g1·g2·g1HE∽g2·g1·g2From Garside and the above we get the following proposition:4Proposition2.7Let H1,...,H n−1be a set of generators of B n and H i1...H ip=H j1...H jptwo positive words(with i k,j k∈{1,...n−1})then H i1···H ipHE∽H j1···H jp.Proof:Apply2.5on H i1...H ip=H j1...H jpwe get afinite sequence of positivewords{W r}q r=0s.t.W0=H i1...H ip,W q=H j1...H jpand W r+1is obtainedfrom W r by a single application of the commutative relation or the triple relation.An application of the triple relation(as in2.6)is equal to an application of2 Hurwitz moves R t+1,R t.An application of the commutative relation is equal to an application of one Hurwitz move(on the commuting elements).Thus, W0HE∽W qDefinition2.8∆2n∈B n[D,K]∆2n=(H1...H n−1)n where{H i}n−1i=1is a frame.We apply2.7on∆2n:Corollary2.9All∆2n factorizations H i1···H in(n−1)i k∈{1,...,n−1}areHurwitz Equivalent.3B3PropertiesThis section concentrates on B3and we prove the following new result: Theorem3.1Let{H1,H2},{F1,F2}two frames of B3,then for every twowords∆23=H i1...H i6=F j1...F j6(with i k,j k∈{1,2})the factorizationsH i1···H i6,F j1···F j6are Hurwitz equivalent.The proof of the main theorem is at the end of the section following from propositions3.7and3.9.Let D be a closed disk on R2and K⊂D,K={a,b,c}.Wefix two parallel lines L1,L2in D which separate the points in K(seefigure1).With the choice of L1and L2we define the length and the minimal paths related to a half-twist:5...L1D L2Figure 1:Simple path with m (σ)=3Definition 3.2Let σbe a simplepath in D \∂D that defines the half-twist H (σ).Then m (σ)=#{σ (L 1 L 2)}as demonstrated in figure 1.Definition 3.3Let H be a half-twist in B n [D,K ].We define the length of H ,m (H )=min {m (σ)|H =H (σ)}and we call such a path σwhich gives the minimal value,the minimal path of H .Notation 3.4Any frame {H 1,H 2}can be defined by the minimal paths σ1,σ2which also satisfy the relations in 1.5.Definition 3.5We say that a frame {H 1,H 2}is economic if there exist σ1,σ2minimal paths of H 1,H 2respectively s.t.for every small neighborhood U of (σ1 K )\σ2,σ1⊂σ2outside U (see 2)Lemma 3.6Let {H 1,H 2}be economic frame then m (H 1)=m (H 2)Proof:Trivial.Proposition 3.7Any frame {H 1,H 2}which generates B 3[D,K ]s.t max (m (H 1),m (H 2))>1is economic.6...σ2c b a σ1Figure 2:Economic frame m (H (σ1))<m (H (σ2)).Proof:Suppose that there exists a frame {H 1,H 2}as above which is not economic.From notation 3.4,there exist σ1,σ2as defined in 1.5s.t.σ1,σ2are minimal paths of H 1,H 2respectively and the two paths are ’separated’at some point.We will show that such a ’separation’is not possible.Starting from s =σ1 σ2we will examine the first ’separation’where the two paths are sepa-rated by one of the points in K .The cases where s =a and s =c are symmetric.Proving the case where s =b is similar.We will assume that both paths start at aCase 1:The two paths entering a neighborhood of the same point but with different orientation (one clockwise and the other counter-clockwise).(1.a)Entering and turning back as shown in figure 3.The two paths create a cycle with one point inside,the internal path has no where to turn,and thus cannot end.This case is also relevant when one path is turning back and the other continues to the next point.(1.b)Entering and continue to the next point:(1.b.i)The two paths continue to the next point with the same orientation (figure 4).The two paths create a cycle that starts at a and contains b .One path has to end at b and will have to change it’s orientation through c .This7...L1D L2ab c Figure 3:Same point different orientation and turning back....L1DL2a b c Figure 4:Same point different orientation and continue to next point with the same orientation.will close a cycle with all the points inside,and the external path has no where to end.(1.b.ii)The two paths continue to the next point with different orientation (figure 5).The two paths create a cycle with all points inside so the external path has no where to end.Case 2:Entering to the same point with the same orientation and leaving to different points.8...L1DL2a b c Figure 5:Same point different orientation and continue to next point with different orientation....L1D L2ab c Figure 6:External path must create a cycle with the internal.This can only happen in point b .The internal path must go back to a and the external will go to c .(2.a)The external path goes to c by changing orientation (figure 6).This enforces the external path to go around a and create a cycle with the inter-nal path.Thus,the two paths create a cycle with all points inside and the external path has no where to end.(2.b)The external path goes to c with the same orientation (figure 7).The external path cannot go to the common part (this will create an empty cycle and the path has no where to end)of the paths so both paths continue to a .9...L1D L2ac b Figure 7:External path must create a cycle with the internal.In this case we get an equivalent cycle as in 1.b.i.This conclude the proof of proposition 3.7.Lemma 3.8Let {H 1,H 2}be a frame generates B 3[D,K ]and H ζhalf-twist,than {H ζ−1H 1H ζ,H ζ−1H 2H ζ}is also a frame.Proof:By III.1.0of [2],H −11H 2H 1=H (H 1(σ2))where H 2=H (σ2).{H 1=H (σ1),H 2=H (σ2)}is a frame,therefore σ1 σ2is a simple smooth path.H ζis a diffeomorphism so H ζ(σ1) H ζ(σ2)=H ζ(σ1 σ2)is also asimple smooth path.K ⊂σ1 σ2,H ζ(K )=K and therefore H ζ(σ1),H ζ(σ2)connecting all points in K appropriately.Proposition 3.9Let {H 1,H 2}be a frame of B 3[D,K ]then there exist a frame {F 1,F 2}s.t.H 1·H 2·H 1·H 2·H 1·H 2HE∽F 1·F 2·F 1·F 2·F 1·F 2and max (m (H 1),m (H 2))>max (m (F 1),m (F 2)).10Proof:From proposition 3.7we get that {H 1,H 2}is economic and from lemma 3.6m (H 1)=m (H 2)we will assume that m (H 1)<m (H 2).Since {H 1,H 2}is economic and m (H 1)<m (H 2),operating H 1on σ2(conju-gation)will cause σ2to start coming back from the starting point (σ1 σ2 K )along the common part (σ1)as shown in figure 8.Therefore,we get that ei-therm (H −11H 2H 1)=m (H (H 1(σ2)))=m (H 2)−m (H 1)orm (H 1H 2H −11)=m (H (H −11(σ2)))=m (H 2)−m (H 1)In the case where m (H (H 1(σ2)))=m (H 2)−m (H 1):By performing the Hurwitz moves R 1R 0R 4R 3we get:H 1·H 2·H 1·H 2·H 1·H 2HE∽H 2·H 1·H 2·H 1·H 2·H 1and by performing R −10R −12R −14:H 2·H 1·H 2·H 1·H 2·H 1HE∽H 1·H −11H 2H 1·H 1·H −11H 2H 1·H 1·H −11H 2H 1Since m (H −11H 2H 1)=m (H (H 1(σ2)))and m (H 2)>m (H 1),max (m (H 1),m (H 2))>max (m (H 1),m (H −11H 2H 1))From Lemma 3.8,the set {H 1,H −11H 2H 1}is a frame,we get an equivalent factorization of the same form but with a reduced length.In the case where m (H (H −11(σ2)))=m (H 2)−m (H 1):H 1·H 2·H 1·H 2·H 1·H 2HE ∽H 1H 2H −11·H 1·H 1H 2H −11·H 1·H 1H 2H −11·H 1By performing the Hurwitz moves R 0R 2R 4.Once again,we get a framewhere the maximum length is reduced.Proof of the main theorem:Let H i 1·H i 2·H i 3·H i 4·H i 5·H i 6and F j 1·F j 2·F j 3·F j 4·F j 5·F j 6be two factorizations as above.11......H 1(σ2)σ1σ2Figure 8:Half-twist conjugation.From 2.7we get that:H i 1·H i 2·H i 3·H i 4·H i 5·H i 6HE∽H 1·H 2·H 1·H 2·H 1·H 2andF j 1·F j 2·F j 3·F j 4·F j 5·F j 6HE ∽F 1·F 2·F 1·F 2·F 1·F 2By 3.9,both H 1·H 2·H 1·H 2·H 1·H 2and F 1·F 2·F 1·F 2·F 1·F 2are Hurwitz equivalent to X 1·X 2·X 1·X 2·X 1·X 2where {X 1,X 2}is a frame with m (X 1)=m (X 2)=1.Since such a frame is unique we get thatH i 1·H i 2·H i 3·H i 4·H i 5·H i 6HE ∽F j 1·F j 2·F j 3·F j 4·F j 5·F j 6References[1]F.A.Garside The Braid group and other groups Quart.J.Math Oxford(2)78(1969),235-254.[2]B.Moishezon and M.Teicher,Braid group technique in complex geom-etry V:The fundamental group of a complement of a branch curve of a veronese generic projection ,Communication in analysis and geometry 4,No.11,(1996),1-120[3]B.Moishezon and M.Teicher,Braid group techniques in complex ge-ometry I,Line arrangments in CP 2,Contemporary Math.78(1988),425-555.12[4]Vik.S.Kulikov and M.Teicher,Braid monodromy factorization and dif-feomorphism types Izvestia,Journal of the Russian Academy of Science, Tom64,2,2000,89-120[5]M.Teicher,Braid monodromy type of4manifolds Preprint13。

Ole WintherTheoretical Physics,Lund UniversityS¨o lvegatan14A,S-22362Lund,Swedenwinther@nimis.thep.lu.seAbstractUsing statistical mechanics results,I calculate learning curves(averagegeneralization error)for Gaussian processes(GPs)and Bayesian neuralnetworks(NNs)used for regression.Applying the results to learning ateacher defined by a two-layer network,I can directly compare GP andBayesian NN learning.Ifind that a GP in general requires-trainingexamples to learn input features of order(is the input dimension),whereas a NN can learn the task with order the number of adjustableweights training examples.Since a GP can be considered as an infiniteNN,the results show that even in the Bayesian approach,it is importantto limit the complexity of the learning machine.The theoreticalfindingsare confirmed in simulations with analytical GP learning and a NN meanfield algorithm.1IntroductionNon-parametric kernel methods such as Gaussian Processes(GPs)and Support V ector Ma-chines(SVMs)are closely related to neural networks(NNs).These may be considered as single layer networks in a possible infinite dimensional feature space.Both the Bayesian GP approach and SVMs regularize the learning problem so that only afinite number of the features(dependent on the amount of data)is used.Neal[1]has shown that Bayesian NNs converge to GPs in the limit of infinite number of hidden units and furthermore argued that(1)there is no reason to believe that real-world problem should require only a‘small’number of hidden units and(2)there are in the Bayesian approach no reasons(besides computational)to limit the size of the network. Williams[2]has derived kernels allowing for efficient computation with both infinite feed-forward and radial basis networks.In this paper,I show that learning with afinite rather than infinite networks can make a profound difference by studying the case where the task to be learned is defined by a large butfinite two-layer NN.A theoretical analysis of the Bayesian approach to learning this task shows that the Bayesian student makes a learning transition from a linear model to specialized non-linear one when the number of examples is of the order of the number of adjustable weights in the network.This effect–which is also seen in the simulations–is a consequence of thefinite complexity of the network.In an infinite network,i.e.a GP on theother hand such a transition will not occur.It will eventually learn the task but it requires -training examples to learn features of order,where is the input dimension. Here,I focus entirely on regression.However,the basic conclusions regarding learning with kernel methods and NNs turn out to be valid more generally,e.g.for classification unpublished results and[3].I consider the usual Bayesian setup of supervised learning:A training set(and)is known and the output for the new in-put is predicted by the function which is sampled from the prior distribution of model outputs.I will consider both a Gaussian process prior and the prior implied by a large(butfinite)two-layer network.The output noise is taken to be Gaussian,so the Likelihood becomes(1)where I have introduced,,to denote an average with re-spect to the model output prior.Gaussian processes.In this case,the model output prior is by definition Gaussian.I consider a Bayesian framework(withfixed known hyperparameters)with a weight prior that factorizes over hidden unitsand Gaussian input-to-hidden weights.From Bayesian NNs to GPs.The prior over outputs for the Bayesian neural network is.In the infinite hidden unit limit, ,when has zero mean andfinite,say unit variance,it follows from the central limit theorem(CLT)that the prior distribution converges to a Gaussian process with kernel[1,2]2Statistical mechanics of learningThe aim of the average case statistical mechanics analysis is to derive learning curves,i.e. the expected generalization error as a function of the number of training examples.The generalization error of the Bayes regressor eq.(1)is(4) where double brackets denote an average over bothtraining examples and the test example.Rather than using eq.(4)directly,will–as usually done–be derived from the average of the free energy,where the partition function is given by(6)(8)where the features are orthonormal eigenvectors of the covariance function with eigenvalues:and. The teacher may also be expanded in terms of the the features:Using the orthonormality the averages may be found:,and.For a Gaussian process prior,the prior over the weight is a spherical Gaussian.Averaging over,the sad-dlepoint equations can be written in terms of the number of examples,the noise levels and,the eigenvectors of the covariance function and the teacher projections:(10) These eqs.are valid for afixed teacher.However,eq.(9)may also be averaged over the distribution of teachers.In the Bayes optimal scenario,the teacher is sampled from the same prior as the student and.Thus implying,I getwith degeneracy,where is the cardinality(in the example above).Plugging these results into eqs.(9)and(10), it follows that to learn features that are order in the inputs,examples are needed. The same behavior has been predicted for learning in SVMs[3].The infinite net eq.(3)reduces to an inner product covariance function for( controls the degree on non-linearity of the rule)and large,:(12) Figure1shows learning curves for GPs for the infinite network kernel.The mismatch between theory and simulations is expected to be due to-corrections to the eigen-values.Thefigure clearly shows that learning of the different order features takes place on different scales.The stars on the-axis show the theoretical prediction of asymptotic error for(the teacher is an odd function).2.2Bayesian neural networksThe limit of large butfinite NNs allows for efficient computation since the prior over functions can be approximated by a Gaussian.The hidden-to-output weights are for sim-050010001500200000.050.10.15LargeFigure 1:Learning curve for Gaussian processes with the infinite network kernel (,and )for two scales of training examples.The full line is the the theoretical prediction for the Bayes optimal GP scenario.The two other curves (almost on top of each other as predicted by theory)are simulations for the Bayes optimal scenario (dotted line)and for GP learning a neural network with hidden units (dash-dotted line).plicity set to one and we introduce the ‘fields’and write the output as ,.In the following,Idiscuss the TAP mean field algorithm used to find an approximation to the Bayes regressor and briefly the theoretical statistical mechanics analysis for the NN task.Mean field algorithm.The derivation sketched here is a straightforward generalization of previous results for neural networks [7].The basic cavity assumption [7,8]is that for large and for a suitable input distribution,the predictive distribution is Gaussian:The predictive distribution for the fields is also assumed to be Gaussianwhere.Using these assumptions,I get an approxi-mate Bayes regressor (13)To make predictions,we therefore need the two first moments of the weights since and .We can simplify this in the large limit by taking the inputs to by iid with zero mean and unit variance:.This approximation can be avoided at a substantial com-putational cost [8].Furthermore,turns out equal to the prior covariance [7].The following exact relation is obtained for the mean weights024681000.010.020.030.040.05forfirst order transitions and should also be observable in the Monte Carlo approach to Bayesian NNs[1].3DiscussionLearning afinite two-layer regression NN using(1)the Bayes optimal algorithm and(2) the Bayes optimal algorithm for an infinite network(implemented by a GP)is compared. It is found that the Bayes optimal algorithm can have a very superior performance.This can be explained as an entropic effect:The infinite network will–although the cor-rectfinite network solution is included a priori–have a vanishing probability offinding this solution.Thefinite network on the other hand is much more constraint wrt the func-tions it implements.It can thus–even in the Bayesian setting–give a great pay off to limit complexity.For-dimensional inner product kernel with iid input distribution,it is found that it in general requires training examples to learn features of.Unpublished results and[3]show that these conclusions remain true also for SVM and GP classification.For SVM hand-written digit recognition,fourth order kernels give good results in prac-tise.Since,it can be concluded that the‘effective’dimension, against typically,i.e.some inputs must be very correlated and/or carry very little information.It could therefore be interesting to develop methods to measure the effective dimension and to extract the important lower dimensional features rather than performing the classification directly from the images.AcknowledgmentsI am thankful to Manfred Opper for valuable discussions and for sharing his results with me and to Klaus-Robert M¨u ller for discussions at NIPS.This research is supported by the Swedish Foundation for Strategic Research.References[1]R.Neal,Bayesian Learning for Neural Networks,Lecture Notes in Statistics,Springer(1996).[2] C.K.I.Williams,Computing with Infinite Networks,in Neural Information Processing Systems9,Eds.M.C.Mozer,M.I.Jordan and T.Petsche,295-301,MIT Press(1997).[3]R.Dietrich,M.Opper and H.Sompolinsky,Statistical Mechanics of Support Vector Machines,Phys.Rev.Lett.82,2975-2978(1999).[4] C.K.I.Williams and C.E.Rasmussen,Gaussian Processes for Regression,In Advances inNeural Information Processing Systems8(NIPS’95).Eds.D.S.Touretzky,M.C.Mozer and M.E.Hasselmo,514-520,MIT Press(1996).[5] D.Malzahn and M.Opper,In this volume.[6]P.Sollich,Learning Curves for Gaussian Processes,In Advances in Neural Information Pro-cessing Systems11(NIPS’98),Eds.M.S.Kearns,S.A.Solla,and D.A.Cohn,344-350,MIT Press(1999).[7]M.Opper and O.Winther,Mean Field Approach to Bayes Learning in Feed-Forward NeuralNetworks,Phys.Rev.Lett.76,1964-1967(1996).[8]M.Opper and O.Winther,Gaussian Processes for Classification:Mean Field Algorithms,Neu-ral Computation12,2655-2684(2000).[9]M.Ahr,M.Biehl and R.Urbanczik,Statistical physics and practical training of soft-committeemachines Eur.Phys.J.B10,583(1999).。

Fast computation of Tate pairing on general divisors of genus3hyperelliptic curves∗Eunjeong Lee a,Hyang-Sook Lee b and Yoonjin Lee ca School of Computational Sciences,Korea Institute for Advanced Study,130-722,Seoul,Koreab Department of Mathematics,Ewha Womans University,120-750,Seoul,Koreac Department of Mathematics,Simon Fraser University,V5A1S6,British Columbia,CanadaAbstractFor the Tate pairing computation over hyperelliptic curves,there are developments by Duursma-Lee and Barreto et al.,and those computations are focused on degenerate divisors.As divisorsare not degenerate form in general,it is necessary tofind algorithms on general divisors forthe Tate pairing computation.In this paper,we present two efficient methods for computingthe Tate pairing over divisor class groups of the hyperelliptic curves y2=x p−x+d,d=±1of genus3.First,we provide the pointwise method,which is a generalization of the previousdevelopments by Duursma-Lee and Barreto et al.In the second method,we use the resultantfor the Tate pairing computation.According to our theoretical analysis of the complexity,theresultant method is48.5%faster than the pointwise method in the best case and15.3%fasterin the worst case,and our implementation result shows that the resultant method is muchfaster than the pointwise method.These two methods are completely general in the sense thatthey work for general divisors with Mumford representation,and they provide very explicitalgorithms.keywords:Tate pairing;hyperelliptic curves;divisors;resultant;pairing-based cryptosystem IntroductionIn recent years the Tate pairing and the Weil pairing have been getting a lot of attentions for designing various protocols in cryptosystem[4,5,14,13,22,25,26].It is therefore important to develop an efficient implementation of the pairings for the practical applications.The recent papers by Barreto et al.[1]and Galbraith et al.[11]provided the fast computation of the Tate pairing over the supersingular elliptic curves y2=x3−x±1in characteristic three.In2003, Duursma and Lee[9]provided a closed formula for the efficient computation of the Tate pairing on y2=x p−x±1,p=3(mod4)in characteristic p.After then,Barreto et al.[2]improved Duursma and Lee’s result and proposed a general technique for the efficient computation of the Tate pairing on supersingular abelian varieties using Eta pairing approach[2,20].They also described efficient pairing algorithms on F q-rational points for elliptic and hyperelliptic curves over F q.∗(e-mail)ejlee@kias.re.kr,hsl@ewha.ac.kr,yoonjinl@sfu.ca The authors a,b were supported by KOSEF,grant number R01-2005-000-10713-0.This work was also done while the last author c was visiting KIAS in Seoul during the summers of2004and2005.The author expresses their gratitude to the institute.1In fact,generally divisor operations over hyperelliptic curves are more complicated than point operations over elliptic curves.Therefore,it has been pointed out that Elliptic Curve Cryptosystem (ECC)is more efficient than Hyperelliptic Curve Cryptosystem(HCC)[25].The Tate pairing computation uses the Miller algorithm,and the Miller algorithm relies on divisor operations.Thus one expects that the Tate pairing computation over hyperelliptic curves may not be as efficient as that over elliptic curves.However,in some special cases,it was shown that HCC can be made more efficient than ECC by giving the explicit formula for divisor operations[6,19,23].For the higher genus,preserving the same security level,we can decrease the size of the definingfield.In fact,some examples given in[6,19]show that for the efficiency of cryptosystems,the size of the definingfield is more important than the complexity of group operation formula.For the Tate pairing,Barreto et al.[2]presented implementation results over elliptic curves and hyperelliptic curves of genus2,where both are defined over F2n.The running time for the Tate pairing over hyperelliptic curves was faster than that of elliptic curves.For the Tate pairing computation it is therefore certainly worthwhile to work over some special types of hyperelliptic curves.Recent developments[2,9]on the Tate pairing computation on hyperelliptic curves over afinite field F q have focused on the case of degenerate divisors.However,in the pairing-based cryptography, the efficient Tate pairing implementation over general divisors is significantly more important.For instance,in the Boneh-Franklin identity-based encryption scheme,the private keys are general divisors,and therefore the decryption process requires computing a pairing of general divisors.For the case of genus2,the result in[6]presents both divisor-wise and pointwise approach,and it turns out that the divisor-wise approach is more efficient than the pointwise approach.For the case of genus≥3,when divisors are general,there has been no Tate pairing computation method developed so far.In this paper,we develop general methods of computing the Tate pairing for the genus3case. We present two feasible methods by pointwise approach and the resultant approach for computing the Tate pairing over divisor class groups of the hyperelliptic curves H d:y2=x p−x+d,where d=±1and p=7.Those methods are completely general in the sense that they work for general divisors with Mumford representation[21],and we give very explicit and feasible algorithms over H d.Furthermore,we analyze the complexities of two methods and show implementation results of proposed algorithms.For our two methods,we use the Eta pairing for reducing the computation cost.We used SINGULAR[12]software package for symbolic computations in this paper.In Section2,we present the pointwise method for computing the Tate pairing over general divisors.This method is a generalization of the pointwise method developed in[2]and[9].In Section3,we use resultant to compute the Tate pairing with Mumford representation.In Section4, we compare the complexities of two methods and show that the resultant method is48.5%faster than the pointwise method in the best case and15.3%faster in the worst case.In Section5,we report experiment results based on our implementation using NTL[24]software package.According to the implementation,we conclude that the Tate pairing computation by using the resultant is much faster than the pointwise approach.We point out that this is thefirst implementation over a genus3curve.1Tate pairing on divisorsLet F q be afinitefield with q elements,and H/F q be a hyperelliptic curve over F q.We denote by J H the group of degree zero divisor classes of H.Note that each divisor class can be uniquely2represented by the reduced divisor using the Mumford representation[21].Reduced divisors of the curve H can be found as discussed in[17]and[21],and most of reduced divisors in J H with genus 3are written as D=[U D,V D]=[x3+u D,2x2+u D,1x+u D,0,v D,2x2+v D,1x+v D,0].We recall the definition of the Tate pairing[10].Let be a positive divisor of the order of J H(F q)with gcd( ,q)=1,and k be the smallest integer such that |(q k−1);such k is called the embedding degree.Let J H[ ]={D∈J H| D=O}.The Tate pairing is a map·:J H[ ]×J H(F q k)/ J H(F q k)→F∗q k/(F∗q k)D,E =f D(E ),where div(f D)= D and E ∼E with support(E )∩support(div(f D))=∅.We define the Tateparing value by t(D,E)= D,E q k−1so that the pairing value is defined uniquely.We write x(i) for x p i.We consider a hyperelliptic curve H d over F q defined by y2=x p−x+d,d=±1,for p≡3 (mod4),where q=p n with gcd(2p,n)=1,and we let F/F q and K/F q be the extensions of degree [F:F q]=p and degree[K:F q]=2p,respectively.Over the extensionfield K,the curve is the quotient of a hermitian curve,hence it is Hasse-Weil maximal.And the class group over K is annihilated by p pn+1;this can be also seen from the following Lemma1.1.It shows that for P∈H d(K),(p pn+1)((P)−(O))is principal[8].Lemma1.1([8]).Let P=(α,β)∈H d.The functionh P=βp y−(αp−x+d)p+12has divisor(h P)=p(P)+(P )−(p+1)O,where P =(α(2)+2d,β(2)).From Lemma1.1,we observe that p((P)−(O))≡([p]P)−(O),thus the multiplication by p over H d has an extremely special form such as[p]=φπ2,whereφ=(x+2d,−y)andπis a Frobenius map of p th power.Let m=(n+1)/2,then from[8]we have|J H+1(F q)|=(1+p n)3+(pn)p m(1+p n+p2n),|J H−1(F q)|=(1+p n)3−(pn)p m(1+p n+p2n).(1)1.1Eta pairing on H dWe discuss the Eta pairing introduced in[2]which is very useful for efficient computation of the Tate pairing.We consider a hyperelliptic curve H d over somefinitefield F p n,and letψbe an endomorphism on the curve H d given byψ:H d(K)→H d(K),ψ(x,y)=(ρ−x,σy),(2) whereρ∈F is a root ofρp−ρ+2d=0,andσ,¯σ∈K are the roots ofσ2+1=0.For efficient Tate pairing computation,we concern with the twisted Tate pairingˆt:JH d [ ]×J Hd(F p2pn)/ J Hd(F p2pn)−→F∗p2pnˆt(D,E)=fD(ψ(E))p pn−1,3where(f D)=(p pn+1)D from[9,Theorem4].For two divisors D and E in J Hd,the Eta pairing is defined byη(D,E)=n−1i=0h Di(ψ(E))p n−1−i,(3)where D i+1+(h Di )=pD i with a divisor D0=D and some rational function h Di.By Lemma1.1,H d has a property thatq(P)−q(O)=(γ(P))−(O)+(g P),(4) for some automorphismγon H d and some function g P.Thusγcan be given byγ=φnπ2n.The following theorem is crucial for efficient computation of the Tate pairing on divisors.Theorem1.2([2],[20]).Let q=p n,p≡3(mod4),γ=φnπ2n on J Hd induced from Eq.(4),andψbe an endomorphism on the curve H d over F q.Assume thatφnψ[q]=ψ,(5) whereψ[q]denotes a map obtained by raising the coefficients ofψby q th power.Then for divisors D and E in J H(F q),we haveη(qD,E)=η(D,E)q.For any divisor E=[U E,V E]in J Hd (F q),the endomorphismψin Eq.(2)on divisors are easilydeduced as follows:ψ(E)=[Uψ(E),Vψ(E)],whereUψ(E)=x3−(3ρ+u E,2)x2+(3ρ2+2u E,2ρ+u E,1)x−(ρ3+u E,2ρ2+u E,1ρ+u E,0),Vψ(E)=σ(v E,2x2−(2ρv E,2+v E,1)x+v E,2ρ2+v E,1ρ+v E,0).(6)Using Eq.(6),a straightforward verification shows that H d satisfies the crucial condition in Eq.(5). From Theorem1.2,it thus follows thatˆt(D,E)=η(D,E)76n+1(77n−1).(7)It is therefore enough to computeη(D,E)to obtainˆt(D,E)for any divisors D,E∈J Hd (F q).When all the points in support(D)and support(E)are F q-rational points,using Eq.(7)makes the Tate pairing computation very efficient as mentioned in[2].In Section2,we will extend the concept of the Eta pairing on the general divisors,that is,the supports of D and E are not necessarily F q-rational points.Throughout this paper,we focus on the hyperelliptic curve H d:y2=x p−x+d,d=±1,p≡3 (mod4)of genus g=3,therefore we work on the case p=7;this case is cryptographically useful[9]. 2Pointwise computation of the Tate pairingThis section presents a generalization of the pointwise method developed in[2]and[9],and this method can be used for any divisors,not only for F q-rational points.The Eta pairing is used for reducing the computation cost as well.As mentioned in Eq.(7),for divisors D,E in J Hd,the Tate pairing can be computed byˆt(D,E)=η(D,E)76n+1(77n−1),(8)4where D and E have the form D=(P1)+(P2)+(P3)−3(O),E=(Q1)+(Q2)+(Q3)−3(O)for points P k and Q j contained in H d(F73n)with k,j=1,2,3.From Eq.(3)we haveη(D,E)=n−1i=0h Di(ψ(E))7n−1−i.For i≥1,let D i=(P i,1)+(P i,2)+(P i,3)−3(O),then h Di(ψ(E))can be computed byh Di (ψ(E))=3k,j=1h Pi,k(ψ(Q j)),(9)where(h Pi,k )=7(P i,k)+(P i,k )−8(O),P0,k=P k,P i,k=(α(2i)+i2d,(−1)iβ(2i))∼7i[P0,k]and[Pi,k]=−[7P i,k]for i≥1.Algorithm1shows the pointwise computation of Tate pairing. Algorithm1Pointwise computationINPUT:D,E∈J Hd (F7n)OUTPUT:ˆt(D,E)1.g←1pute P k=(αk,βk),k=1,2,3and Q j=(x j,y j),j=1,2,3which are supporting points for D and E,respectively.3.For i=0to n−1do4.For k,j=1to3dopute h k,j=β7k ·y j·σ−(α7k+x j+d−ρ)46.setαk←α72k +2d,βk←β72k7.set g←g7· 3k,j=1h k,j8.Return g76n+1(77n−1),where g=η(D,E).Let m3(resp.M3,M)be the time cost for a multiplication in F73n(resp.F73(14n),F714n). For simplicity,we assume that a squaring cost is similar to a multiplication cost,and we omit the computation cost for7th powering since it is negligible compared with the other operations.Step5requires two multiplications and two squarings in F73n,and Step7needs eight multipli-cations in F73(14n)and one multiplication in F714n.For computingˆt(D,E),the total complexity is thereforeT P:=2T3rt+n(9·4m3+8M3+1M)=2T3rt+n(36m3+8M3+1M),(10) where T3rt is the time forfinding all the roots of a cubic polynomial over F73n;this is required for obtaining the supporting points of D and E.3Computation of the Tate pairing by using the resultantIn this section,our goal is,for given divisor inputs with the divisor representation,tofind an efficient algorithm which provides us thefinal Tate pairing value over H d.For evaluating a function at a5divisor,we apply the resultant for the efficient computation of the Tate pairing,and show that this approach is much faster than thefirst method.According to Eq.(7),for the Tate pairing computation over divisors D,E∈J H(F7n),it is sufficient to computeη(D,E).In the following subsections3.1and3.2,to obtain the value of η(D,E),wefind the explicit formulas for D i=[7i]D and h Difor i≥1,and we also obtain the evaluation formula of rational function h Diat a divisor in a very explicit way.3.17-multiplication on divisorsLet D be a reduced divisor of H d such thatD=(P1)+(P2)+(P3)−3O=[U D,V D],where P j=(αj,βj)for j=1,2,3,U D=x3+u D,2x2+u D,1x+u D,0,and V D=v D,2x2+v D,1x+v D,0∈F7n[x].Let D0=D,D i+1+(h Di )=7D i,and D i=[U Di,V Di]for each positive integer i.The following lemma provides us with explicit formulas for U Di and V Diin terms of the coef-ficients of U D and V D for i≥1.The proof can be obtained from the knowledge of Section5in Appendix of[17].Lemma3.1.Let[7]be the multiplication map by7on the divisor class group of H d/F7n.Thenwe have,for i≥1,[7i]D=D i=[U Di ,V Di]withU Di =x3+(u(2i)D,2+id)x2+(u(2i)D,1+3idu(2i)D,2−2i2)x+u(2i)D,0−2idu(2i)D,1−3i2u(2i)D,2−i3d,V Di =(−1)i v(2i)D,2x2+(−1)i(3idv(2i)D,2+v(2i)D,1)x+(−1)i(−3i2v(2i)D,2−2idv(2i)D,1+v(2i)D,0).In the following proposition,wefind the function h D such that(h D)=7D+D in an explicit way.Proposition3.2.Let h D(x,y)be a function such that(h D)=7D+D ,andτbe a mapτ:H d→ˆH d,(x,y)→(ˆX,Y)=(x−ξ7−d,y).Then,for appropriateξ,we haveˆh ˜D(ˆX,Y):=hD(x,y)◦τ−1=δ1Y3+s(ˆX)Y2+t(ˆX)Y+δ16(ˆX),whereδ16(ˆX)=−(ˆX3+˜u71ˆX+˜u70)4,andδ1,s(ˆX)and t(ˆX)are described in Table5of Appendix. Proof.Let D=(P1)+(P2)+(P3)−3(O),and7((P j)−(O))=(h j)−(P j)+(O)for j=1,2,3. Then7D=(h1h2h3)−[(P 1)+(P 2)+(P 3)−3(O)]=(h D)−D ,where D =(P 1)+(P 2)+(P 3)−3(O).For simplicity,the change of variableτξ:x→X=x−ξ,y→Y=ywithξ=−u D,23transforms the curve H d to a curve˜H d:Y2=X7−X+(ξ7−ξ+d).6Let P j=(αj,βj),˜P j=(αj−ξ,βj),˜αj=αj−ξand˜βj=βj.From the fact thatβj=V D(αj)and˜βj=V˜D (˜αj)=V˜D(αj−ξ),it follows that U˜D=x3+˜u1x+˜u0and V˜D=˜v2X2+˜v1X+˜v0.We also have˜D=(˜P1)+(˜P2)+(˜P3)−3(O)=[X3+˜u1X+˜u0,˜v2X2+˜v1X+˜v0].Furthermore, (˜h j)=7(˜P j)+(˜P j )−8(O),where˜h j=h j(X+ξ,Y).Lettingθ=ξ7−ξ+d,it is easy to see that˜hj=˜βj7Y−(˜αj7−X+θ)4=(˜v2˜αj2+˜v1˜αj+˜v0)7Y−(˜αj7−X+θ)4.Thus we obtainh˜D(X,Y)=˜h1(X,Y)˜h2(X,Y)˜h3(X,Y)=3j=1(˜v2˜αj2+˜v1˜αj+˜v0)7Y−(˜αj7−X+θ)4.(11)If we apply the Elimination method in[7]to Eq.(11)with elimination order{˜α1,˜α2,˜α3}>{˜u1,˜u0},then we can obtain Eq.(11)as a function of˜u1and˜u0.The coefficients forˆh˜D (ˆX,Y)=h˜D (X−θ,Y)are described in Table5,where the second column shows the corresponding coefficientin terms of˜v i s and˜u is.3.2Evaluation at a divisorIn this subsection,we use resultant to evaluate a rational function at a divisor,which is necessary to achieve our goal.For the definition of resultant and its properties,we refer to[27,Ch.VI]. Theorem3.3.Let F be afield.For A,B∈F[x]with deg A=m,deg B=n,we haveres(A,B)=a nmi=1B(αi),whereα1,α2,···,αm∈¯F(=algebraic closure of F)are all the roots of A and a is the leading coefficient of A.With the same notations as in Theorem3.3,furthermore,we haveres(A,B)=(−1)mn res(B,A).(12)In addition,efficient reduction method for computing the resultant is also introduced in[27,Ch. VI].When m≥n,by Euclidean division algorithm,there exists Q(x),R(x)∈F(x)such that A(x)=Q(x)B(x)+R(x)with deg R<n.Thenres(A,B)=(−1)mn res(B,R).(13)Now we are ready to apply the resultant to our Tate pairing computation.Lemma3.4.For h D(x,y)and E=[U E,V E],we let H D,E(x)=h D(x,V E(x)).Then we haveh D(E)=res(U E,H D,E).Proof.In fact,h D(E)=H D,E(x1)H D,E(x2)H D,E(x3),where x i’s are the roots of U E(x).The assertion thus follows immediately from Theorem3.3.7Algorithm2Tate pairing computation by using resultantINPUT:D=[U D,V D],E=[U E,V E]∈J Hd (F7n),endomorphismψOUTPUT:ˆt(D,E)1.Setξ←2u D,2andθ←ξ7−ξ+d.pute u1=3ξ2+2ξu D,2+u D,1and u0=ξ3+u D,2ξ2+u D,1ξ+u D,0.puteδj for j=1,...,15using Table54.g←1,5.for i=0to n−1doputeˆE=τξ+θ(ψ(E))pute H˜D,ˆE =ˆh˜D(x,VˆE)and R=H˜D,ˆE(mod UˆE)(Table6).pute h Di (ψ(E))=res(UˆE,R).9.g←g7·h Di(ψ(E))10.set u0←u720,u1←u72111.setξ←ξ72,θ←θ72,δj←δ72j if j=2,3,4,5,6,andδj←(−1)iδ72j otherwise.12.Return g76n+1(77n−1),g=η(D,E).Table6of Appendix describes the nonzero coefficients of H D,E(x),and the complexity is counted by using Karastuba’s technique[15].Now by using the reduction method in Eq.(13),we can compute res(U E,H D,E)as follows: Lemma3.5.Let H D,E(x)=Q(x)U E(x)+R(x)with deg R≤2.Then we haveh D(E)=res(U E,R).Proof.We observe that the degree of H D,E is12and the degree of U E is3.Thus by using Eq.(12),we have res(U E,H D,E)=res(H D,E,U E).From Eq.(13)it follows that res(H D,E,U E)= res(UE,R),so we get res(U E,H D,E)=res(U E,R).3.3Algorithm for the Tate pairing computation by using the resultantIn this subsection,we describe an algorithm for computing the Tate pairing on divisors,and we also compute its complexity.From Lemma3.1,Proposition3.2and Lemma3.4,the Tate pairing given inEq.(7)can be computed by using Algorithm2.Since vˆE,j =σ·(some element in F77n),j=0,1,2,we note that H˜D,ˆEin the step7of Algorithm2can be written asH˜D,ˆE =−x12+10i=0(d iσ+e i)x i,d i,e i∈F77n for0≤i≤10.Tofind H˜D,ˆE (mod UˆE)in the step7,we use the following recursive relations:x i≡a i x2+b i x+c i(mod U E),3≤i≤12a3=−uˆE,2,b3=−uˆE,1,c3=−uˆE,0∈F77na i=a i−1a3+b i−1,b i=a i−1b3+c i−1,c i=a i−1c3.Then R can be computed by8R=H˜D,ˆE (mod UˆE)=(a12+10i=3a i(d iσ+e i)+d2σ+e2)x2+(b12+10i=3b i(d iσ+e i)+d1σ+e1)x+(c12+10i=3c i(d iσ+e i)+d0σ+e0).(14)Now we discuss the complexity of Algorithm2by counting the number of operations which are necessary for computingη(D,E).We denote the time for multiplications in F714n,F77n and F7n by M,m and m,respectively,and a multiplication between F7n and F77n by˜m.Notingthat,in Step6,uˆE,j ,j=0,1,2and vˆE,0,vˆE,1belong to F77n,and from Eq.(6)we have vˆE,2=σ·(some element in F7n).The computation cost of H˜D,ˆE =ˆh˜D(x,VˆE)in Step7is counted inTable6.We need7m+18m for computing x i(mod U E)since we do not need the computation x11,and we need48m to compute R in Eq.(14).The total complexity of this algorithm is therefore40m+n(29m+31˜m+70m +T res+1M),(15)where T res is the computation cost for the resultant res(UˆE ,R)of UˆEand R in F714n.In detail,we need3m in the step2,and37m in the step3from Table5.For each loop,we need5m in the step6,17m+31˜m+4m in the step7from Table6,and1M in the step9.We calculate the resultant by computing the determinant of two polynomials with degree2 and3in Mumford representation.Then we have T res=48m ,where m is a multiplication(resp. squaring)in F77n.4Complexity comparisonIn this section we compare the complexities of our two methods given in Section2and3.When an extension degree is of the form k=2i3j,the computation cost for a multiplication in F q k is theoretically3i5j times of the cost for a multiplication F q([16],[18]).From this observation, we assume that1mult.in F73n(m3)≈5m,1mult.in F73(14n)(M3)≈5M,1mult.in F714n(M)≈3m (16)and we also let˜m≈7m.With the above assumptions,the pointwise computation cost in Eq.(10) is T P:=2T3rt+n(36·5m+123m ),where T3rt is the time forfinding all the roots of a cubic polynomial over F73n.By Berlekamp-Rabin algorithm[3],we have T3rt=O(32log3log73n)·5m≈27n·4·m3=108nm3.Counting the cost for T3rt,wefinally haveT P≈n(1260m+123m ).(17)On the other hand,the total time for the resultant method in Eq.(15)is T R:=40m+n(246m+ 70m +T res+1M),where T res is the time for computing the resultant of two polynomials over F714n.As mentioned in Section3.3,we have T res=48m ,where m is a multiplication in F77n. Thus,the computation cost of our resultant approach is approximatelyT R=40m+n(246m+121m ).(18)9Table1:Complexity comparison:examplessecurity(bits)80128192 bitlength of714n114030728192 n2979211 pointwise(T P)36540m+3567m 99540m+9717m 265860m+25953m resultant(T R)7174m+3509m 19474m+9559m 51946m+25531mT P T R 1.17982≤T PT R≤1.938081.17998≤T PT R≤1.939631.18004≤T PT R≤1.94019To compare the complexities of two methods,we summarize T P,T R and the ratio T P/T R in Table1,where the examples are chosen for cryptographically meaningful values[18].According to[16],the ratio of m and m is7≤mm≤49,and the last row of Table1showsthe range of the ratio of T PT R for eachfixed value of n.For each n,as m /m is decreasing,the ratioT P T R is increasing.This implies that as the performance of m ,the multiplication in F77n,is gettingmore efficient,the resultant method gets more efficient than the pointwise method.Furthermore,we observe that when m /m isfixed,as n is increasing,T PT R is also increasing.Thus,for highersecurity level,the resultant method gives better efficiency than the pointwise method.Therefore, we can conclude that the Tate pairing computation by using the resultant is48.5%faster than the pointwise computation in the best case and15.3%faster in the worst case.5Experimental resultsWe have proposed two methods by the resultant and pointwise approach for computing the Tate pairing over the genus3hyperelliptic curve H d:y2=x7−x+d,d=±1over F q.In Section4,we compared the complexities of two proposed methods,and it turned out that the resultant approach is up to48.5%faster than the pointwise approach.In this section,we provide experiment results for the Tate pairing computation over the genus3hyperelliptic curve and compare the running time. Basically our goal in this experimentation is that we verify our theoretical complexity comparison in Section4by actual implementation using one of the standard packages such as NTL.We make implementations when both input divisors D and E are general divisors,and we use the NTL software package.We provide implementation for genus3hyperelliptic curves for thefirst time.Wefirst need tofind a prime n for each security level s such that2s≈73n,and alsofind a largeprime dividing|J Hd (F7n)|such that ≈2s.The formula for|J Hd(F7n)|is given in Eq.(1).Bysearching for good candidates for and n from n=29through n=79,wefind the four values of n,namely,29,43,47and73with corresponding primes as given in Appendix.Table2shows the amount of time to perform thefield multiplications in F7n,F73n and F77n using NTL.The table was computed by taking average time of5000multiplications of random elements in eachfield.In Section4,we assumed the ratio m3/m is5for thefield operations m3in F73n and m in F7n.However,in NTL the actual ratio m3/m is approximately7or9as shown in Table2,and m /m in Table2is in the range7≤m /m≤49as we expected.In our implementation M3 is optimized to56m3.Therefore,each complexity for the Tate pairing computation is given by T R=40m+n(246m+121m )andT P=2T3rt+n(36m3+8M3+1M)=2T3rt+n(36m3+56·8m3+3m )≈n(700m3+3m ).10Table2:Multiplication timings(in milliseconds)n29434773F7n(m)0.25620.56860.6626 1.6062F73n(m3) 2.4 4.3218 4.890611.1562F77n(m )7.843816.67217.515627.8688m3/m9.367687.600777.38092 6.94571m /m30.615929.321126.434717.3508According to the actual ratio of thefield operations in NTL,Table1is adjusted to obtain Table3.As shown in Table3,for n≥43,as n increases,T P/T R also increases as we expected in Section4. On the other hand,when n increases from29to43,T P/T R decreases,which is opposite to what we expected,and we guess that the reason is the following:For instance,we observe that when n changes from29to43,the decrement of m3/m(resp.m /m)is1.767(resp.1.295).On the other hand,when n changes from43to47,the decrement of m3/m(resp.m /m)is0.220(resp.2.886). So,the decrement of m3/m is much larger than m /m when n changes from29to43,while m3/m is much smaller than m /m when n changes from29to43.From Table3,the resultant method is40.57%(resp.29.38%,34.32%,and52.26%)faster than the point-wise method for n=29(resp.43,47,and73).These examples support our theoretical complexity analysis in Section4,that is,for higher security level the resultant method is more efficient than the pointwise method for the Tate pairing computation.Table3:Complexity comparison:examples in NTLbitlength of714n1140169018472869 n29434773 pointwise(T P)20300m3+87m 30100m3+129m 32900m3+141m 51100m3+219m resultant(T R)7174m+3509m 10618m+5203m 11602m+5687m 17998m+8833m T PT R1.68254 1.42525 1.522572.09465Table4shows the implementation results of the Tate pairing for selected examples.The resul-tant method is48.8%(resp.39.1%,38.7%,and43.4%)faster than the pointwise method for n=29 (resp.43,47,and73).We performedfifty calculations with random samples for each method and took the average time.The experiments ran on a machine with2.2Ghz Opteron,and we used Microsoft Visual C++6.0.Our implementation shows that the performance ratio T PT R for n=29is larger than the ratiofor n=73,while the theoretical complexity analysis in Table3shows the other way around.This difference occurs because of the relative time cost T3rtT Pfor computing all the supporting pointsof an input divisor.In more detail,in the theoretical complexity analysis,for T3rtT Pwe have aflat ratio approximately0.152.On the other hand,in our implementation,T3rtT Pis0.447242(resp.0.436616,0.41533,and0.170231)for n=29(resp.43,47,and73).Thus the ratio T3rtT P is variousdepending on the values of n,and in fact,the ratio is largest when n=29and smallest when11Table4:Experiment results(in seconds)bit-length of 237338373608bit-length of714n1140169018472869n29434773pointwise method(T P)38.356499.2936120.672399.962resultant method(T R)19.631560.462273.9278226.412T P1.95382 1.64224 1.63229 1.76652T Rn=73.According to the theoretical complexity analysis and the implementation,we conclude that the resultant method is faster than the pointwise method for the Tate pairing computation.Conclusions.In this paper,we have provided two methods by pointwise approach and resul-tant approach for computing the Tate pairing over divisor class groups of the hyperelliptic curves H d:y2=x p−x+d,d=±1of p=7.From the theoretical analysis of the complexity,the resultant method is48.5%faster than the pointwise method in the best case and15.3%faster in the worst case,and our implementation results also support our theoretical analysis of the complexity.There is room for further optimization in the implementation,and using NTL might not be the best choice.However,our implementation is sufficient enough to conclude that the resultant method is more efficient than the pointwise method in the Tate pairing computation.References[1]P.S.L.M.Barreto,H.Y.Kim,B.Lynn,M.Scott,Efficient Algorithms for Pairing-BasedCryptosystems.Advances in Cryptology–Crypto2002,Lecture Notes in Computer Science, Vol.2442,Springer-Verlag,(2002)354–368.[2]P.S.L.M.Barreto,S.Galbraith, C.hEigeartaigh and M.Scott,Efficient Pairing Com-putation on Supersingular Abelian Varieties,Cryptology eprint Atchives,Available at ,2004,No.2004/375.[3]E.R Berlekamp,Factoring polynomials over largefinitefields,p.,Vol24,(1970)713-735.[4]D.Boneh and M.Franklin,Identity-based encryption from the Weil pairing.Advances inCryptology,Crypto2001,Lecture Notes in Computer Science,Vol.2139,Springer-Verlag, (2001)213-229.[5]J.C.Cha,J.H.Cheon,An Identity-Based Signature from Gap Diffie-Hellman Groups.Pro-ceedings of PKC,Lecture Notes in Computer Science,Vol.2567,(2003)18-30.[6]Y.Choie and E.Lee,Implementation of Tate pairing on hyperelliptic curves of genus2,Information security and cryptology—ICISC2003,97–111,Lecture Notes in Comput.Sci., 2971,Springer,Berlin,(2004).12。