# A Mean Value Formula for Elliptic Curves

Authors: Rongquan Feng; Hongfeng Wu
Journal: Journal of Numbers
 (2014)

---

## Abstract

It is proved in this paper that, for any point on an elliptic curve, the mean value ofx-coordinates of its n-division points is the same as its x-coordinate and that of y-coordinates of its n-division points is n times that of its y-coordinate.


---

## Body

## 1. Introduction

LetK be a field with char(K)≠2,3 and let K¯ be the algebraic closure of K. Every elliptic curve E over K can be written as a classical Weierstrass equation as follows:
(1)E:y2=x3+ax+bwith coefficientsa,b∈K. A point Q on E is said to be smooth (or nonsingular) if (∂f/∂x|Q,∂f/∂y|Q)≠(0,0), where f(x,y)=y2-x3-ax-b. The point multiplication is the operation of computing
(2)nP=P+P+⋯+P︸nfor any pointP∈E and a positive integer n. The multiplication-by-n map
(3)[n]:E⟶EP⟼nPis an isogeny of degreen2. For a point Q∈E, any element of [n]-1(Q) is called an n-division point of Q. Assume that (char(K),n)=1. In this paper, the following result on the mean value of the x,y-coordinates of all the n-division points of any smooth point on an elliptic curve is proved.Theorem 1.
LetE be an elliptic curve defined over K and let Q=(xQ,yQ)∈E be a point with Q≠O. Set
(4)Λ={P=(xP,yP)∈E(K¯)∣nP=Q}.
Then(5)1n2∑P∈Λ‍xP=xQ,1n2∑P∈Λ‍yP=nyQ.According to Theorem1, let Pi=(xi,yi), i=1,2,…,n2, be all the points such that nP=Q and let λi be the slope of the line through Pi and Q; then yQ=λi(xQ-xi)+yi. Therefore,
(6)n2yQ=∑i=1n2‍λi·∑i=1n2xin2-∑i=1n2‍λixi+∑i=1n2‍yi.Thus we have(7)yQ=∑i=1n2λin2·∑i=1n2xin2-∑i=1n2λixin2+∑i=1n2yin2=λi¯·xi¯-λixi¯+yi¯,
where λi¯, xi¯, λixi¯, and yi¯ are the average values of the variables λi, xi, λixi, and yi, respectively. Therefore,
(8)Q=(xQ,yQ)=(xi¯,λi¯·xi¯-λixi¯+yi¯)=(xi¯,1nyi¯).Remark 2.
The discrete logarithm problem in elliptic curveE is to find n by given P,Q∈E with Q=nP. The above theorem gives some information on the integer n.


## 2. Proof of Theorem1

To prove Theorem1, define division polynomials [1] ψn∈Z[x,y,a,b] on an elliptic curve E:y2=x3+ax+b inductively as follows:
(9)ψ0=0,ψ1=1,ψ2=2y,ψ3=3x4+6ax2+12bx-a2,ψ4=4y(x6+5ax4+20bx3-5a2x2-4abx-8b2-a3),ψ2n+1=ψn+2ψn3-ψn-1ψn+13,forn≥2,2yψ2n=ψn(ψn+2ψn-12-ψn-2ψn+12),forn≥3.It can be checked easily by induction that theψ2n’s are polynomials. Moreover, ψn∈Z[x,y2,a,b] when n is odd, and (2y)-1ψn∈Z[x,y2,a,b] when n is even. Define the polynomial
(10)ϕn=xψn2-ψn-1ψn+1forn≥1. Then ϕn∈Z[x,y2,a,b]. Since y2=x3+ax+b, replacing y2 by x3+ax+b, one has ϕn∈Z[x,a,b]. So we can denote it by ϕn(x). Note that ψnψm∈Z[x,a,b] if n and m have the same parity. Furthermore, the division polynomials ψn have the following properties.Lemma 3.
Consider(11)ψn=nx(n2-1)/2+n(n2-1)(n2+6)60ax(n2-5)/2+lowerdegreeterms,
whenn is odd and
(12)ψn=ny(x(n2-4)/2+(n2-1)(n2+6)-3060ax(n2-8)/2111+lowerdegreeterms(n2-1)(n2+6)-3060),
whenn is even.Proof.
We prove the result by induction onn. It is true for n<5. Assume that it holds for all ψm with m<n. We give the proof only for the case for odd n≥5. The case for even n can be proved similarly. Now let n=2k+1 be odd, where k≥2. If k is even, then by induction
(13)ψk=ky(x(k2-4)/2+(k2-1)(k2+6)-306011111111111×ax(k2-8)/2+⋯(k2-1)(k2+6)-3060),ψk+2=(k+2)yψk+2=×(x(k2+4k)/2+(k2+4k+3)(k2+4k+10)-306011111111111×ax(k2+4k-4)/2+⋯(k2+4k+3)(k2+4k+10)-3060),ψk-1=(k-1)x(k2-2k)/2ψk-1=+(k-1)(k2-2k)(k2-2k+7)60ψk-1=×ax(k2-2k-4)/2+⋯,ψk+1=(k+1)x(k2+2k)/2ψk+1=+(k+1)(k2+2k)(k2+2k+7)60ψk+1=×ax(k2+2k-4)/2+⋯.
Substitutingy4 by (x3+ax+b)2, we have
(14)ψk+2ψk3=k3(k+2)×(x2k2+2k+4(k+1)(k3+k2+10k+3)601111111×ax2k2+2k-2+⋯4(k+1)(k3+k2+10k+3)60),ψk-1ψk+13=(k-1)(k+1)3x2k2+2k+4k(k-1)(k3+2k2+11k+7)(k+1)360×ax2k2+2k-2+⋯.
Therefore,(15)ψ2k+1=ψk+2ψk3-ψk-1ψk+13=(2k+1)x2k2+2k+(2k+1)(4k2+4k)(4k2+4k+7)60×ax2k2+2k-2+⋯=(2k+1)x((2k+1)2-1)/2+(2k+1)((2k+1)2-1)((2k+1)2+6)60×ax((2k+1)2-5)/2+⋯.
The case whenk is odd can be proved similarly.The following corollary follows immediately from Lemma3.Corollary 4.
Consider(16)ψn2=n2xn2-1-n2(n2-1)(n2+6)30axn2-3+⋯,ϕn=xn2-n2(n2-1)6axn2-2+⋯.Proof of Theorem1.
Defineωn as
(17)4yωn=ψn+2ψn-12-ψn-2ψn+12.
Then for anyP=(xP,yP)∈E, we have ([1])
(18)nP=(ϕn(xP)ψn2(xP),ωn(xP,yP)ψn(xP,yP)3).
IfnP=Q, then ϕn(xP)-xQψn2(xP)=0. Therefore, for any P∈Λ, the x-coordinate of P satisfies the equation ϕn(x)-xQψn2(x)=0. From Corollary 4, we have that
(19)ϕn(x)-xQψn2(x)=xn2-n2xQxn2-1+lowerdegreeterms.
Since♯Λ=n2, every root of ϕn(x)-xQψn2(x) is the x-coordinate of some P∈Λ. Therefore,
(20)∑P∈Λ‍xP=n2xQ
by Vitae’s theorem.
Now we prove the mean value formula fory-coordinates. Let K be the complex number field C first and let ω1 and ω2 be complex numbers which are linearly independent over R. Define the lattice
(21)L=Zω1+Zω2={n1ω1+n2ω2∣n1,n2∈Z}
and the Weierstrass℘-function by
(22)℘(z)=℘(z,L)=1z2+∑ω∈L,ω≠0(1(z-ω)2-1ω2).
For integersk≥3, define the Eisenstein series Gk by
(23)Gk=Gk(L)=∑ω∈L,ω≠0‍ω-k.
Setg2=60G4 and g3=140G6; then
(24)℘′(z)2=4℘(z)3-g2℘(z)-g3.
LetE be the elliptic curve given by y2=4x3-g2x-g3. Then the map
(25)CL⟶E(C)z⟼(℘(z),℘′(z)),0⟼∞
is an isomorphism of groupsC/L and E(C). Conversely, it is well known [1] that, for any elliptic curve E over C defined by y2=x3+ax+b, there is a lattice L such that g2(L)=-4a,g3(L)=-4b and there is an isomorphism between groups C/L and E(C) given by z↦(℘(z),(1/2)℘′(z)) and 0↦∞. Therefore, for any point (x,y)∈E(C), we have (x,y)=(℘(z),(1/2)℘′(z)) and n(x,y)=(℘(nz),(1/2)℘′(nz)) for some z∈C.
LetQ=(℘(zQ),(1/2)℘′(zQ)) for a zQ∈C. Then for any Pi∈Λ, 1≤i≤n2, there exist integers j,k with 0≤j,k≤n-1, such that
(26)Pi=(℘(zQn+jnω1+knω2),12℘′(zQn+jnω1+knω2)).
Thus,(27)∑j,k=0n-1‍℘(zQn+jnω1+knω2)=n2℘(zQ)
which comes from∑i=1n2xi=n2xQ. Differentiate with respect to zQ, we have
(28)∑j,k=0n-1‍℘′(zQn+jnω1+knω2)=n3℘′(zQ).
That is,(29)∑i=1n2‍yi=n3yQ.
Secondly, letK be a field of characteristic 0 and let E be the elliptic curve over K given by the equation y2=x3+ax+b. Then all of the equations describing the group law are defined over Q(a,b). Since C is algebraically closed and has infinite transcendence degree over Q, Q(a,b) can be considered as a subfield of C. Therefore we can regard E as an elliptic curve defined over C. Thus the result follows.
At last assume thatK is a field of characteristic p. Then the elliptic curve can be viewed as one defined over some finite field Fq, where q=pm for some integer m. Without loss of generality, let K=Fq for convenience. Let K′=Qq be an unramified extension of the p-adic numbers Qp of degree m, and let E¯ be an elliptic curve over K′ which is a lift of E. Since (n,p)=1, the natural reduction map E¯[n]→E[n] is an isomorphism. Now for any point Q∈E with Q≠O, we have a point Q¯∈E¯ such that the reduction point is Q. For any point Pi∈E(K¯) with nPi=Q, its lifted point P¯i satisfies nP¯i=Q¯ and P¯i≠P¯j whenever Pi≠Pj. Thus,
(30)∑i=1n2‍y(P¯i)=n3y(Q¯),
sinceK′ is a field of characteristic 0. Therefore the formula ∑i=1n2yi=n3yQ holds by the reduction from E¯ to E.Remark 5.
(1)
The result forx-coordinate of Theorem 1 holds also for the elliptic curve defined by the general Weierstrass equation y2+a1xy+a3y=x3+a2x2+a4x+a6.
(2)
The mean value formula forx-coordinates was given in the first version of this paper [2] with a slightly complicated proof. The formula for y-coordinates was conjectured by Feng and Wu based on [2] and numerical examples in a personal email communication with Moody (June 1, 2010).
(3)
Recently, some mean value formulae for twisted Edwards curves [3, 4] and other alternate models of elliptic curves were given by [5, 6].


## 3. An Application

LetE be an elliptic curve over K given by the Weierstrass equation y2=x3+ax+b. Then we have a nonzero invariant differential ω=dx/y. Let ϕ∈End(E) be a nonzero endomorphism. Then ϕ*ω=ω∘ϕ=cϕω for some cϕ∈K¯(E), since the space ΩE of differential forms on E is a 1-dimensional K¯(E)-vector space. Since cϕ≠0 and div⁡(ω)=0, we have
(31)div⁡(cϕ)=div⁡(ϕ*ω)-div⁡(ω)=ϕ*div⁡(ω)-div⁡(ω)=0.Hencecϕ has neither zeros nor poles and cϕ∈K¯. Let φ and ψ be two nonzero endomorphisms; then
(32)cφ+ψω=(φ+ψ)*ω=φ*ω+ψ*ω=cφω+cψω=(cφ+cψ)ω.Therefore,cφ+ψ=cφ+cψ. For any nonzero endomorphism ϕ, set ϕ(x,y)=(Rϕ(x),ySϕ(x)), where Rϕ and Sϕ are rational functions. Then
(33)cϕ=Rϕ′(x)Sϕ(x),
where Rϕ′(x) is the differential of Rϕ(x). In particular, for any positive integer n, the map [n] on E is an endomorphism. Set [n](x,y)=(Rn(x),ySn(x)). From c[1]=1 and [n]=[1]+[(n-1)], we have
(34)c[n]=Rn′(x)Sn(x)=n.For anyQ=(xQ,yQ)∈E and any
(35)P=(xP,yP)∈Λ={P=(xP,yP)∈E(K¯)∣nP=Q},we haveyP=yQ/Sn(xP). Therefore, Theorem 1 gives
(36)∑P∈Λ‍1Sn(xP)=∑P∈Λ‍yPyQ=1yQ∑P∈Λ‍yP=n3.Thus,(37)∑P∈Λ‍1Rn′(xP)=∑P∈Λ‍1n·Sn(xP)=1n∑P∈Λ‍1Sn(xP)=n2,∑P∈Λ‍xQRn′(xP)=xQ∑P∈Λ‍1Rn′(xP)=n2xQ=∑P∈Λ‍xP.



---

*Source: 298632-2014-08-25.xml*