A Mean Value Formula for Elliptic Curves

Theorem 1. Let E be an elliptic curve defined over K and let Q = (x_Q, y_Q) ∈ E be a point with $$. Set

Then

Remark 2. The discrete logarithm problem in elliptic curve E is to find n by given P, Q ∈ E with Q = nP. The above theorem gives some information on the integer n.

Lemma 3. Consider

when n is odd and

when n is even.

Proof. We prove the result by induction on n. 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

Substituting y⁴ by (x³ + ax + b) ², we have

Therefore,

The case when k is odd can be proved similarly.

Corollary 4. Consider

Proof of Theorem 1. Define ω_n as

Then for any P = (x_P, y_P) ∈ E, we have ([1])

If nP = Q, then $$. Therefore, for any P ∈ Λ, the x-coordinate of P satisfies the equation $$. From Corollary 4, we have that

Since ♯Λ = n², every root of $$ is the x-coordinate of some P ∈ Λ. Therefore,

by Vitae’s theorem.

Now we prove the mean value formula for y-coordinates. Let K be the complex number field $$ first and let ω₁ and ω₂ be complex numbers which are linearly independent over $$. Define the lattice

and the Weierstrass ℘-function by

For integers k ≥ 3, define the Eisenstein series G_k by

Set g₂ = 60G₄ and g₃ = 140G₆; then

Let E be the elliptic curve given by y² = 4x³ − g₂x − g₃. Then the map

is an isomorphism of groups $$ and $$. Conversely, it is well known [1] that, for any elliptic curve E over $$ defined by y² = x³ + ax + b, there is a lattice L such that g₂(L) = −4a, g₃(L) = −4b and there is an isomorphism between groups $$ and $$ given by z ↦ (℘(z), (1/2)℘^′(z)) and 0 ↦ ∞. Therefore, for any point $$, we have (x, y) = (℘(z), (1/2)℘^′(z)) and n(x, y) = (℘(nz), (1/2)℘^′(nz)) for some $$.

Let Q = (℘(z_Q), (1/2)℘^′(z_Q)) for a $$. Then for any P_i ∈ Λ, 1 ≤ i ≤ n², there exist integers j, k with 0 ≤ j, k ≤ n − 1, such that

Thus,

which comes from $$. Differentiate with respect to z_Q, we have

That is,

Secondly, let K be a field of characteristic 0 and let E be the elliptic curve over K given by the equation y² = x³ + ax + b. Then all of the equations describing the group law are defined over $$. Since $$ is algebraically closed and has infinite transcendence degree over $$, $$ can be considered as a subfield of $$. Therefore we can regard E as an elliptic curve defined over $$. Thus the result follows.

At last assume that K is a field of characteristic p. Then the elliptic curve can be viewed as one defined over some finite field $$, where q = p^m for some integer m. Without loss of generality, let $$ for convenience. Let $$ be an unramified extension of the p-adic numbers $$ of degree m, and let $$ be an elliptic curve over K^′ which is a lift of E. Since (n, p) = 1, the natural reduction map $$ is an isomorphism. Now for any point Q ∈ E with $$, we have a point $$ such that the reduction point is Q. For any point $$ with nP_i = Q, its lifted point $$ satisfies $$ and $$ whenever P_i ≠ P_j. Thus,

since K^′ is a field of characteristic 0. Therefore the formula $$ holds by the reduction from $$ to E.

Remark 5.

• (1)

  The result for x-coordinate of Theorem 1 holds also for the elliptic curve defined by the general Weierstrass equation y² + a₁xy + a₃y = x³ + a₂x² + a₄x + a₆.

• (2)

  The mean value formula for x-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].