Jacobian curve

Definition: Jacobi intersection

An elliptic curve in P³(K) can be represented as the intersection of two quadric surfaces:

${\displaystyle Q:\{Q_1(X_0,X_1,X_2,X_3)=0\}\cap \{Q_2(X_0,X_1,X_2,X_3)=0\}}$

It is possible to define the Jacobi form of an elliptic curve as the intersection of two quadrics. Let E_a,b be an elliptic curve in the Weierstrass form, we apply the following map to it:

${\displaystyle \mathrm{\Phi }:(x,y)\mapsto (X,Y,Z,T)=(x,y,1,x^2)}$

We see that the following system of equations holds:

${\displaystyle \mathbf{S}:\{\begin{array}{l}{X}^2-TZ=0\\ Y^2-aXZ-b{Z}^2-TX=0\end{array}}$

The curve E[j] corresponds to the following intersection of surfaces in P³(K):

${\displaystyle \mathbf{S}1:\{\begin{array}{l}{X}^2+Y^2-T^2=0\\ k{X}^2+Z^2-T^2=0\end{array}}$.

The "special case", E[0], the elliptic curve has a double point and thus it is singular.

S1 is obtained by applying to E[j] the transformation:

ψ: E[j] → S1

${\displaystyle (x,y)\mapsto (X,Y,Z,T)=(-2y,x^2-j,x^2+2jx+j,x^2+2x+j)}$

${\displaystyle O=(0:1:0)\mapsto (0,1,1,1)}$

Group law

For S1, the neutral element of the group is the point (0, 1, 1, 1), that is the image of O = (0: 1: 0) under ψ.

Addition and doubling

Given P₁ = (X₁, Y₁, Z₁, T₁) and P₂ = (X₂, Y₂, Z₂, T₂), two points on S1, the coordinates of the point P₃ = P₁ + P₂ are:

${\displaystyle X_3=T_1{Y}_2{X}_1{Z}_2+Z_1{X}_2{Y}_1{T}_2}$

${\displaystyle Y_3=T_1{Y}_2{Y}_1{T}_2-Z_1{X}_2{X}_1{Z}_2}$

${\displaystyle Z_3=T_1{Z}_1{T}_2{Z}_2-k{X}_1{Y}_1{X}_2{Y}_2}$

${\displaystyle T_3=(T_1{Y}_2{)}^2+(Z_1{X}_2{)}^2}$

These formulas are also valid for doubling: it sufficies to have P₁ = P₂. So adding or doubling points in S1 are operations that both require 16 multiplications plus one multiplication by a constant (k).

It is also possible to use the following formulas for doubling the point P₁ and find P₃ = [2]P₁:

${\displaystyle X_3=2Y_1{T}_1{Z}_1{X}_1}$

${\displaystyle Y_3=(T_1{Y}_1{)}^2-(T_1{Z}_1{)}^2+(Z_1{Y}_1{)}^2}$

${\displaystyle Z_3=(T_1{Z}_1{)}^2-(T_1{Y}_1{)}^2+(Z_1{Y}_1{)}^2}$

${\displaystyle T_3=(T_1{Z}_1{)}^2+(T_1{Y}_1{)}^2-(Z_1{Y}_1{)}^2}$

Using these formulas 8 multiplications are needed to double a point. However, there are even more efficient “strategies” for doubling that require only 7 multiplications. In this way it is possible to triple a point with 23 multiplications; indeed [3]P₁ can be obtained by adding P₁ with [2]P₁ with a cost of 7 multiplications for [2]P₁ and 16 for P₁ + [2]P₁

Example of addition and doubling

Let K = R or C and consider the case:

${\displaystyle \mathbf{S}1:\{\begin{array}{l}{X}^2+Y^2-T^2=0\\ 4X^2+Z^2-T^2=0\end{array}}$

Consider the points ${\displaystyle P_1=(1,\sqrt{3},0,2)}$ and ${\displaystyle P_2=(1,2,1,\sqrt{5})}$: it is easy to verify that P₁ and P₂ belong to S1 (it is sufficient to see that these points satisfy both equations of the system S1).

Using the formulas given above for adding two points, the coordinates for P₃, where P₃ = P₁ + P₂ are:

${\displaystyle X_3=T_1{Y}_2{X}_1{Z}_2+Z_1{X}_2{Y}_1{T}_2=4}$

${\displaystyle Y_3=T_1{Y}_2{Y}_1{T}_2-Z_1{X}_2{X}_1{Z}_2=4\sqrt{15}}$

${\displaystyle Z_3=T_1{Z}_1{T}_2{Z}_2-k{X}_1{Y}_1{X}_2{Y}_2=-8\sqrt{3}}$

${\displaystyle T_3=(T_1{Y}_2{)}^2+(Z_1{X}_2{)}^2=16}$

The resulting point is ${\displaystyle P_3=(4,4\sqrt{15},-8\sqrt{3},16)}$.

With the formulas given above for doubling, it is possible to find the point P₃ = [2]P₁:

${\displaystyle X_3=2Y_1{T}_1{Z}_1{X}_1=0}$

${\displaystyle Y_3=(T_1{Y}_1{)}^2-(T_1{Z}_1{)}^2+(Z_1{Y}_1{)}^2=12}$

${\displaystyle Z_3=(T_1{Z}_1{)}^2-(T_1{Y}_1{)}^2+(Z_1{Y}_1{)}^2=-12}$

${\displaystyle T_3=(T_1{Z}_1{)}^2+(T_1{Y}_1{)}^2-(Z_1{Y}_1{)}^2=12}$

So, in this case P₃ = [2]P₁ = (0, 12, –12, 12).

Negation

Given the point P₁ = (X₁, Y₁, Z₁, T₁) in S1, its negation is −P₁ = (−X₁, Y₁, Z₁, T₁)

Addition and doubling in affine coordinates

Given two affine points P₁ = (x₁, y₁, z₁) and P₂ = (x₂, y₂, z₂), their sum is a point P₃ with coordinates:

${\displaystyle x_3=\frac{y_2{x}_1{z}_2+z_1{x}_2{y}_1}{(y_2^2+(z_1{x}_2{)}^2)}}$

${\displaystyle y_3=\frac{y_2{y}_1-z_1{x}_2{x}_1{z}_2}{(y_2^2+(z_1{x}_2{)}^2)}}$

${\displaystyle z_3=\frac{z_1{z}_2-a{x}_1{y}_1{x}_2{y}_2}{(y_2^2+(z_1{x}_2{)}^2)}}$

These formulas are valid also for doubling with the condition P₁ = P₂.

Extended coordinates

There is another kind of coordinate system with which a point in the Jacobi intersection can be represented. Given the following elliptic curve in the Jacobi intersection form:

${\displaystyle \mathbf{S}1:\{\begin{array}{l}{x}^2+y^2=1\\ k{x}^2+z^2=1\end{array}}$

the extended coordinates describe a point P = (x, y, z) with the variables X, Y, Z, T, XY, ZT, where:

${\displaystyle x=X/T}$

${\displaystyle y=Y/T}$

${\displaystyle z=Z/T}$

${\displaystyle XY=X\cdot Y}$

${\displaystyle ZT=Z\cdot T}$

Sometimes these coordinates are used, because they are more convenient (in terms of time-cost) in some specific situations. For more information about the operations based on the use of these coordinates see http://hyperelliptic.org/EFD/g1p/auto-jintersect-extended.html

Definition: Jacobi quartic

An elliptic curve in Jacobi quartic form can be obtained from the curve E_a,b in the Weierstrass form with at least one point of order 2. The following transformation f sends each point of E_a,b to a point in the Jacobi coordinates, where (X: Y: Z) = (sX: s²Y: sZ).

f: E_a,b → J

${\displaystyle (p,0)\mapsto (0:-1:1)}$

${\displaystyle (x,y)\ne (p,0)\mapsto (2(x-p):(2x+p)(x-p{)}^2-y^2:y)}$

${\displaystyle O\mapsto (0:1:1)}$

Applying f to E_a,b, one obtains a curve in J of the following form:

${\displaystyle C:Y^2=e{X}^4-2d{X}^2{Z}^2+Z^4}$

where:

${\displaystyle e=\frac{-(3p^2+4a)}{16},d=\frac{3p}{4}}$.

are elements in K. C represents an elliptic curve in the Jacobi quartic form, in Jacobi coordinates.

Jacobi quartic in affine coordinates

The general form of a Jacobi quartic curve in affine coordinates is:

${\displaystyle y^2=e{x}^4+2a{x}^2+1}$,

where often e = 1 is assumed.

Group law

The neutral element of the group law of C is the projective point (0: 1: 1).

Addition and doubling in affine coordinates

Given two affine points ${\displaystyle P_1=(x_1,y_1)}$ and ${\displaystyle P_2=(x_2,y_2)}$, their sum is a point ${\displaystyle P_3=(x_3,y_3)}$, such that:

${\displaystyle x_3=\frac{x_1{y}_2+y_1{x}_2}{1-e(x_1{x}_2{)}^2}}$

${\displaystyle y_3=\frac{((1+e(x_1{x}_2{)}^2)(y_1{y}_2+2a{x}_1{x}_2)+2e{x}_1{x}_2({x_1}^2+{x_2}^2))}{(1-e(x_1{x}_2{)}^2{)}^2}}$

As in the Jacobi intersections, also in this case it is possible to use this formula for doubling as well.

Addition and doubling in projective coordinates

Given two points P₁ = (X₁: Y₁: Z₁) and P₂ = (X₂: Y₂: Z₂) in C′, the coordinates for the point P₃ = (X₃: Y₃: Z₃), where P₃ = P₁ + P₂, are given in terms of P₁ and P₂ by the formulae:

${\displaystyle X_3=X_1{Z}_1{Y}_2+Y_1{X}_2{Z}_2}$

${\displaystyle Y_3=\left(Z_1^2{Z}_2^2+e{X}_1^2{X}_2^2\right)\left(Y_1{Y}_2-2a{X}_1{X}_2{Z}_1{Z}_2\right)+2e{X}_1{X}_2{Z}_1{Z}_2\left(X_1^2{Z}_2^2+Z_1^2{X}_2^2\right)}$

${\displaystyle Z_3=Z_1^2{Z}_2^2-e{X}_1^2{X}_2^2}$

One can use this formula also for doubling, with the condition that P₂ = P₁: in this way the point P₃ = P₁ + P₁ = [2]P₁ is obtained.

The number of multiplications required to add two points is 13 plus 3 multiplications by constants: in particular there are two multiplications by the constant e and one by the constant a.

There are some "strategies" to reduce the operations required for adding and doubling points: the number of multiplications can be decreased to 11 plus 3 multiplications by constants (see section 3 for more details).

The number of multiplications can be reduced by working on the constants e and d: the elliptic curve in the Jacobi form can be modified in order to have a smaller number of operations for adding and doubling. So, for example, if the constant d in C is significantly small, the multiplication by d can be cancelled; however the best option is to reduce e: if it is small, not only one, but two multiplications are neglected.

Example of addition and doubling

Consider the elliptic curve E_4,0, it has a point P of order 2: P = (p, 0) = (0, 0). Therefore, a = 4, b = p = 0 so we have e = 1 and d = 1 and the associated Jacobi quartic form is:

${\displaystyle C:Y^2=X^4+Z^4}$

Choosing two points ${\displaystyle P_1=(1:\sqrt{2}:1)}$ and ${\displaystyle P_2=(2:\sqrt{17}:1)}$, it is possible to find their sum P₃ = P₁ + P₂ using the formulae for adding given above:

${\displaystyle X_3=1\cdot 1\cdot \sqrt{17}+\sqrt{2}\cdot 2\cdot 1=\sqrt{17}+2\sqrt{2}}$

${\displaystyle Y_3=\left(1^2\cdot 1^2+1\cdot 1^2\cdot 2^2\right)\left(\sqrt{2}\cdot \sqrt{17}-2\cdot 0\cdot 1\cdot 2\cdot 1\cdot 1\right)+2\cdot 1\cdot 1\cdot 2\cdot 1\cdot 1\left(1^2\cdot 1^2+1^2\cdot 2^2\right)=5\sqrt{34}+20}$

${\displaystyle Z_3=1^2\cdot 1^2-1\cdot 1^2\cdot 2^2=-3}$.

So

${\displaystyle P_3=(\sqrt{17}+2\sqrt{2}:5\sqrt{34}+20:-3)}$.

Using the same formulae, the point P₄ = [2]P₁ is obtained:

${\displaystyle X_3=1\cdot 1\cdot \sqrt{2}+\sqrt{2}\cdot 1\cdot 1=2\sqrt{2}}$

${\displaystyle Y_3=\left(1+1\cdot 1\right)\left(\sqrt{2}\cdot \sqrt{2}-2\cdot 0\cdot 1\cdot 1\cdot 1\cdot 1\right)+2\cdot 1\left(1^2\cdot 1^2+1^2\cdot 1^2\right)=8}$

${\displaystyle Z_3=1^2\cdot 1^2-1\cdot 1^2\cdot 1^2=0}$

So

${\displaystyle P_4=(2\sqrt{2}:8:0)}$.

Negation

The negation of a point P₁ = (X₁: Y₁: Z₁) is: −P₁ = (−X₁: Y₁: Z₁)

Alternative coordinates for the Jacobi quartic

There are other systems of coordinates that can be used to represent a point in a Jacobi quartic: they are used to obtain fast computations in certain cases. For more information about the time-cost required in the operations with these coordinates see http://hyperelliptic.org/EFD/g1p/auto-jquartic.html

Given an affine Jacobi quartic

${\displaystyle y^2=x^4+2a{x}^2+1}$

the Doubling-oriented XXYZZ coordinates introduce an additional curve parameter c satisfying a² + c² = 1 and they represent a point (x, y) as (X, XX, Y, Z, ZZ, R), such that:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/ZZ}$

${\displaystyle XX=X^2}$

${\displaystyle ZZ=Z^2}$

${\displaystyle R=2\cdot X\cdot Z}$

the Doubling-oriented XYZ coordinates, with the same additional assumption (a² + c² = 1), represent a point (x, y) with (X, Y, Z) satisfying the following equations:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/Z^2}$

Using the XXYZZ coordinates there is no additional assumption, and they represent a point (x, y) as (X, XX, Y, Z, ZZ) such that:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/ZZ}$

${\displaystyle XX=X^2}$

${\displaystyle ZZ=Z^2}$

while the XXYZZR coordinates represent (x, y) as (X, XX, Y, Z, ZZ, R) such that:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/ZZ}$

${\displaystyle XX=X^2}$

${\displaystyle ZZ=Z^2}$

${\displaystyle R=2\cdot X\cdot Z}$

with the XYZ coordinates the point (x, y) is given by (X, Y, Z), with:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/Z^2}$.