text:
# Non-equilibrium Born-Oppenheimer potential energy surfaces for molecular wires

## Abstract

We present a method for computing non-equilibrium, current-dependent Born-Oppenheimer potential energy surfaces for molecular wires. Calculations are performed for polyacetylene wire described by tight-binding model with electron-phonon interactions. We find that dimerization of the polyacetylene wire is amplified by electric current flow. We show that the boundary between transparent and opaque black states of the wire is blue-shifted by current.

One of the major goals in modern nanotechnology is the construction of an electronic circuit in which molecular systems act as conducting element nitzan03 . Two critical issues should be thoroughly investigated to proceed with the design of real molecular devices: heating in a molecular junction and current induced conformational changes of a junction caused by electromigration. By the inelastic scattering of electrons the kinetic energy of current is transfered to the nuclear vibrations and then it is released as heat. The second process, electromigration, is the phenomenon of atom motion due to current induced forces and it is related to the transfer of electronic momentum to nuclei due to both elastic and inelastic scattering. The electromigration can lead to device breakdown at critical values of current and therefore current-induced forces may present a limitation for the development of molecular electronic devices. Very recently, controlled electromigration has been used constructively to make a single-molecular junction liang02 . Both issues, heating and electromigration, are ultimately related to understanding how Born-Oppenheimer (BO) potential energy surface of a molecular wire is responded to electronic current flow. If current-dependent BO potential energy surface of a molecular device is available, we can compute current-induced forces as the corresponding gradients as well as we can perform the normal modes analysis to obtain the current-dependent vibrations.

Although the practical importance of a current-dependent BO surface can not be underestimated, some intricate theoretical questions connected to the difficulty in defining a generic variational energy functional for non-equilibrium steady state systems todorov00 ; diventra00 ; emberly01  can be also puzzled out. Theoretical work to date has failed to define or even to prove the existence of the BO potential energy surface for molecular wires with current flow. The principle theoretical difficulty is the treatment of the transport problem as an electron transmission (Landauer approach landauer70 ) which is non-variational from the outset. A wire with current is by definition an open quantum system and as long as one works within a non-variational transport theory it is likely not possible to comprise a geometrical optimization of the nuclear degrees of freedom with electronic transport calculations within a single theoretical approach. There is the opinion that current induced forces can not be conservative sorbello98  although validity of this claim has been recently questioned diventra03 . If a current induced force is not conservative then there does not exist a BO potential energy surface of which this force might be derivative. One of the goals of this Letter is to show that this is not true and that the Born-Oppenheimer potential energy surface can be properly defined and efficiently computed in the presence of current flow.

The Lagrange multiplier based transport theory kosov02 ; kosov03-jcp  takes its origin in the modern development of steady state non-equilibrium statistical mechanics antal97 ; antal99 ; eisler03 . This theory is equivalent to a variational formulation where the constrained minimization of the expectation value of the Hamiltonian on the manifold of the desired current $`J`$ yields the transport properties kosov02 . The “algorithm” of the Lagrange multiplier based transport theory to compute a current-dependent BO surface can be summarized as follows: (1) define the operator of the current $`J`$ via the continuity equation; (2) extend the Hamiltonian $`H`$ by adding the term ($`\lambda J`$) where $`\lambda `$ is a Lagrange multiplier; (3) compute the BO surface as the expectation value $`0(\lambda )|H|0(\lambda )`$ where $`|0(\lambda )`$ is the “ground state” of the extended Hamiltonian $`H\lambda J`$.

In this Letter, using the Lagrange multiplier based transport theory we compute the current-dependent BO potential energy surfaces of conjugated polymer, polyacetylene, wire. Polyacetylene is a linear polymer, it consists of coupled chain of $`CH`$ units forming a quasi-one-dimensional lattice. Each $`C`$ has four valence electrons: two of them contribute to the $`\sigma `$-type bonds connecting neighboring carbons along the one-dimensional backbone, while the third forms a bond with the the hydrogen. The remaining electron has the symmetry of a $`2p_z`$ orbital and contributes to $`\pi `$-bond. In terms of the energy band description, the $`\sigma `$-bonds form low-lying completely filled band, while $`\pi `$-bond leads to half-filled energy band responsible for electron transport properties. The $`\pi `$-electrons can to a fair approximation be treated as a quasi-one dimensional electron gas within the tight-binding approximation. Accordingly, we start our consideration from the following model electronic Hamiltonian for the polymer chain

$`H`$ $`=`$ $`{\displaystyle \underset{n\sigma }{}}(t_o+(1)^n\alpha x)(a_{n+1\sigma }^{}a_{n\sigma }+a_{n\sigma }^{}a_{n+1\sigma })`$ (1)
$`+`$ $`2NKx^2.`$
Here $`a_{n\sigma }`$ creates an electron of spin $`\sigma `$ on site $`n`$. The Hamiltonian $`H`$ is based upon the so called Su-Schrieffer-Heeger (SSH) heeger88  model for the band-structure of trans-(CH)n lattices. The first term in the $`H`$ gives the energy for an electron with spin $`\sigma `$ to hop between neighboring $`p_z`$-orbitals. The strength of this term is modulated by linear coupling to distortions $`x`$ in the polymer lattice away from evenly spaced lattice positions. Finally, the last terms in $`H`$ gives the harmonic interactions between lattice-sites arising from the $`\sigma `$-bonds between neighboring lattice atoms.

We begin the derivation by defining the operator of current via continuity equation. The number of electrons on the site $`n`$ is given by the expectation value of the operator

$$N_n=\underset{\sigma }{}a_{n\sigma }^{}a_{n\sigma }.$$
(2)
By making use of the Heisenberg representation the continuity equation can be written as the Heisenberg equation-of-motion for the operator $`N_n`$:

$$\dot{N_n}=i[H_o,N_n].$$
(3)
Given standard anti-commutation relations between the electron creation and annihilation operators, the r.h.s. commutator (3) can be readily computed. Comparing eq.(3) with the finite difference expression for continuity equation $`\dot{N_n}=(j_nj_{n1})`$ we obtain the definition of the operator of current through site $`n`$. By making the sum of on-site currents $`j_n`$ along the wire we define the net, macroscopic current through the wire

$$J=i\underset{n\sigma }{}(t_o+(1)^n\alpha x)(a_{n+1\sigma }^{}a_{n\sigma }a_{n\sigma }^{}a_{n+1\sigma }).$$
(4)
There are two distinct contributions to the net current. The term $`t_o(a_{n+1\sigma }^{}a_{n\sigma }a_{n\sigma }^{}a_{n+1\sigma })`$ is the standard for molecular wires without electron-phonon coupling whereas the term $`(1)^n\alpha x(a_{n+1\sigma }^{}a_{n\sigma }a_{n\sigma }^{}a_{n+1\sigma })`$ is the phonon-assisted current.

We assume now that there is a time-independent, constant current through the wire. A homogeneous current-carrying state is the same whether it is introduced by reservoirs or by a bulk driving driving field, the current enters the problem via a Lagrange multiplier $`\lambda `$. To this end the Hamiltonian $`H`$ is modified by adding the term which constraints the macroscopic current $`J`$:

$$H_J=H\lambda J.$$
(5)
The Hamiltonian $`H_J`$ is a quadratic form in fermion creation/annihilation operators. This quadratic form can be exactly diagonalized by two unitary transformations. The Fourier transformation

$$a_{n\sigma }=\frac{1}{\sqrt{N}}\underset{k}{}\mathrm{exp}(ikn)c_{k\sigma },$$
(6)
brings the Hamiltonian (5) to the following form

$`H_J={\displaystyle \underset{0k<2\pi }{}}{\displaystyle \underset{\sigma }{}}\left(c_{k+\pi \sigma }^{}c_{k\sigma }^{}\right)\left(\begin{array}{cc}ϵ_k& \mathrm{\Delta }_k\\ \mathrm{\Delta }_k& ϵ_k\end{array}\right)\left(\begin{array}{c}c_{k+\pi \sigma }\\ c_{k\sigma }\end{array}\right).`$ (11)
We have introduced here the phonon-unperturbed band energy

$$ϵ_k(\lambda )=2t_0(\mathrm{cos}(k)+\lambda \mathrm{sin}(k)),$$
(12)
and the phonon-induced gap

$$\mathrm{\Delta }_k(\lambda ,x)=4\alpha x(\mathrm{sin}(k)\lambda \mathrm{cos}(k)).$$
(13)
Both quantities, $`ϵ_k(\lambda )`$ and $`\mathrm{\Delta }_k(\lambda ,x)`$ depend upon current via the Lagrange multiplier $`\lambda `$ and if we let $`\lambda `$ tend to zero we recover the usual zero-current results heeger88 . Mixing $`c_{k\sigma }`$ and $`c_{k+\pi \sigma }`$ operators by the canonical Bogoliubov transformation

$`\left(\begin{array}{c}\alpha _{k+\pi \sigma }\\ \alpha _{k\sigma }\end{array}\right)=\left(\begin{array}{cc}u_k& v_k\\ v_k& u_k\end{array}\right)\left(\begin{array}{c}c_{k+\pi \sigma }\\ c_{k\sigma }\end{array}\right),`$ (20)
we obtain new quasipaticles $`\alpha _{k\sigma }`$ and $`\alpha _{k+\pi \sigma }`$. The coefficients of the Bogoliubov transformation is chosen in such a way that the extended Hamiltonian (11) should be diagonal. It leads to the following expressions for the coefficients

$$u_k=\sqrt{\theta (ϵ_k)}\mathrm{cos}(\varphi _k)\sqrt{1\theta (ϵ_k)}\mathrm{sin}(\varphi _k),$$
(21)
$$v_k=\sqrt{\theta (ϵ_k)}\mathrm{sin}(\varphi _k)+\sqrt{1\theta (ϵ_k)}\mathrm{cos}(\varphi _k),$$
(22)
where $`\theta (ϵ_k)`$ is the Heaveside step function and the mixing angle $`\varphi _k`$ is given by the formula $`\varphi _k=1/2\mathrm{arctan}(ϵ_k/\mathrm{\Delta }_k)`$. This canonical Boguluibov transformation produces the non-interacting Hamiltonian for the quasiparticles $`\alpha _{k\sigma }`$ and $`\alpha _{k+\pi \sigma }`$:

$`H_J`$ $`=`$ $`{\displaystyle \underset{0k<\pi }{}}{\displaystyle \underset{\sigma }{}}E_k(\alpha _{k+\pi \sigma }^{}\alpha _{k+\pi \sigma }\alpha _{k\sigma }^{}\alpha _{k\sigma })`$ (23)
$`+`$ $`2NKx^2,`$
with the wave-vector $`k`$ in the reduced Brillouin zone of the system. The band energy, $`E_k=\sqrt{ϵ_k^2+\mathrm{\Delta }_k^2}`$, and the mixing angle $`\varphi _k`$ in the canonical Bogoliubov transformation are functions of the phonon-unperturbed band energy, $`ϵ_k(\lambda )`$, and the phonon-induced energy gap, $`\mathrm{\Delta }_k(\lambda ,x)`$.

It can be straitforwardly shown that this diagonalization of the Hamiltonian is equivalent to the variational problem $`\delta H\lambda J=0`$ with the coefficients of the Bogoliubov transformation $`u_k`$ and $`v_k`$ as variational parameters. Current carrying steady states are by definition the ground states of extended, current dependent Hamiltonian $`H_J`$ kosov02  . The ground state of the Hamiltonian (23) can be defined as the vacuum state for quasiparticle $`\alpha _{k+\pi \sigma }`$ and $`\alpha _{k\sigma }^{}`$. All physical properties of the system depend upon the current and can be obtained as the matrix element of the corresponding operators over the current carrying “ground state” $`|0(\lambda )`$. Now the non-equilibrium Born-Oppenheimer potential energy surface is defined as the expectation value of the original Hamiltonian $`H`$ (1) over the current carrying wave function:

$`E_{BO}(\lambda ,x)=0(\lambda )|H|0(\lambda )`$
$`=2{\displaystyle \underset{0k<\pi }{}}E_k(\lambda ,x)+2NKx^2`$ (24)
The band energy $`E_k`$, the mixing angles $`\varphi _k`$, and the current carrying wave function $`|0(\lambda )`$ are not yet in a form to be computed as the Lagrange multiplier $`\lambda `$ is not known yet. The additional equation for the Lagrangian multiplier $`\lambda `$ is obtained if the density of an expectation value of the net current operator (4) over the current carrying state of the Hamiltonian (23) is required to yield a desired current density $`I`$. This sets up the continuity equation:

$$\frac{1}{N}0(\lambda )|J|0(\lambda )=\frac{2}{N}\underset{0k<\pi }{}(2\theta (\epsilon _k)1)\left(2t_0\mathrm{sin}(k)\mathrm{cos}(2\varphi _k)+4\alpha x\mathrm{cos}(k)\mathrm{sin}(2\varphi _k)\right)=I$$
(25)
For any given lattice distortion $`x`$ the nonlinear equation (25) should be resolved for $`\lambda `$. Then the band energy and the mixing angle $`\varphi _k`$ of the canonical Bogoliubov transformations are computed as functions of current.

We now discuss the main results obtained using the above model. The numerical calculations are performed for the half-occupied conductance band with the box length $`N=1000`$. In all our calculations we use the following model parameters of the SSH model ness01 : $`t_o=2.5`$ eV, $`\alpha =4.1`$ eV, and $`K=21`$ $`eV/\stackrel{̊}{A}^2`$. This parameterization of the ASH Hamiltonian is typically used to describe coherent electron transport in polyacetylene wire ness01 .

In the first calculations, shown in Fig.1, we studied the changes of the BO surface as current flows through the wire. It is immediately evident from Fig.1 that the current substantially alters the Born-Oppenheimer potential energy surface of the polyacetylene wire. The minima on the BO surface correspond to the optimal non-equilibrium steady state geometries of the wire. The dimerization coordinate increases as current flows, i.e. the $`C=C`$ double bonds are shortened and the $`CC`$ single bonds are elongated by the current induced forces. By increasing the current we also increase the barrier between the two-fold degenerate ground states, therefore the energy difference between evenly spaced polyacetylene and dimerized polyacetylene is increased as we increase the current. Since SSH Hamiltonian is very general and applicable in its present formulation to any long semiconductor wires we do expect that effect of the current-amplified dimerization occurs in other quasi-one-dimensional wires as well. The results of our calculations are qualitatively consistent with the finding of Todorov, Hoekstra and Sutton todorov01  that current-induced forces generally form an alternating patterns in atomic wires. The critical value of the current at which the current induced forces break the wire into pieces can be also determined. If we assume that the current-induced bond distortion larger than 0.2$`\stackrel{̊}{A}`$ will be sufficient to rupture the wire, the critical value of the current which the polyacetylene wire can sustain is 0.8 mA.

Finally, we turn our attention towards what physical quantities which are accessible experimentally can be used to monitor the current-amplified polyacetylene dimerization. To this end we compute the response of the band structure of polyacetylene to current flow. The current-dependent band structure of the first Brillouin zone is plotted in Fig.2. Polyacetylene’s band is half occupied therefore the states with negative $`E_k`$ are completely occupied and the states with positive $`E_k`$ are empty. The current flow through the wire does not only produce the overall shift of the band energy within the reduced Brillouin zone but also changes the the total bandwidth from 10 eV at zero current to 12.5 eV at $`I=0.5`$ mA. The band gap between the valence and conductance bands is also modulated by current.

From the band structure calculations the band gap can be extracted as a function of the current. Then the band gap can be turned into the longest possible wavelength of absorbed radiation $`\lambda _{max}`$ and this is plotted in Fig.3 for different values of the net current density. Being a semiconductor wire, polyacetylene is transparent to the photons with wave length longer than $`\lambda _{max}`$ (i.e. with the energies within the band gap) but it is opaque to photons with wavelength shorter than $`\lambda _{max}`$ (within the bandwidth). It is clear from that the boundary between transparent and opaque black parts of the spectrum is blue-shifted by current flow in the polyacetylene wire. In other words, the color of the polyacetylene wire can be modified by electric current.

In this Letter, we have laid a theoretical ground-work for computing a Born-Oppenheimer potential energy surface for molecular wires with direct current. Within the Lagrange multiplier based transport theory we presented a computational tractable theoretical scheme to compute BO of molecular wire junctions. Based upon applications of the techniques to tight-binding model with electron-phonon interactions we predict that (1)the dimerization of the polyacetylene wire is amplified by current; (2)the transparent-opaque boundary is blue-shifted by current flow; (3)the generic mechanism of the semiconductor wire breakage is current increased dimerization.

The author wishes to thank A.Nitzan for valuable discussion.


format: text

text:
# ‘Notches’ in the Average Profiles of Bright Pulsars

## 1 Introduction

Detailed studies of the structure of radio pulsar pulse profiles are essential for understanding the pulsar emission mechanism and the forms of the pulsar emission beam. Pulse profiles are remarkably stable over timescales ranging from a few pulses to many years, indicating that these profiles are determined by permanent physical characteristics of the neutron star and its environment. Many profile properties can be explained very well by the “hollow-cone” model of pulsar emission developed by Radhakrishnan & Cooke (1969) and Komesaroff (1970), shortly after the discovery of the first pulsar. This “magnetic-pole” model, further developed by Sturrock (1971) and Ruderman & Sutherland (1975), involves charges streaming from the polar cap along the open field lines, radiating in the direction of their motion and forming an emission cone aligned with the magnetic axis of the star. As more pulsars were discovered, many were found to have two, three or even more pulse components, prompting various efforts to classify and interpret the various forms (e.g.. Backer 1973; Rankin 1983, 1993; Lyne & Manchester 1988).

In this paper we draw attention to the strange “notches” in the profiles of B0950+08 and two other pulsars, J0437–4715 and B1929+10. All three stars exhibit very similar double “notch” features which appear to have virtually nothing to do with the component structures of their very different profiles. B0950+08 and B1929+10 have rotational periods of 253 and 227 ms, whereas J0437–4715 is a binary millisecond pulsar with a period of only 5.75 ms. Significantly, these stars are some of the very closest among the pulsar population—all with dispersion measures (DMs) of about 3 pc cm-3 and parallax-determined distances of some 262$`\pm `$5, 331$`\pm `$10 and 170$`\pm `$3 pc (Brisken et al 2000, 2002)—and, in spite of the fact that they all have rather ordinary spindown values, all have been detected in the optical and/or soft x-ray region (Mignani et al 2002; De Luca et al 2003; Wang et al 1997; Zavlin et al 2002). B0950+08 and B1929+10 are among the brightest pulsars in the radio sky\[Taylor et al 1993\], and J0437–4715 is well known as the brightest millisecond pulsar. In §2 we discuss our observations of B0950+08, present its average pulse profiles and describe the unusual features. In §3 we compare these features with similar ones seen in the profiles of J0437$``$4715 and B1929+10 and discuss possible physical interpretations.

## 2 Observations and Results

Observations presented in this section were made using the 305-m Arecibo Telescope in Puerto Rico. Observations at 430 MHz were obtained using the Arecibo Observatory Fourier Transform Machine (AOFTM111http://www.naic.edu/ aoftm+) with 1024 channels across a 10-MHz bandpass and with 409.6-$`\mu `$s sampling. B0950+08 was observed at 430 MHz on MJDs 51182, 51188 and 51189 (4th, 10th and 11th of January, 1999) for durations of 3000, 3700 and 2500 seconds, respectively. The 1475-MHz data presented were acquired with the Wideband Arecibo Pulsar Processor (WAPP222http://www.naic.edu/ wapp+) with 128 channels across a 100-MHz bandpass and 256-$`\mu `$s sampling. Observations of B0950+08 at this frequency were taken on MJDs 52187 and 52189 (5th and 7th of October, 2001) for durations of 1100 and 7200 seconds, respectively.

For each B0950+08 observation, pulse phases were calculated using the software package TEMPO333http://pulsar.princeton.edu/tempo+ \[Taylor & Weisberg 1989\] and an ephemeris obtained at Jodrell Bank Observatory \[Hobbs 2002\]. Data were folded to create mean pulse profiles. The up-to-date ephemeris allowed alignment of the profiles acquired on different dates and at different frequencies. The 430-MHz average profiles for the MJD 51188 and 51189 observations are presented in Figs. 1 and 3. Note that the two profiles are distinctly different in overall form, but that the low-level features are seen at just the same $`30^{}`$ longitude before the main pulse (MP) peak (see Figs. 2 & 4). Moreover, a similar pair of features is seen in the MJD 51182 data (not shown).

In Fig. 5 we present a corresponding 1475-MHz profile for the MJD 52189 observation, where again a low-level feature is seen at some $`30^{}`$ (see Fig. 6). At 430 MHz the feature consists of two dips in the profile intensity with half widths of some 2 and their centers separated by some $`7^{}`$. The total width of the feature at 430 MHz is $`11^{}`$. At 1475 MHz—in both this observation and another (not shown) on MJD 52187—the feature appears as a single peak with a width of $`3^{}`$.

Several published observations also appear to record the B0950+08 “notches”. They are very clear in the 430-MHz time-aligned profile of Hankins & Rankin (2003), but cannot be discerned in the lower quality observations at various other frequencies. Moreover, the “notches” can probably be seen in the polarimetric observations of both Gould & Lyne (1998) and Weisberg et al (1998). The former very high quality profiles seem to show pairs of features at the correct phase at 408, 610 and 925 MHz, and in the latter we appear to see a pair of features at 1418 MHz. This latter observation (see their Fig. 5) is especially interesting because the features appear to involve the linear polarization also, which is only 20–30% in the region on the far leading edge of the profile.

It must be said that the features in B0950+08 are rather weak, at best reducing the intensity at their centers by a few percent. It might even be regarded as surprising that such features would be found in a star which is well known for its sporadic emission (It may not be known, for instance, whether the pulsar ever nulls, because the range of intensities exhibited by its pulses is so large.) In this context, it is interesting that Nowakowski et al (2003) have shown that this pulsar’s profile is comprised of different intensity fractions which have quite different partial-average profile forms. These studies indicate that the MP has three main “components”: the trailing one which is usually strongest, the middle one which varies in relative intensity, and a leading one which can only be discerned in certain populations of weak pulses. It would therefore appear that the distinct 430-MHz profiles seen above represent distinct profile “modes” in this star. Finally, the above study finds that the “notches” are seen only in the very weakest populations of pulses, which nonetheless contribute significant power to the profile. The authors believe that the weakest pulses represent emission from rather higher altitudes than the stronger fractions.

## 3 Discussion

Unusual features similar to those presented in §2 have been observed in two other pulsars. Rankin & Rathnasree (1997) reported a double notch-like feature in the average profile of B1929+10 at 430 MHz, and a display similar to theirs using the same observations is given in Fig. 7. As can be seen there, the “notches” follow the main pulse peak by roughly $`100^{}`$ and have a total width of approximately $`10^{}`$. More accurate scaling reveals that they have widths of some 2.3 and that their centers are separated by just twice this interval. Note also that B1929+10’s profile is generally fully linearly polarized, so that the features are most clearly seen in both the total power and total linear polarization444The possible origin of this strange “superpolarization”, that was also seen by Phillips (1990), is discussed in Rankin & Rathnasree (1997). Phillips, however, seems to have plotted his Figs. 1 & 2 with some unreported smoothing, so that the “notches” are not visible, though there is a broad dip in the power just were they should be., where they represent about a 40% diminuation of the power at their centers. The “notches” do appear to be just visible in a sensitive 430-MHz observation of Blaskiewicz et al (1991: see their Fig. 22), though they are not seen at 1.4 GHz either in this paper or in Rankin & Rathnasree. This may be due to the overall weakening of the broad low-level emission feature that follows the MP as well as the poorer signal-to-noise of the 21-cm observations. Neither, unfortunately, were the recent observations of Weisberg et al (2003) sufficiently sensitive to detect the features.

Similar features have also been observed by Navarro et al (1997) in the average profile of the millisecond pulsar J0437$``$4715. These “notches” fall on the trailing edge of this star’s very broad profile, some 70 after the bright central component. Here, the pair is separated by about 3.3, the half-power widths are about a degree, and the fractional intensity decrease at their centers is about 50%. These characteristics are clearly seen in the 1512-MHz polarization profile of Navarro et al (their Fig. 4) which we reproduce here as Fig. 8. However, this paper reports additional detections at frequencies of 438 and 660 MHz, and the three total-power profiles appear together in our Fig. 9, aligned (according to their Fig. 5 caption) on the basis of the anti-symmetric circularly polarized signature associated with the central component. One can see that the “notches” at the three frequencies do not quite align, falling slightly earlier at 660 and 1512 MHz. However, were the profiles aligned more nearly according the the centroids of the central component, the “notches” might well fall at just the same profile phase. It would be interesting to see the results of a timing alignment as carried out for B0950+08 above. Finally, the features do appear to evolve somewhat with frequency, becoming wider and more separated at lower frequencies.

It is noteworthy that, for all three pulsars, these unprecedented features have roughly the same angular width, implying that their overall scale is some nearly fixed fraction of the rotational cycle of the star \[as, apparently, is also the case for pulsar microstructure (e.g., Popov et al 2002)\]. Furthermore, for the two pulsars in which the features have been detected at more than one frequency, they seem to appear at exactly the same longitude. Again, this is a well-known feature of pulsar microstructure, implying that the two phenomena derive from the same physical regions in the pulsar magnetosphere. Pulsar microstructure generally shows the same width regardless of frequency, however, there is evidence for the width of the notch features decreasing with frequency.

B0950+08 and B1929+10 have remarkably similar properties. Both are very bright, have quarter-second rotational periods, and are very nearby. Both pulsars have detectable emission over an unusually broad fraction of their rotation cycle and both exhibit interpulses. With a spin period of 5.75 ms, J0437$``$4715 has very different spin-down properties; however, it is also nearby, extremely bright, and, while it has no interpulse, it has detectable emission over more than $`180^{}`$ of longitude.

The identification of these features in the three brightest pulsars with broad pulse profiles suggests that such features may be common among pulsars with broad profiles. As they are apparently seen over a substantial portion of the radio band and evolve little with frequency, it would seem that they cannot be attributed to absorption in any usual sense. Thus it would seem that they are either due to some very puzzling aspect of the emission process or represent an equally puzzling obscuration of the emission along our sight line. While we cannot more than speculate about the causes of these features, a very novel mechanism is being suggested by Wright (2003) in a companion paper. Clearly, few pulsars show emission so far from the main pulse or interpulse, so observing this feature in more pulsars will be very difficult until the advent of more sensitive pulsar instruments such as the SKA. However, future more sensitive multi-frequency observations of the pulsars discussed above, in addition to polarimetric observations, may yield more clues as to the origin of these unusual features.

## Acknowledgments

We thank Leszek Nowakowski and Geoff Wright for discussions and critical comments on the manuscript. One of us (JMR) wishes to acknowledge support from US National Science Foundation Grant AST 99-87654. The Arecibo Observatory is operated by Cornell University under contract to the US NSF.


text:
# Improved Weil and Tate pairings for elliptic and hyperelliptic curves

## 1 Introduction

The Weil and Tate pairings have been proposed for use in cryptography, including one-round 3-way key establishment, identity-based encryption, and short signatures . For a fixed positive integer $`m`$, the Weil pairing $`e_m`$ is a bilinear map that sends two $`m`$-torsion points on an elliptic curve to an $`m`$th root of unity in the field. For elliptic curves, the Weil pairing is a quotient of two applications of the Tate pairing, except that the Tate pairing needs an exponentiation which the Weil pairing omits.

For cryptographic applications, the objective is a bilinear map with a specific recipe for efficient evaluation, and no clear way to invert. The Weil and Tate pairings provide such tools. Each pairing has a practical definition which involves finding functions with prescribed zeros and poles on the curve, and evaluating those functions at pairs of points.

For elliptic curves, Miller  gave an algorithm for the Weil pairing. (See also the Appendix B to , for a probabilistic implementation of Miller’s algorithm which recursively generates and evaluates the required functions based on a random choice of points.) For Jacobians of hyperelliptic curves, Frey and Rück  gave a recursive algorithm to generate the required functions, assuming the knowledge of intermediate functions having prescribed zeros and poles.

For elliptic curves, we present an improved algorithm for computing the squared Weil pairing, $`e_m(P,Q)^2`$. Our deterministic algorithm does not depend on a random choice of points for evaluation of the pairing. Our algorithm saves about 20% over the standard implementation of the Weil pairing . We use this idea to obtain an improved algorithm for computing the squared Tate pairing for elliptic and hyperelliptic curves. The Tate pairing is already more efficient to implement than the Weil pairing. Our new squared Tate pairing is more efficient than Miller’s algorithm for the Tate pairing for elliptic curves, for another 20% saving. For pairings on special families of elliptic curves in characteristics $`2`$ and $`3`$, some implementation improvements were given in  and . Another deterministic algorithm was given in . In , an algorithm for the pairing on ordinary elliptic curves in arbitrary characteristic is given. Our squared pairing matches the efficiency of the algorithm in  in the case of arbitrary base points where their denominator cancellation technique does not apply.

For hyperelliptic curves, we use Cantor’s algorithm to produce the intermediate functions assumed by Frey and Rück. We define a squared Tate pairing for hyperelliptic curves, and use the knowledge of these intermediate functions to implement the pairing and give an example. Our analysis shows that using the squared Tate pairing saves roughly 30% over the standard Tate pairing for genus $`2`$ curves. Our algorithm for the pairing on hyperelliptic curves can be thought of as a partial generalization of the Barreto-Lynn-Scott algorithm for elliptic curves in the sense that we give a deterministic algorithm which is more efficient to evaluate than the standard one. It remains to be seen whether some denominator cancellation can also be achieved in the hyperelliptic case by choosing base points of a special form as was done for elliptic curves in . For a special family of hyperelliptic curves, Duursma and Lee have given a closed formula for the pairing in , but ours is the first algorithm for the Tate pairing on general hyperelliptic curves, and we have implemented the genus 2 case. The squared Weil pairing or the squared Tate pairing can be substituted for the Weil or Tate pairing in many of the above cryptographic applications.

The paper is organized as follows. Section 2 provides background on the Weil pairing for elliptic curves and gives the algorithm for computing the squared Weil pairing. Section 3 does the same for the squared Tate pairing for elliptic curves. Section 4 presents the squared Tate pairing for hyperelliptic curves and shows how to implement it. Section 5 gives an example of the hyperelliptic pairing.

## 2 Weil pairings for elliptic curves

### 2.1 Definition of the Weil pairing

Let $`E`$ be an elliptic curve over a finite field $`𝔽_q`$. In the following $`𝐎`$ denotes the point at infinity on $`E`$. If $`P`$ is a point on $`E`$, then $`x(P)`$ and $`y(P)`$ denote the rational functions mapping $`P`$ to its affine $`x`$\- and $`y`$-coordinates.

Let $`m`$ be a positive integer. We will use the Weil pairing $`e_m(,)`$ definition in \[11, p. 107\]. To compute $`e_m(P,Q)`$, given two distinct $`m`$-torsion points $`P`$ and $`Q`$ on $`E`$ over an extension field, pick two divisors $`𝒜_P`$ and $`𝒜_Q`$ which are equivalent to $`(P)(𝐎)`$ and $`(Q)(𝐎)`$, respectively, and such that $`𝒜_P`$ and $`𝒜_Q`$ have disjoint support. Let $`f_{𝒜_P}`$ be a function on $`E`$ whose divisor of zeros and poles is $`(f_{𝒜_P})=m𝒜_P`$. Similarly, let $`f_{𝒜_Q}`$ be a function on $`E`$ whose divisor of zeros and poles is $`(f_{𝒜_Q})=m𝒜_Q`$. Then

$$e_m(P,Q)=\frac{f_{𝒜_P}(𝒜_Q)}{f_{𝒜_Q}(𝒜_P)}.$$

### 2.2 Rational functions needed in the evaluation of the pairing

Fix an integer $`m>0`$ and an $`m`$-torsion point $`P`$ on an elliptic curve $`E`$. Let $`𝒜_P`$ be a divisor equivalent to $`(P)(𝐎)`$. For a positive integer $`j`$, let $`f_{j,𝒜_P}`$ be a rational function on $`E`$ with divisor

$$(f_{j,𝒜_P})=j𝒜_P(jP)+(𝐎)$$

This means that $`f_{j,𝒜_P}`$ has $`j`$-fold zeros and poles at the points in $`𝒜_P`$, as well as a simple pole at $`jP`$ and a simple zero at $`𝐎`$, and no other zeros or poles. Since $`mP=𝐎`$, it follows that $`f_{m,𝒜_P}`$ has divisor $`m𝒜_P`$, so in fact $`f_{𝒜_P}=f_{m,𝒜_P}`$. Throughout the paper the notation $`f_{j,P}`$ will be used to denote the function $`f_{j,𝒜_P}`$ with $`𝒜_P=(P)(𝐎)`$.

Silverman \[11, Cor. 3.5, p. 67\] shows that these functions exist. Each $`f_{i,𝒜_P}`$ is unique up to a nonzero multiplicative scalar. Miller’s algorithm gives an iterative construction of these functions (see for example ). The construction of $`f_{1,𝒜_P}`$ depends on $`𝒜_P`$. Given $`f_{i,𝒜_P}`$ and $`f_{j,𝒜_P}`$, one constructs $`f_{i+j,𝒜_P}`$ as the product

$$f_{i+j,𝒜_P}=f_{i,𝒜_P}f_{j,𝒜_P}\frac{g_{iP,jP}}{g_{(i+j)P}}.$$
(1)
Here the notation $`g_{U,V}`$ (two subscripts) denotes the line passing through the points $`U`$ and $`V`$ on $`E`$. The notation $`g_U`$ (one subscript) denotes the vertical line through $`U`$ and $`U`$. For more details on efficiently computing $`f_{m,𝒜_P}`$, see .

### 2.3 Squared Weil pairing for elliptic curves

The purpose of this section is to construct a new pairing, which we call the ‘squared Weil pairing’, and which has the advantage of being more efficient to compute than Miller’s algorithm for the original Weil pairing. Our algorithm also has the advantage that it is guaranteed to output the correct answer and does not depend on inputting a randomly chosen point. In contrast Miller’s algorithm may restart, since the randomly chosen point can cause the algorithm to fail.

### 2.4 Algorithm for $`e_m(P,Q)^2`$

Fix a positive integer $`m`$ and the curve $`E`$. Given two $`m`$-torsion points $`P`$ and $`Q`$ on $`E`$, we want to compute $`e_m(P,Q)^2`$. Start with an addition-subtraction chain for $`m`$. That is, after an initial $`1`$, every element in the chain is a sum or difference of two earlier elements, until an $`m`$ appears. Well-known techniques give a chain of length $`O(\mathrm{log}(m))`$. For each $`j`$ in the addition-subtraction chain, form a tuple $`t_j=[jP,jQ,n_j,d_j]`$ such that

$$\frac{n_j}{d_j}=\frac{f_{j,P}(Q)f_{j,Q}(P)}{f_{j,P}(Q)f_{j,Q}(P)}.$$
(2)
Start with $`t_1=[P,Q,\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}1}]`$. Given $`t_j`$ and $`t_k`$, this procedure gets $`t_{j+k}`$:

1. Form the elliptic curve sums $`jP+kP=(j+k)P`$ and $`jQ+kQ=(j+k)Q`$.
2. Find coefficients of the line $`g_{jP,kP}(X)=c_0+c_1x(X)+c_2y(X)`$.
3. Find coefficients of the line $`g_{jQ,kQ}(X)=c_0^{}+c_1^{}x(X)+c_2^{}y(X)`$.
4. Set

$$\begin{array}{c}\hfill n_{j+k}=n_jn_k(c_0+c_1x(Q)+c_2y(Q))(c_0^{}+c_1^{}x(P)c_2^{}y(P))\\ \hfill d_{j+k}=d_jd_k(c_0+c_1x(Q)c_2y(Q))(c_0^{}+c_1^{}x(P)+c_2^{}y(P)).\end{array}$$

A similar construction gives $`t_{jk}`$ from $`t_j`$ and $`t_k`$. The vertical lines through $`(j+k)P`$ and $`(j+k)Q`$ do not appear in the formulae for $`n_{j+k}`$ and $`d_{j+k}`$, because the contributions from $`Q`$ and $`Q`$ (or from $`P`$ and $`P`$) are equal. When $`j+k=m`$, this simplifies to $`n_{j+k}=n_jn_k`$ and $`d_{j+k}=d_jd_k`$, since $`c_2`$ and $`c_2^{}`$ will be zero.

When $`n_m`$ and $`d_m`$ are nonzero, then the computation

$$\frac{n_m}{d_m}=\frac{f_{m,P}(Q)f_{m,Q}(P)}{f_{m,P}(Q)f_{m,Q}(P)}.$$

has been successful, and we have the correct output. If, however, $`n_m`$ or $`d_m`$ is zero, then some factor such as $`c_0+c_1x(Q)+c_2y(Q)`$ must have vanished. That line was chosen to pass through $`jP`$, $`kP`$, and $`(jk)P`$, for some $`j`$ and $`k`$. It does not vanish at any other point on the elliptic curve. Therefore this factor can vanish only if $`Q=jP`$ or $`Q=kP`$ or $`Q=(jk)P`$. In all of these cases $`Q`$ will be a multiple of $`P`$, ensuring $`e_m(P,Q)=1`$.

### 2.5 Correctness proof

###### Theorem 2.1 (Squared Weil Pairing Formula)

Let $`m`$ be a positive integer. Suppose $`P`$ and $`Q`$ are $`m`$-torsion points on $`E`$, with neither being the identity and $`P`$ not equal to $`\pm Q`$. Then the squared Weil pairing satisfies

$$\frac{f_{m,P}(Q)f_{m,Q}(P)}{f_{m,P}(Q)f_{m,Q}(P)}=(1)^me_m(P,Q)^2.$$

###### Proof

Let $`R_1,R_2`$ be points on $`E`$ such that the divisors $`𝒜_P:=(P+R_1)(R_1)`$ and $`𝒜_Q:=(Q+R_2)(R_2)`$ have disjoint support. Let $`𝒜_Q:=(Q+R_2)(R_2)`$. Let $`f_{𝒜_P}`$ and $`f_{𝒜_Q}`$ be as above. Then

$$e_m(P,Q)=\frac{f_{𝒜_P}((Q+R_2)(R_2))}{f_{𝒜_Q}((P+R_1)(R_1))}=\frac{f_{𝒜_P}(Q+R_2)}{f_{𝒜_P}(R_2)}\frac{f_{𝒜_Q}(R_1)}{f_{𝒜_Q}(P+R_1)}.$$

Let $`g(X)=f_{m,P}(XR_1)`$. Then $`(g)=m(P+R_1)m(R_1)=m𝒜_P=(f_{𝒜_P}),`$ This implies $`g(X)/f_{𝒜_P}(X)`$ is constant and

$$\frac{f_{𝒜_P}(Q+R_2)}{f_{𝒜_P}(R_2)}=\frac{g(Q+R_2)}{g(R_2)}=\frac{f_{m,P}(Q+R_2R_1)}{f_{m,P}(R_2R_1)}.$$

Similarly

$$\frac{f_{𝒜_Q}(R_1)}{f_{𝒜_Q}(P+R_1)}=\frac{f_{m,Q}(R_1R_2)}{f_{m,Q}(P+R_1R_2)}.$$

Plugging these into Miller’s formula gives

$$e_m(P,Q)=\frac{f_{m,P}(Q+R_2R_1)}{f_{m,P}(R_2R_1)}\frac{f_{m,Q}(R_1R_2)}{f_{m,Q}(P+R_1R_2)}.$$

Using the same argument for $`e_m(P,Q)`$ we obtain

$$e_m(P,Q)=\frac{f_{m,P}(Q+R_2R_1)}{f_{m,P}(R_2R_1)}\frac{f_{m,Q}(R_1R_2)}{f_{m,Q}(P+R_1R_2)}$$

$$=\frac{f_{m,P}(Q+R_2R_1)}{f_{m,P}(R_2R_1)}\frac{f_{m,Q}(R_1+R_2)}{f_{m,Q}(PR_1+R_2)}$$

Hence we can simplify $`e_m(P,Q)^2`$ to

$$\frac{e_m(P,Q)}{e_m(P,Q)}=\frac{f_{m,P}(Q+R_2R_1)f_{m,Q}(R_1R_2)f_{m,Q}(PR_1+R_2)}{f_{m,P}(Q+R_2R_1)f_{m,Q}((R_1R_2))f_{m,Q}(P+R_1R_2)}.$$

Let $`R:=R_2R_1`$. This equation becomes

$$e_m(P,Q)^2=\frac{f_{m,P}(Q+R)f_{m,Q}(R)f_{m,Q}(P+R)}{f_{m,P}(Q+R)f_{m,Q}(R)f_{m,Q}(PR)}.$$
(3)
Fix two linearly independent $`m`$-torsion points $`P`$ and $`Q`$. The right side of (3) is a rational function of $`R`$; call it $`\psi =\psi (R)`$. Since $`f_{m,P}`$ can have zeros and poles only at $`P`$ and $`𝐎`$, and $`f_{m,Q}`$ can have zeros and poles only at $`Q`$ and $`𝐎`$, this function $`\psi (R)`$ can have zeros or poles only at $`R=Q`$, $`Q`$, $`PQ`$, $`P+Q`$, $`P`$, and $`𝐎`$. By looking at the factors of $`\psi `$ we can check that at each of these points, the value of $`\psi (R)`$ is well-defined, because the zeros and poles cancel each other out. Since $`\psi `$ is a rational function on an elliptic curve which does not have any zeros or poles, $`\psi `$ must be constant. Since for certain values of $`R`$, $`\psi (R)=e_m(P,Q)^2`$, this must be the case for all values of $`R`$. Hence we may in particular choose $`R=𝐎`$, or equivalently $`R_1=R_2`$. So let $`R_1=R_2`$. By Lemma 1 below,

$$\frac{f_{m,Q}(R_1R_2)}{f_{m,Q}((R_1R_2))}=(1)^m,$$

and by assumption $`f_{m,P}`$ does not have a zero or pole at $`Q`$ and $`f_{m,Q}`$ does not have a zero or pole at $`P`$. Hence expression (3) simplifies to

$$e_m(P,Q)^2=(1)^m\frac{f_{m,P}(Q)f_{m,Q}(P)}{f_{m,P}(Q)f_{m,Q}(P)}.$$
(4)
###### Lemma 1

Let $`f:E𝔽_q`$ be a rational function on $`E`$ with a zero of order $`m`$ (or a pole of order $`m`$) at $`𝐎`$. Define $`g:E𝔽_q`$ by $`g(X)=f(X)/f(X)`$. Then $`g(𝐎)`$ is finite and $`g(𝐎)=(1)^m`$.

###### Proof

The rational function $`h(X)=x(X)/y(X)`$ has a zero of order $`1`$ at $`X=𝐎`$. The function $`f_1=f/h^m`$ has neither a pole nor a zero at $`X=𝐎`$, so $`f_1(𝐎)`$ is finite and nonzero. We check that the rational function $`\varphi (X)=h(X)/h(X)`$ has no zeros and poles on $`E`$. Hence $`\varphi `$ is constant. By computing $`\varphi (X)`$ for a finite point $`X=(x,y)`$ on $`E`$ with $`x,y0`$, we see that $`\varphi `$ is equal to $`1`$. Hence

$$g(X)=\frac{f(X)}{f(X)}=\frac{h(X)^mf_1(X)}{h(X)^mf_1(X)}=\varphi (X)^m\frac{f_1(X)}{f_1(X)}=(1)^m\frac{f_1(X)}{f_1(X)},$$

and $`g(𝐎)=(1)^m`$.

### 2.6 Estimated savings

In this section we compare our algorithm for the squared Weil pairing to Miller’s algorithm for the Weil pairing. We count operations in the underlying finite field, counting field squarings as field multiplications throughout. This analysis assumes that we use the short Weierstrass form for the elliptic curve $`E`$.

In practice, some of these arithmetic operations may be over a base field and others over an extension field. That issue is discussed in more detail in . Without knowing the precise context of the application, we don’t distinguish these, although individual costs may differ considerably.

#### 2.6.1 Miller’s algorithm.

Miller’s algorithm chooses two points $`R_1`$, $`R_2`$ on $`E`$, and lets $`𝒜_P=(P+R_1)(R_1)`$ and $`𝒜_Q=(P+R_2)(R_2)`$. Recall that in the notation of Section 2.1, $`f_{𝒜_P}`$ is a function whose divisor is $`m𝒜_P`$. As in Section 2.2, let $`f_{j,𝒜_P}`$ be a function with divisor $`(f_{j,𝒜_P})=j(P+R_1)j(R_1)(jP)+(𝐎).`$ This is the function $`f_j`$ in the notation of \[3, p. 611f.\]. Then $`f_{m,𝒜_P}=f_{𝒜_P}`$. As pointed out in Equation (B.1) of \[3, p. 612\], (1) leads to the recurrence

$`f_{i+j,𝒜_P}(𝒜_Q)=f_{i,𝒜_P}(𝒜_Q)f_{j,𝒜_P}(𝒜_Q){\displaystyle \frac{g_{iP,jP}(𝒜_Q)}{g_{(i+j)P}(𝒜_Q)}}.`$ (5)
During the computations, each $`f_{j,𝒜_P}(𝒜_Q)`$ is a known field element, unlike the unevaluated functions $`f_{j,𝒜_P}`$. Since $`𝒜_Q`$ has degree 0, the value of $`f_{j,𝒜_P}(𝒜_Q)`$ is unambiguous, whereas $`f_{j,𝒜_P}`$ is defined only up to a multiplicative scalar.

To compute the Weil pairing we need

$`e_m(P,Q)={\displaystyle \frac{f_{𝒜_P}(Q+R_2)}{f_{𝒜_P}(R_2)}}{\displaystyle \frac{f_{𝒜_Q}(R_1)}{f_{𝒜_Q}(P+R_1)}}={\displaystyle \frac{f_{m,𝒜_P}(Q+R_2)}{f_{m,𝒜_P}(R_2)}}{\displaystyle \frac{f_{m,𝒜_Q}(R_1)}{f_{m,𝒜_Q}(P+R_1)}}.`$
For integers $`j`$ in an addition-subtraction chain for $`m`$, we will construct a tuple $`t_j=[jP,jQ,n_j,d_j]`$ where $`n_j`$ and $`d_j`$ satisfy

$$\frac{n_j}{d_j}=\frac{f_{j,𝒜_P}(Q+R_2)}{f_{j,𝒜_P}(R_2)}\frac{f_{j,𝒜_Q}(R_1)}{f_{j,𝒜_Q}(P+R_1)}.$$

To compute $`t_{i+j}`$ from $`t_i`$ and $`t_j`$, one uses the above recurrence (5) to derive the following expression for $`n_{i+j}/d_{i+j}`$:

$$\frac{n_{i+j}}{d_{i+j}}=\frac{n_i}{d_i}\frac{n_j}{d_j}\frac{g_{iP,jP}(Q+R_2)}{g_{iP,jP}(R_2)}\frac{g_{(i+j)P}(R_2)}{g_{(i+j)P}(Q+R_2)}$$

$$\frac{g_{iQ,jQ}(R_1)}{g_{iQ,jQ}(P+R_1)}\frac{g_{(i+j)Q}(P+R_1)}{g_{(i+j)Q}(R_1)}.$$
(6)
To evaluate, for example, $`g_{iP,jP}(Q+R_2)/g_{iP,jP}(R_2)`$, start with the elliptic curve addition $`iP+jP=(i+j)P`$. This costs 1 field division and 2 field multiplications in the generic case where $`iP`$ and $`jP`$ have distinct $`x`$-coordinates and neither is $`𝐎`$. Save the slope $`\lambda `$ of the line $`g_{iP,jP}(X)=y(X)y(iP)\lambda (x(X)x(iP))`$ through $`iP`$ and $`jP`$. Two field multiplications suffice to evaluate $`g_{iP,jP}(Q+R_2)`$ and $`g_{iP,jP}(R_2)`$ given $`Q+R_2`$ and $`R_2`$. No more field multiplications or divisions are needed to compute the numerator and denominator of

$$\frac{g_{(i+j)P}(R_2)}{g_{(i+j)P}(Q+R_2)}=\frac{x(R_2)x((i+j)P)}{x(Q+R_2)x((i+j)P)}.$$

Repeat this once more to evaluate the last two fractions in (6). Overall these evaluations cost 8 field multiplications and 2 field divisions. We need 10 multiplications to multiply the six fractions, for an overall cost of 18 multiplications and 2 divisions.

#### 2.6.2 Squared pairing.

The squared pairing needs $`n_m/d_m`$ where $`n_j/d_j`$ is given by (2). The recurrence formula is

$$\frac{n_{i+j}}{d_{i+j}}=\frac{n_i}{d_i}\frac{n_j}{d_j}\frac{g_{iP,jP}(Q)}{g_{iP,jP}(Q)}\frac{g_{(i+j)P}(Q)}{g_{(i+j)P}(Q)}\frac{g_{iQ,jQ}(P)}{g_{iQ,jQ}(P)}\frac{g_{(i+j)Q}(P)}{g_{(i+j)Q}(P)}.$$
(7)
This time the update from $`t_i=[iP,iQ,n_i,d_i]`$ and $`t_j`$ to $`t_{i+j}`$ needs 2 elliptic curve additions. Each elliptic curve addition needs 2 multiplications and 1 division in the generic case. We can evaluate the numerator and denominator of

$$\frac{g_{iP,jP}(Q)}{g_{iP,jP}(Q)}=\frac{y(Q)y(iP)\lambda (x(Q)x(iP))}{y(Q)y(iP)\lambda (x(Q)x(iP))}$$

with only 1 multiplication, since $`x(Q)=x(Q)`$.

The fraction $`g_{(i+j)P}(Q)/g_{(i+j)P}(Q)`$ simplifies to 1 since $`g_{(i+j)P}(X)`$ depends only on $`x(X)`$, not $`y(X)`$. Overall 6 multiplications and 2 divisions suffice to evaluate the numerators and denominators of the six fractions in (7). We multiply the four non-unit fractions with 6 field multiplications.

Overall, the squared Weil pairing advances from $`t_i`$ and $`t_j`$ to $`t_{i+j}`$ with 12 field multiplications and 2 field divisions in the generic case, compared to 18 field multiplications and 2 field divisions for Miller’s method. When $`i=j`$, each algorithm needs 2 additional field multiplications due to the elliptic curve doublings. Estimating a division as 5 multiplications, this is roughly a 20% savings.

## 3 Squared Tate pairing for elliptic curves

### 3.1 Squared Tate pairing formula

Let $`m`$ be a positive integer. Let $`E`$ be defined over $`𝔽_q`$, where $`m`$ divides $`q1`$. Let $`E(𝔽_q)[m]`$ denote the $`m`$-torsion points on $`E`$ over $`𝔽_q`$. Assume $`PE(𝔽_q)[m]`$, and $`QE(𝔽_q)`$, with neither being the identity and $`P`$ not equal to a multiple of $`Q`$. The Tate pairing $`\varphi _m(P,Q)`$ on $`E(𝔽_q)[m]\times E(𝔽_q)/mE(𝔽_q)`$ is defined in  as

$$\varphi _m(P,Q):=\left(f_{𝒜_P}(𝒜_Q)\right)^{(q1)/m},$$

with the notation and evaluation as for the Weil pairing above. Now we define

$$v_m(P,Q):=\left(\frac{f_{m,P}(Q)}{f_{m,P}(Q)}\right)^{(q1)/m},$$

where $`f_{m,P}`$ is as above, and call $`v_m`$ the squared Tate pairing. To justify this terminology, we will show below that $`v_m(P,Q)=\varphi _m(P,Q)^2.`$

### 3.2 Algorithm for $`v_m(P,Q)`$

Fix a positive integer $`m`$ and the curve $`E`$. Given an $`m`$-torsion point $`P`$ on $`E`$ and a point $`Q`$ on $`E`$, we want to compute $`v_m(P,Q)`$. As before, start with an addition-subtraction chain for $`m`$. For each $`j`$ in the chain, form a tuple $`t_j=[jP,n_j,d_j]`$ such that

$$\frac{n_j}{d_j}=\frac{f_{j,P}(Q)}{f_{j,P}(Q)}.$$
(8)
Start with $`t_1=[P,1,1]`$. Given $`t_j`$ and $`t_k`$, this procedure gets $`t_{j+k}`$:

1. Form the elliptic curve sum $`jP+kP=(j+k)P`$.
2. Find the line $`g_{jP,kP}(X)=c_0+c_1x(X)+c_2y(X)`$.
3. Set

$$\begin{array}{c}\hfill n_{j+k}=n_jn_k(c_0+c_1x(Q)+c_2y(Q))\\ \hfill d_{j+k}=d_jd_k(c_0+c_1x(Q)c_2y(Q)).\end{array}$$

A similar construction gives $`t_{jk}`$ from $`t_j`$ and $`t_k`$. The vertical lines through $`(j+k)P`$ and $`(j+k)Q`$ do not appear in the formulae for $`n_{j+k}`$ and $`d_{j+k}`$, because the contributions from $`Q`$ and $`Q`$ are equal. When $`j+k=m`$, one can further simplify this to $`n_{j+k}=n_jn_k`$ and $`d_{j+k}=d_jd_k`$, since $`c_2`$ will be zero. When $`n_m`$ and $`d_m`$ are nonzero, then the computation of (8) with $`j=m`$ is successful, and after raising to the $`(q1)/m`$ power, we have the correct output. If some $`n_m`$ or $`d_m`$ were zero, then some factor such as $`c_0+c_1x(Q)+c_2y(Q)`$ must have vanished. That line was chosen to pass through $`jP`$, $`kP`$, and $`(jk)P`$, for some $`j`$ and $`k`$. It does not vanish at any other point on the elliptic curve. Therefore this factor can vanish only if $`Q=jP`$ or $`Q=kP`$ or $`Q=(jk)P`$ for some $`j`$ and $`k`$. In all of these cases $`Q`$ would be a multiple of $`P`$, contrary to our assumption.

### 3.3 Correctness proof

###### Theorem 3.1

Let $`m`$ be a positive integer. Suppose $`PE(𝔽_q)[m]`$ and $`QE(𝔽_q)`$ with neither being the identity and $`P\pm Q`$. Then the squared Tate pairing is

$$\varphi _m(P,Q)^2=\left(\frac{f_{m,P}(Q)}{f_{m,P}(Q)}\right)^{(q1)/m}.$$

###### Proof

Let $`R_1`$ and $`R_2`$ be as in the proof of Theorem 2.1. The proof proceeds exactly as the correctness proof for the Weil pairing. The only difference is that the factor of $`(1)^m`$ is missing in the Tate pairing and so we have

$`\varphi _m(P,Q)^2={\displaystyle \frac{\varphi _m(P,Q)}{\varphi _m(P,Q)}}=\left({\displaystyle \frac{f_{m,P}(Q+R_2R_1)}{f_{m,P}(Q+R_2R_1)}}\right)^{(q1)/m}.`$
By the same argument as in the proof for the Weil pairing we may choose $`R_2=R_1`$, which gives us the desired formula.

### 3.4 Estimated savings

This analysis is almost identical to that for the Weil pairing in Section 2.6. When analyzing Miller’s algorithm for the Tate pairing, the main difference from Section 2.6 is that the analog of (6) has 2 fewer fractions to evaluate and combine. An elliptic curve addition costs 1 division and 2 multiplications, while 2 multiplications are needed to evaluate the numerators and denominators of the two fractions. Then 6 multiplications are needed to combine the numerators and denominators of the 4 fractions. Therefore each step of Miller’s algorithm performing an addition costs 1 division and 10 multiplications.

For the squared Tate pairing, the analog of (7) also has 2 fewer fractions in it. An elliptic curve addition costs 1 division and 2 multiplications, while only 1 multiplication is needed to evaluate the numerators and denominators of the 2 fractions. Then 4 multiplications are needed to combine the numerators and denominators of the 3 non-unit fractions. Therefore each step of the squared Tate pairing algorithm performing an addition costs 1 division and 7 multiplications.

Overall, the squared Tate pairing advances from $`t_i`$ and $`t_j`$ to $`t_{i+j}`$ with 7 field multiplications and 1 field division in the generic case, compared to 10 field multiplications and 1 field division for Miller’s method applied to the usual Tate pairing. When $`i=j`$, each algorithm needs one additional field multiplication due to the elliptic curve doubling. Estimating a division as 5 multiplications, this is roughly a 20% savings.

Comparing our squared pairing to the algorithm from , the algorithms are equally efficient in the case of general base points, where there is no cancellation of denominators in their algorithm. In , the authors show that if the security multiplier is even ($`k=2d`$) and the $`x`$-coordinate of the base point $`Q`$ lies in a subfield $`𝔽_{q^d}`$, then the denominators in the Tate pairing evaluation disappear. This makes their method more efficient, but it is possible that adding this extra structure may weaken the system for cryptographic use. Also, in some situations, restricting to $`k`$ even may not be desirable.

## 4 Squared Tate pairing for hyperelliptic curves

Let $`C`$ be a hyperelliptic curve of genus $`g`$ given by an affine model $`y^2=f(x)`$ with $`\mathrm{deg}f=2g+1`$ over a finite field $`𝔽_q`$ not of characteristic $`2`$. The curve $`C`$ has one point at infinity, which we will denote by $`P_{\mathrm{}}`$. Let $`J=J(C)`$ be the Jacobian of $`C`$. If $`P=(x,y)`$ is a point on $`C`$, then $`P^{}`$ will denote the point $`P^{}:=(x,y)`$. We denote the identity element of $`J`$ by $`\mathrm{𝐢𝐝}`$.

The Riemann-Roch theorem assures that each element $`D`$ of $`J`$ contains a representative of the form $`AgP_{\mathrm{}}`$, where $`A`$ is an effective divisor of degree $`g`$. In addition, we will always work with semi-reduced representatives, which means that if a point $`P=(x,y)`$ occurs in $`A`$ then $`P^{}:=(x,y)`$ does not occur elsewhere in $`A`$. The effective divisor representing the identity element $`\mathrm{𝐢𝐝}`$ will be $`gP_{\mathrm{}}`$. For an element $`D`$ of $`J`$ and integer $`i`$, a representative for $`iD`$ will be $`A_igP_{\mathrm{}}`$, where $`A_i`$ is effective of degree $`g`$ and semi-reduced.

To a representative $`A_igP_{\mathrm{}}`$ we associate two polynomials $`(a_i,b_i)`$ which represent the divisor. The first polynomial, $`a_i(x)`$, is monic and has zeros at the $`x`$-coordinates of the points in the support of the divisor $`A_i`$. The second polynomial, $`b_i(x)`$, has degree less than $`\mathrm{deg}(a_i(x))`$, and the graph of $`y=b_i(x)`$ passes through the finite points in the support of the divisor $`A_i`$.

### 4.1 Definition of the Tate pairing

Fix a positive integer $`m`$ and assume that $`𝔽_q`$ contains a primitive $`m`$th root of unity $`\zeta _m`$. The Tate pairing, $`\varphi _m:J(𝔽_q)[m]\times J(𝔽_q)/mJ(𝔽_q)𝔽_q^{}/𝔽_{q}^{}{}_{}{}^{m}\zeta _m,`$ is defined in \[7, p. 871\] explicitly as follows. Let $`DJ(𝔽_q)[m]`$ and $`EJ(𝔽_q)`$. Let $`h_{m,D}`$ be a function on $`C`$ whose divisor is $`(h_{m,D})=mD.`$ Then

$$\varphi _m(D,E):=h_{m,D}(E)^{\frac{q1}{m}}\zeta _m.$$

This pairing is known to be well-defined, bilinear, and non-degenerate. The value $`h_{m,D}(E)`$ is defined only up to $`m`$th powers, so we raise the result to the power $`\frac{q1}{m}`$ to eliminate all $`m`$th powers. Note that $`E`$ is a divisor on the curve $`C`$, not an elliptic curve. We also assume that the support of $`E`$ does not contain $`P_{\mathrm{}}`$ and that $`E`$ is prime to the $`A_i`$’s. Actually $`E`$ needs to be prime to only those representatives which will be used in the addition-subtraction chain for $`m`$, so to about $`\mathrm{log}m`$ divisors.

Frey and Rück \[7, pp. 872-873\] show how to evaluate the Tate pairing on the Jacobian of a curve assuming an explicit reduction algorithm for divisors on a curve. Cantor  gives such an algorithm for hyperelliptic curves when the degree of $`f`$ is odd. In Section 4.4 below, we use Cantor’s algorithm to explicitly compute the necessary intermediate functions. These functions will be used to evaluate the squared Tate pairing, but they could just as well be used to evaluate the usual Tate pairing.

### 4.2 Squared Tate pairing $`v_m`$ for hyperelliptic curves

###### Theorem 4.1

Given an $`m`$-torsion element $`D`$ of $`J`$ and an element $`E`$ of $`J`$, with representatives $`D=P_1+P_2+\mathrm{}+P_ggP_{\mathrm{}}`$ and $`E=Q_1+Q_2+\mathrm{}+Q_ggP_{\mathrm{}}`$ respectively, with $`P_i`$ not equal to $`Q_j`$ or $`Q_j^{}`$ for any $`i,j`$ define

$$v_m(D,E):=\left(h_{m,D}(Q_1Q_1^{}+Q_2Q_2^{}+\mathrm{}+Q_gQ_g^{})\right)^{(q1)/m}.$$

Then $`v_m(D,E)=\pm \varphi _m(D,E)^2`$ where $`\varphi _m(D,E)`$ is the Tate pairing defined above.

###### Proof

Recall that if $`P_1=(x,y)`$ is a point on $`C`$, then $`P_1^{}`$ is the point $`(x,y)`$. Similarly, if $`D=P_1+P_2+\mathrm{}+P_ggP_{\mathrm{}}`$, let $`D^{}=P_1^{}+P_2^{}+\mathrm{}+P_ggP_{\mathrm{}}`$. For the proof, we will compute $`\varphi _m(2D,\mathrm{\hspace{0.17em}2}E)`$.

Observe that $`EE^{}=Q_1Q_1^{}+Q_2Q_2^{}+\mathrm{}+Q_gQ_g^{}2E`$ in the Jacobian of $`C`$, since $`E+E^{}=(Q_1+Q_1^{}2P_{\mathrm{}})+\mathrm{}+(Q_g+Q_g^{}2P_{\mathrm{}})\mathrm{𝐢𝐝}`$. Let $`h_{m,D}`$ denote the rational function on $`C`$ with divisor $`(h_{m,D})=mP_1+\mathrm{}+mP_g2gmP_{\mathrm{}}`$ as above. Then the divisor of $`h_{m,D}/h_{m,D^{}}`$ has the form

$$\left(\frac{h_{m,D}}{h_{m,D^{}}}\right)=mP_1mP_1^{}+\mathrm{}+mP_gmP_g^{},$$

so $`(h_{m,D}/h_{m,D^{}})2mD`$ in the Jacobian. That means we can use $`h_{m,D}/h_{m,D^{}}`$ to compute the pairing $`\varphi _m(2D,2E)`$. If $`Q`$ is any point on $`C`$, then we can see by comparing the divisors of the two functions that $`h_{m,D}(Q)=ch_{m,D^{}}(Q^{})`$, where $`c`$ is a constant which does not depend on $`Q`$.

Hence

$`\varphi _m(2D,\mathrm{\hspace{0.17em}2}E)`$ $`=`$ $`\left({\displaystyle \frac{h_{m,D}(EE^{})}{h_{m,D^{}}(EE^{})}}\right)^{(q1)/m}=\left({\displaystyle \frac{h_{m,D}(EE^{})}{h_{m,D}(E^{}E)}}\right)^{(q1)/m}`$
$`=`$ $`\left(h_{m,D}(EE^{})^2\right)^{(q1)/m}.`$
Since $`\varphi _m(2D,\mathrm{\hspace{0.17em}2}E)=\varphi _m(D,E)^4`$, it follows that

$$\varphi _m(D,E)^2=\pm (h_{m,D}(Q_1Q_1^{}+\mathrm{}+Q_gQ_g^{}))^{(q1)/m}.$$

### 4.3 Functions needed in the evaluation of the pairings

Let $`D`$ be an $`m`$-torsion element of $`J`$. For a positive integer $`j`$, let $`h_{j,D}`$ denote a rational function on $`C`$ with divisor

$$(h_{j,D})=jA_1A_j(j1)gP_{\mathrm{}}.$$

Since $`D`$ is an $`m`$-torsion element, we have that $`A_m=gP_{\mathrm{}}`$, so the divisor of $`h_{m,D}`$ is $`(h_{m,D})=mA_1mgP_{\mathrm{}}`$. Each $`h_{j,D}`$ is well-defined up to a multiplicative constant.

Given positive divisors $`A_i`$ and $`A_j`$, we can use Cantor’s algorithm to find a positive divisor $`A_{i+j}`$ and a function $`u_{i,j}`$ with divisor equal to

$$(u_{i,j})=A_i+A_jA_{i+j}gP_{\mathrm{}}.$$

We construct $`h_{j,D}(E)`$ iteratively. For $`j=1`$, let $`h_{1,D}`$ be 1. Suppose we have $`A_i`$, $`A_j`$, $`h_{i,D}(E)`$ and $`h_{j,D}(E)`$. Let $`u_{i,j}`$ be the above function on $`C`$. Then

$$h_{i+j,D}(E)=h_{i,D}(E)h_{j,D}(E)u_{i,j}(E).$$

### 4.4 Algorithm to compute $`v_m(D,E)`$

Let $`D`$ and $`E`$ be as above. Form an addition-subtraction chain for $`m`$. For each $`j`$ in the chain we need to form a tuple $`t_j=[A_j,n_j,d_j]`$ such that $`jD`$ has representative $`A_j2P_{\mathrm{}}`$ and

$$\frac{n_j}{d_j}=\frac{h_{j,D}(Q_1)h_{j,D}(Q_2)}{h_{j,D}(Q_1^{})h_{j,D}(Q_2^{})}.$$

Let $`t_1=[A_1,\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}1}]`$. Given $`t_i`$ and $`t_j`$, let $`(a_i,b_i)`$ and $`(a_j,b_j)`$ be the polynomials corresponding to the divisors $`A_i`$ and $`A_j`$. Do a composition step as in Cantor’s algorithm to obtain $`(a,b)`$ corresponding to $`A_i+A_j`$, without performing the reduction step. Let $`d(x)=\mathrm{gcd}(a_i(x),a_j(x),b_i(x)+b_j(x))`$. The output polynomials $`a`$, $`b`$, and $`d`$ depend on $`i`$ and $`j`$, but we will omit the subscripts here for ease of notation. If $`d(x)=1`$, then $`a(x)=a_i(x)a_j(x)`$, and $`b(x)`$ is the polynomial with $`\mathrm{deg}(b)<\mathrm{deg}(a)`$ such that $`y=b(x)`$ passes through the distinct finite points in the support of $`A_i`$ and $`A_j`$.

The reduction step described in \[4, p. 99\] then replaces $`(a,b)`$ by $`(\stackrel{~}{a},\stackrel{~}{b})`$ where $`\stackrel{~}{a}=(fb^2)/a,\stackrel{~}{b}b(mod\stackrel{~}{a})`$ and $`\mathrm{deg}(\stackrel{~}{b})<\mathrm{deg}(\stackrel{~}{a})`$. This reduction step is applied repeatedly until $`\mathrm{deg}(\stackrel{~}{a})g`$. In the genus 2 situation, it follows from \[4, p. 99\] that at most one reduction step is performed.

Case i. If $`g=2`$ and $`\mathrm{deg}(a(x))>2`$, a reduction step is performed. If we let

$$v_{i,j}(P)=\frac{a(x(P))}{b(x(P))+y(P)},$$
(9)
and

$$u_{i,j}(P):=v_{i,j}(P)d(x(P)),$$

then $`(u_{i,j})=A_i+A_jA_{i+j}2P_{\mathrm{}}`$, and

$`{\displaystyle \frac{u_{i,j}(P)}{u_{i,j}(P^{})}}={\displaystyle \frac{a(x(P))}{a(x(P^{}))}}{\displaystyle \frac{b(x(P^{}))+y(P^{})}{b(x(P))+y(P)}}{\displaystyle \frac{d(x(P))}{d(x(P^{}))}}={\displaystyle \frac{b(x(P^{}))+y(P^{})}{b(x(P))+y(P)}}.`$
Let

$$\begin{array}{c}\hfill n_{i+j}:=n_in_j(b+y)(Q_1^{})(b+y)(Q_2^{})\\ \hfill d_{i+j}:=d_id_j(b+y)(Q_1)(b+y)(Q_2).\end{array}$$
(10)
There is no contribution from $`a`$ in $`n_{i+j}`$ and $`d_{i+j}`$ because the contributions from $`Q_i`$ and $`Q_i^{}`$ are equal. This improves the algorithm for the Tate pairing in .

Case ii. If $`g=2`$ and $`\mathrm{deg}(a(x))2`$, then $`u_{i,j}(P)=d(x(P))`$. In this case we let $`n_{i+j}:=n_in_j`$ and $`d_{i+j}:=d_id_j`$.

Case iii. Suppose $`g>2`$. If $`r`$ reduction steps are needed, then to compute $`u_{i,j}`$, we obtain intermediate factors $`v_{i,j}^{(1)},\mathrm{},v_{i,j}^{(r)}`$, one factor as in (9) per reduction step. Then $`u_{i,j}`$ will be the product $`u_{i,j}:=v_{i,j}^{(1)}\mathrm{}v_{i,j}^{(r)}d(x(P))`$.

Note: If we evaluate $`n_i`$ and $`d_i`$ at intermediate steps then it is not enough to assume that the divisors $`D`$ and $`E`$ are coprime. Instead, $`E`$ must also be coprime to $`A_i`$ for all $`i`$ which occur in the addition chain for $`m`$. One way to ensure this condition is to require that $`E`$ and $`D`$ be linearly independent and that the polynomial $`p(x)`$ in the pair $`(p(x),q(x))`$ representing $`E`$ be irreducible. There are other ways possible to achieve this, like changing the addition chain for $`m`$.

### 4.5 Estimated savings for genus 2

Using a straightforward implementation of Cantor’s algorithm, the total costs for doubling and addition on the Jacobian of a hyperelliptic curve of genus 2 in odd characteristic, $`C:y^2=f(x)`$, where $`f`$ has degree $`5`$, are as follows. Doubling an element costs $`34`$ multiplications and $`2`$ inversions. Adding two distinct elements of $`J`$ costs $`26`$ multiplications and $`2`$ inversions. More efficient implementations of the group law may alter the total impact of our algorithm. Different field multiplication/inversion ratios and field sizes, as well as differing costs in an extension field will also affect the analysis, but these costs are chosen as representative for the purpose of estimating the savings.

#### 4.5.1 Analysis of standard algorithm

Let $`D:=P_1+P_22P_{\mathrm{}}`$. Let $`R_1`$, $`R_2`$, $`R_3`$, $`R_4`$ be four points on $`C`$ such that $`Q_1+Q_22P_{\mathrm{}}R_1+R_2R_3R_4`$ in $`J`$. The algorithm in  computes $`t_{i+j}`$ from $`t_i`$ and $`t_j`$, where $`t_i=[A_i,n_j,d_j]`$ and

$$\frac{n_j}{d_j}=\frac{h_{j,D}(R_1)h_{j,D}(R_2)}{h_{j,D}(R_3)h_{j,D}(R_4)}.$$

The expression for $`n_{i+j}/d_{i+j}`$ becomes

$`{\displaystyle \frac{n_{i+j}}{d_{i+j}}}={\displaystyle \frac{n_i}{d_i}}{\displaystyle \frac{n_j}{d_j}}{\displaystyle \frac{u_{i,j}(R_1)u_{i,j}(R_2)}{u_{i,j}(R_3)u_{i,j}(R_4)}}.`$
To form $`u_{i,j}`$, we have to perform an addition or doubling step to obtain $`A_{i+j}`$ from $`A_i`$ and $`A_j`$. This costs 34 multiplications and 2 inversions for a doubling, 26 multiplications and 2 inversions for an addition. Then

$$u_{i,j}(P)=\frac{a(x(P))}{b(x(P))+y(P)},$$

and to compute $`(n_{i+j},d_{i+j})`$, we need to evaluate $`u_{i,j}`$ at four different points. Each evaluation of $`a(x(P))`$ costs 2 multiplications in a doubling step, 3 multiplications in an addition step (square or product of monic quadratics). Evaluation of $`b(x(P))`$ (cubic) costs 3 multiplications. Finally we multiply the partial numerators and denominators out, using 5 multiplications each, including the multiplications with $`n_i`$, $`n_j`$, $`d_i`$, and $`d_j`$. So the total cost for an addition step is 60 multiplications and 2 inversions, and the total cost for a doubling is 64 multiplications and 2 inversions.

#### 4.5.2 Squared Tate pairing

The squared Tate pairing works with the divisor $`Q_1Q_1^{}+Q_2Q_2^{}2Q_1+2Q_24P_{\mathrm{}}`$. After adding $`A_i`$ and $`A_j`$ to obtain $`A_{i+j}`$ as above, we need to form

$`{\displaystyle \frac{n_{i+j}}{d_{i+j}}}={\displaystyle \frac{n_i}{d_i}}{\displaystyle \frac{n_j}{d_j}}{\displaystyle \frac{u_{i,j}(Q_1)u_{i,j}(Q_1^{})}{u_{i,j}(Q_2)u_{i,j}(Q_2^{})}}.`$
As can be seen from (10) above, no evaluations of $`a(x(P))`$ are needed. For $`i=1,2`$, we need to evaluate $`b(x(Q_i))`$ and $`b(x(Q_i^{}))`$. This costs only 3 multiplications for each $`i`$, since the $`x`$-coordinates of $`Q_i`$ and $`Q_i^{}`$ are the same. Finally, we have to multiply the partial numerators and denominators, for a total cost of 12 multiplications for either a doubling or an addition.

So the total cost for an addition step is 38 multiplications and 2 inversions, and the total cost for a doubling is 46 multiplications and 2 inversions. Estimating an inversion as 4 multiplications, this is a 25% improvement in the doubling case and a 33% improvement in the addition case.

## 5 Example: $`g=2`$, $`p=31`$, $`m=5`$

In this section, we evaluate the squared Tate pairing on $`5`$-torsion on the Jacobian of a hyperelliptic genus $`2`$ curve over a field of $`31`$ elements. Let $`C`$ be defined by the affine model $`y^2=f(x)`$ where $`f(x)=x^5+13x^4+2x^3+4x^2+11x+1.`$ The group of points on the Jacobian of $`C`$ over $`𝔽_{31}`$ has order $`N=1040`$. Let $`D`$ be the $`5`$-torsion element of the Jacobian of $`C`$ given by the pair of polynomials $`D=[x^2+23x+15,13x+28].`$ Let $`E`$ be the element of the Jacobian of $`C`$ of order $`260`$ given by the pair $`E=[x^2+4x+2,29x+20].`$ Then the squared Tate pairing evaluated at $`D`$ and $`E`$ is $`v_5(D,E)=4,`$ where

$$h_{5,D}=\frac{(x+26)^2(x^4+19x^3+23x^2+16x+19)(x^2+23x+15)}{x^3+6x^2+9x+21+y}.$$

To illustrate the bilinearity of the pairing, look for example at $`2D=[x^2+25x+9,10x+6],`$ $`3D=[x^2+25x+9,21x+25],`$ and $`2E=[x^2+x+3,26x+3].`$ Then we compute that indeed $`v_5(2D,E)=16=v_5(D,E)^2,`$ with

$$h_{5,2D}=\frac{(x+26)(x^4+19x^3+23x^2+16x+19)^2(x^2+25x+9)}{(x^3+6x^2+9x+21+y)^2},$$

and $`v_5(D,2E)=16=v_5(D,E)^2,`$ with $`h_{5,D}`$ as above. Also

$$v_5(3D,E)2v_5(D,E)^3(mod31),$$

with

$$h_{5,3D}=\frac{(x+26)(x^4+19x^3+23x^2+16x+19)^2(x^2+25x+9)}{(30x^3+25x^2+22x+10+y)^2}.$$


text:
# Short-range correlations in asymmetric nuclear matter

## Abstract

The spectral function of protons in the asymmetric nuclear matter is calculated in the self-consistent $`T`$-matrix approach. The spectral function per proton increases with increasing asymmetry. This effect and the density dependence of the spectral function partially explain the observed increase of the spectral function with the mass number of the target nuclei in electron scattering experiments.

short-range correlations, electron scattering, spectral function

21.65.+f, 24.10.Cn, 25.30.-c

The hard core in the free nucleon-nucleon potential induces strong short-range correlations in the nuclear medium. The inclusion of these correlations in the modeling of the nuclear medium is crucial . Variational , Brueckner-Hartree-Fock , and self-consistent $`T`$-matrix  nuclear matter calculations take this effect into account. As a result of the scattering in the medium nucleonic excitations get dressed. A measure of such medium modifications is given by the spectral function, which can be observed in electron scattering experiments. The extraction of the spectral function is relatively straightforward in the Plane Wave Impulse Approximation but important final state rescattering effects complicate the analysis. The knowledge of the spectral function sheds light on the origin of the nuclear binding energy  and gives the nucleon momentum distribution.

Several calculation of the spectral function exists, both for finite systems  and for nuclear matter . At high momentum and high removal energy the spectral function is dominated by short-range correlations which can be studied in the homogeneous nuclear matter. Existing calculations are restricted to symmetric or pure neutron nuclear matter. On the other hand electron scattering experiments are performed on nuclei with a range of values of the neutron to proton ratio $`N/Z`$. The scaled spectral function, i.e. the spectral function divided by the number of protons, was compared for different nuclei and a significant increase with the mass number was observed . This is interpreted as an indication of strong short-range correlations due to neutron-proton scattering which populates the spectral function at high removal energy . In this work we present the first calculation of the proton spectral function in the asymmetric nuclear matter. We discuss the effect of the $`N/Z`$ ratio on the scaled spectral function for different atomic number of the target nuclei.

The calculation is performed in the self-consistent $`T`$-matrix  approach using fermion propagators dressed in the self-consistent self-energy. The scheme is thermodynamically consistent and the obtained single particle properties, i.e. the self-energy and the spectral function are consistent with the global properties such as the binding energy . In the Brueckner approach the spectral function can be reliably calculated only after inclusion of the rearrangement terms . The self-consistent in medium $`T`$-matrix  is

$$T=V+VGGT$$
(1)
where the Green’s functions $`G^1=\omega p^2/2m\mathrm{\Sigma }`$ in the ladder propagator are dressed by the self-consistent self-energy

$$i\mathrm{\Sigma }=Tr[TG].$$
(2)
The details of the calculation can be found in Refs. . The same retarded self-energy $`\mathrm{\Sigma }`$ is used to construct the spectral function

$`A(p,\omega )`$ $`=`$ $`2\mathrm{I}\mathrm{m}G(p,\omega )`$ (3)
$`=`$ $`{\displaystyle \frac{2\mathrm{I}\mathrm{m}\mathrm{\Sigma }(p,\omega )}{(\omega p^2/2m\mathrm{Re}\mathrm{\Sigma }(p,\omega )+\mu )^2+\mathrm{Im}\mathrm{\Sigma }(p,\omega )^2}}.`$
The calculation is done for a range of densities and asymmetries using the CD-Bonn potential. The hole spectral function $`A^h(p,E)=A(p,E)`$ is shown in Fig. 1 as a function of the missing energy for several values of the momentum. The spectral function at normal nuclear density is presented for a symmetric nuclear matter and for $`Z/N=0.7`$. The proton spectral function is larger for the symmetric nuclear matter, but at large missing energy the two curves almost coincide. Since in the asymmetric medium a lower number of p-p collisions is compensated by a more frequent n-p collisions contribution, tensor interaction would lead to a higher scattering rate for high momentum on-shell protons in the asymmetric medium. A far off-shell proton however is scattered in a similar manner in the symmetric and asymmetric nuclear matter. In fact $`|Im\mathrm{\Sigma }(p,\omega )|`$ for protons far off-shell ($`\omega <\mu `$, $`p>p_F`$) is even slightly smaller in the asymmetric than in the symmetric nuclear matter. Far off-shell the value of the spectral function is determined by the imaginary part of the self-energy in the numerator of Eq. 3, and leads to almost no variation of the hole spectral function with asymmetry. Only for energies closer to the quasi-particle pole ($`p>p_F`$, $`\omega >\mu `$) is the scattering of protons larger in the asymmetric nuclear matter, giving a higher on shell width for high momentum protons in the neutron rich nuclear matter.

When comparing different proton densities in the asymmetric nuclear matter the scaled spectral function $`\frac{N+Z}{2Z}A^h(p,\omega )`$ is used, which is a measure of the spectral function per proton. We see that the high energy and high momentum part of the scaled hole spectral function is larger in the asymmetric nuclear matter. The increase of the far off-shell correlations per proton compensates the slight decrease of the proton off-shell scattering rate.

The real-part of the self-energy and the quasiparticle poles depend on the neutron to proton ratio. Accordingly the proton Fermi momentum depends on the proton density, which changes with the proton content. In Fig. 2 is plotted the proton momentum distribution

$$n(p)=\frac{dE}{2\pi }A^h(p,E).$$
(4)
in nuclear matter at normal density for different $`Z/N`$ ratios. The depletion of the occupation number inside the Fermi sphere and the high momentum component in the distribution are given by short-range correlations in the medium. These effects to within a few percent are the same for the proton to neutron ratio changing from $`1`$ to $`0.7`$. The change in the proton density with asymmetry is accommodated by a shift in the proton Fermi momentum.

Experiments with electron scattering on finite nuclei are available for several target masses (C, Al, Fe and Au) . A strong dependence on the target of the scaled proton spectral function was interpreted partly as a signal of strong p-n correlations. The increase of the off-shell hole spectral function per proton when going from C to Au target is about a factor $`2`$. The spectral function at high missing energy and momentum can be calculated using the local density approximation

$$S(p,E)=\frac{2}{(2\pi )^4}d^3rA^h(p,E,\rho (r)).$$
(5)
In Fig. 3 is plotted the spectral function divided by the number of protons for several nuclei. The spectral function depends on the mass number of the target. Part of the increase of the spectral function at high missing energy is due to the different proton to neutron ratio. We have

$$S(p,E)\mathrm{Volume}A_h(p,E)=\frac{Z}{\overline{\rho }_p}A_h(p,E)$$
(6)
where $`\overline{\rho }_p`$ is the mean proton density. The scaled spectral function is

$$\frac{S(p,E)}{Z}\frac{1}{\overline{\rho }_p}A_h(p,E)=\frac{1}{\overline{\rho }}\frac{N+Z}{Z}A_h(p,E).$$
(7)
Since the hole spectral functions $`A_h(p,E)`$ at different proton densities are very similar in the considered region of energy and momentum (Fig. 1) we see from Eq. 7 that the scaled proton spectral function $`S(p,E)/Z`$ increases with the asymmetry for nuclei with the same average density $`\overline{\rho }`$. This effect however is not sufficient to explain quantitatively the observed dependence on the target mass.

The upper curves in Fig. 3 are the spectral functions without dividing by $`Z`$, i.e. the lower curves multiplied by $`12Z/A`$. In a homogeneous matter this rescaling should bring the curves back onto each other as in Fig 1. The remaining difference visible in Fig. 3 is due to the density dependence of the spectral function. Heavier nuclei have a larger mean density which gives rise to stronger short-range correlations. Qualitatively the same effect is seen in the data , but the strongest increase of the proton spectral function happens between Fe and Au targets, and the effect is much more pronounced, especially in the region where the $`\mathrm{\Delta }`$ resonance starts to be visible.

The proton spectral function in the asymmetric nuclear matter is calculated. In the far off-shell region the spectral function does not depend strongly on the proton-neutron asymmetry. It means that the spectral function scaled by the proton number is approximately inversely proportional to the proton density (7). This effect together with density dependence of the spectral function leads to an increase of the scaled proton spectral function with increasing mass number of the target. The experimentally observed increase of the spectral function for heavy target nuclei is stronger than our estimate, especially for the case of gold. Larger frequency of neutron-proton interactions in asymmetric matter leads to a stronger scattering of proton excitation on-shell, but in the off-shell region ($`p>p_F`$, $`\omega <\mu `$) we find that the scattering width $`2|Im\mathrm{\Sigma }(p,\omega )|`$ decreases slightly with the asymmetry.

Acknowledgments This work was partly supported by the KBN under Grant No. 2P03B05925. The author thanks the organizers of the ECT Workshop on “Contributions of Short and Long-range correlations to Nuclear Binding and Saturation” in Trento for a fruitful atmosphere and Daniela Rohe for an illuminating discussion.


text:
# Weak antilocalization in a strained InGaAs/InP quantum well structure

## I Introduction

When spin-orbit scattering is strong the weak localization feature in a 2-dimensional system develops an antilocalization structure Altshuler85 ; Hikami80 . This appears as an additional negative magneto-resistance at very low fields and provides a convenient means of monitoring the spin-orbit interaction Koga02 ; Miller03 ; StudPRB  an understanding of which is needed if spins are to be manipulated for spintronic and quantum computing applications in semiconductors Wolf01 . Results are presented here for a strained InGaAs/InP quantum well, where the antilocalization feature is prominent, but which cannot be explained using currently available theories.

## II Experimental

The QW structure, grown on a (100) InP semi-insulated substrate, consisted of: 450 nm of undoped InP buffer layer, 10 nm InxGa1-xAs (with x=0.76), a 13 nm undoped InP spacer layer, 13 nm of InP doped with Si at $`4\times 10^{17}`$cm-3) and a 13 nm undoped cap layer. Because the lattice constant of InP is 1.53% less than 76% InGaAs the quantum well is compressively strained in the plane. A gated Hall bar was prepared using standard optical lithography and wet etching techniques. At zero gate voltage the concentration was 4.9$`\times `$1015m-2 and the electron mobility 7.8 m2/Vs. Measurements were made in a He3 system with a split tranverse axis superconducting coil.

Figure 1 shows typical magnetoresistance traces at T=0.35 K for various magnetic fields tilted by the angles shown away from the normal to the surface. When plotted against Rxy (which depends only on the normal component of the magnetic field ) it can be seen \[Fig.1(b)\] that the data collapses onto a single curve. That is (at least up to tilt angles of 850) both the weak localization and weak antilocalization (WAL) features depend only on the perpendicular component of the magnetic field and therefore result from orbital motion. This is in contrast to the intuitive expectation that the antilocalization depends on spin and that tilting the magnetic field should decouple the spins from the orbital motion. Similar results have also been observed in an isomorphous (unstrained) sample StudPRB .

Figure 2 shows magnetoconductivity traces for various gate voltages (Vg) between +0.1 V (corresponding to a density of 5.4$`\times `$1015m-2) and -0.6V (1.4$`\times `$1015m-2) A feature of these results is that the WAL peak depends non-monotonically on gate voltage: it is absent at positive gate voltages, increases with decreasing Vg to reach a maximum at -0.3V and then decrease again with further decreases in gate voltage. It is qualitatively evident from Fig. 2 that the spin-orbit scattering parameter $`\beta _{so}`$ (defined as $`\tau /\tau _{so}`$ where $`\tau `$ and $`\tau _{so}`$ are respectively the elastic and spin-orbit scattering times) depends non-monotonically on the gate voltage. The maximum at -0.3V corresponds to a density of 3.4$`\times `$1015m-2. This behaviour cannot be explained by either the Rasba or the Dresselhaus mechanisms Miller03 ; Dresselhaus92 ; StudJETP , both of which predict a monotonic dependence on density.

## III Discussion

The solid lines in Fig. 2 are attempts to fit the data using a recent theory for the weak localization effect valid in arbitrary magnetic fields Gasparyan85 ; Zduniak97 . The data in Fig. 2 are plotted vs normalized magnetic field $`B/B_{tr}`$,where $`B_{tr}=\mathrm{}/4eD\tau `$ is the characteristic transport field. The theory assumes a single spin-orbit scattering mechanism dominates. For InGaAs structures this is expected to be the Rasba term which should be significantly larger than the bulk (Dresselhaus) term. It should be noted that at low magnetic fields this theory coincides with the exact analytical solution due to Hikami, Larkin and Nagaoka Hikami80 . Even under these conditions, that is $`B/B_{tr}<1`$, the theory is unable to adequately describe the experimental data, which indicates that the current theoretical understanding of the weak localisation phenomena, in presence of spin-orbit scattering, is incomplete.

Figure 3a shows how it is possible to fit either the low field (central) part of the magnetoconductivity, or the high field tails, but not both parts simultaneously. Satisfactory fits to the high field region can be made assuming negligible spin-orbit scattering (i.e. $`\beta _{so}`$ = 0). Interestingly, this fit (curve 3) yields the same dephasing rate ($`\beta _\varphi `$) as that obtained from fitting the low field WAL peak (curves 1 and 2) where both $`\beta _{so}`$ and $`\beta _\varphi `$ are allowed to vary. This implies that while the dephasing rate is field independent (as expected) the spin orbit scattering rate decreases quite markedly as the magnetic field increases.

If the main mechanism of spin-orbit relaxation is the spin precession around the effective k-dependent crystal magnetic field that results from the bulk or structural inversion asymmetry Dyakonov86 ; Lau01 ; Winkler03  then it would be reasonable to assume that this precession will be affected by external magnetic fields larger than the effective spin-orbit field $`B_{so}`$. $`B_{so}`$ is typically smaller than 1 mT so one might expect the spin precession to be disturbed by external fields of this order. We have been unable to find any theoretical discussion of this effect in the literature and have therefore used an empirical approach. We postulate that the spin orbit scattering rate decreases with increasing field in a Lorentzian fashion, ie that $`\beta _{so}=\tau /\tau _{so}=\beta _{so}^0/(1+aB^2)`$. Using this expression, with the introduction of an additional fitting parameter a, allows quite satisfactory fits to the experimental data (see Fig. 3(b)). Due to space limitations discussion of the parameters determined in the fits must be deferred to another publication but it can be noted that the values of $`a^{1/2}`$ correspond to fields of order of 0.1 mT.

## IV Conclusion

In contrast to intuitive expectation it is found that experimental weak antilocalization and weak localization peaks respond in the same way to tilted magnetic fields and depend only on the normal component of field. To fit the shape of the peaks it was found necessary to assume that the spin-orbit scattering parameter decreases with increasing magnetic fields. Although this can be understood qualitatively in terms of quenching of the precession around internal, spin- orbit related, magnetic fields an improved theoretical treatment is needed if an understanding of the electron transport properties and microscopical spin dynamics in gated semiconductor structures is to be achieved.

### IV.1 Acknowledgements

S.A.S acknowledges support of The Canadian Institute for Advanced Research (CIAR). We would like to thank Chandre Dharma-wardana for helpful discussion.