Elliptic curve

This article covers elliptic curves. For the ellipse as a geometric figure, see Ellipse .

Elliptic curve over the field of real numbers ${\displaystyle 5y^{2}=x^{3}-3x+5}$

In mathematics , elliptic curves are special algebraic curves on which an addition is geometrically defined. This addition is used in cryptography to construct secure encryption methods. But elliptic curves also play an important role in pure mathematics. Historically, they were created through the parameterization of elliptic integrals as their inverse functions ( elliptic functions ).

An elliptic curve is a smooth 3-order algebraic curve in the projective plane . Elliptic curves are usually shown as curves in the affine plane , but they also have an additional point at infinity.

Elliptic curves over the field of real numbers can be viewed as the set of all (affine) points that make up the equation ${\displaystyle (x,y)\in \mathbb {R} ^{2}}$

${\displaystyle y^{2}=x^{3}+ax+b}$

meet, along with a so-called point at infinity (notated as or ). The (real) coefficients and must meet the condition that for the discriminant of the cubic polynomial in on the right-hand side applies in order to exclude singularities (the roots of the polynomial are then different in pairs, the curve has no colons or other singularities). ${\displaystyle \infty }$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle x}$ ${\displaystyle -4a^{3}-27b^{2}\neq 0}$

In general, when considering the given equation, one will not limit oneself to the case of real coefficients and solutions, but rather consider the case where the coefficients and solutions originate from the field of complex numbers . Elliptic curves over the field of rational numbers , over finite fields and over p-adic fields have also been extensively investigated . The theory of elliptic curves therefore combines very different areas of mathematics. The investigation of elliptical curves over the rational numbers or finite fields is the subject of number theory and a special case of the Abelian varieties, which are also considered in higher dimensions . Your investigation of complex numbers is a classic area of function theory .

Each elliptic curve over the complex numbers can be represented as a complex torus with the help of a grid in the complex number plane , which already results from the double periodicity of elliptic functions (see Weierstrasse elliptic function ). Its Riemann surface is topologically a torus and, through the associated division of the complex plane by a lattice, an Abelian group. This group structure also carries over to elliptic curves over the rational numbers and to a special kind of addition for points on elliptic curves (see below). In 1994, the mathematician Andrew Wiles proved the modularity theorem , which says that all elliptic curves over the rational numbers are parameterized by modular forms . From this theorem the proof of a known number theoretic problem ( Fermat's last theorem ) can be inferred.

Elliptic curves find practical application in modern encryption methods ( elliptic curve cryptosystem ), which use the above-mentioned special addition of points on elliptic curves for the definition of one-way functions . Further applications can be found in the factorization of natural numbers .

Solutions to the equation for different values ​​of . In this case the curve is singular and therefore not an elliptic curve ${\displaystyle y^{2}=x^{3}+ax+b}$ ${\displaystyle (a,b)}$ ${\displaystyle (a,b)=(0,0)}$

If polynomials higher than the fourth degree are considered instead of cubic polynomials, hyperelliptic curves are obtained (which have a higher topological gender).

history

The theory of elliptic curves initially developed in the context of function theory . With various geometric or physical problems - for example, when determining the arc length of ellipses  - elliptical integrals occur. These integral functions could inverse functions are determined. Because of this context, these meromorphic functions were called elliptic functions (for their history see there). As will be shown below, one can unambiguously assign a torus to every elliptic curve over the field of complex numbers by means of elliptic functions . In this way the elliptical curves can be classified and it is because of this relationship that they got their name. ${\displaystyle \mathbb {C} }$

Since the end of the 19th century, arithmetic and number theoretic questions have been at the center of the theory. It could be shown that elliptic curves can be meaningfully defined on general bodies and it was shown - as already described above - that an elliptic curve can be interpreted as a commutative group (which goes back to Henri Poincaré ).

In the 1990s, after preliminary work by Gerhard Frey and others , Andrew Wiles was able to prove Fermat's conjecture from the 17th century using the theory of elliptic curves .

Affine and projective planes

The two-dimensional space of -rational projective points is defined as ${\displaystyle K}$

${\displaystyle \mathbb {P} ^{2}(K)=\{(X,Y,Z)|X,Y,Z\in K{\text{ nicht alle gleich 0}}\}/\!{\sim }}$

with the equivalence relation

${\displaystyle (X_{1},Y_{1},Z_{1})\sim (X_{2},Y_{2},Z_{2})\Leftrightarrow \exists \lambda \in K^{\ast }:(X_{1},Y_{1},Z_{1})=(\lambda X_{2},\lambda Y_{2},\lambda Z_{2})}$.

Points from are usually noted as to distinguish them from points in three-dimensional affine space . ${\displaystyle \mathbb {P} ^{2}(K)}$ ${\displaystyle (X:Y:Z)}$

The projective plane can be represented as the union of the set ${\displaystyle \mathbb {P} ^{2}(K)}$

${\displaystyle \{(X:Y:1)|X,Y\in K\}}$

with the hyperplane generated by : ${\displaystyle Z=0}$ ${\displaystyle H}$ ${\displaystyle \mathbb {P} ^{2}(K)}$

${\displaystyle H=\{(X:Y:0)|X,Y\in K{\text{ nicht beide gleich 0}}\}}$

In order to represent projective cubes in the affine plane, one then identifies the projective point with the affine point . ${\displaystyle Z\neq 0}$ ${\displaystyle (X:Y:Z)=\left({\frac {X}{Z}}:{\frac {Y}{Z}}:1\right)=(x:y:1)}$ ${\displaystyle (x,y)}$

In the case of an elliptic curve, the (projective) polynomial equation has exactly one solution , namely the point at infinity . ${\displaystyle Z=0}$ ${\displaystyle {\mathcal {O}}=(0:1:0)}$

definition

${\displaystyle E}$is called an elliptic curve over the body if one of the following (pairwise equivalent) conditions is met: ${\displaystyle K}$

• ${\displaystyle E}$is a smooth projective curve across from gender 1 with a point whose coordinates lie in. ${\displaystyle K}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle K}$
• ${\displaystyle E}$is a smooth projective cube over with a point whose coordinates lie in. ${\displaystyle K}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle K}$
• ${\displaystyle E}$ is a smooth, by a Weierstraß equation

${\displaystyle Y^{2}Z+a_{1}XYZ+a_{3}YZ^{2}=X^{3}+a_{2}X^{2}Z+a_{4}XZ^{2}+a_{6}Z^{3}}$

given projective curve with coefficients . You write ${\displaystyle a_{i}\in K}$

${\displaystyle F(X,Y,Z)=Y^{2}Z+a_{1}XYZ+a_{3}YZ^{2}-X^{3}-a_{2}X^{2}Z-a_{4}XZ^{2}-a_{6}Z^{3},}$

so is just the set of zeros of the homogeneous polynomial . (Note: The point definitely satisfies the polynomial equation, so it is on .) ${\displaystyle E}$ ${\displaystyle F\in K[X,Y,Z]}$ ${\displaystyle (0:1:0)={\mathcal {O}}}$ ${\displaystyle E}$

If one considers an affine curve, one obtains an affine Weierstraß equation ${\displaystyle E}$

${\displaystyle y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}}$

or an affine polynomial . In this case, the set of (affine) points that satisfy the equation, together with the so-called “infinitely distant point” , is also written as. ${\displaystyle f(x,y)=y^{2}+a_{1}xy+a_{3}y-x^{3}-a_{2}x^{2}-a_{4}x-a_{6}\in K[x,y]}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \infty }$

Isomorphic elliptic curves

definition

Every elliptical curve is described by a projective polynomial or by an affine polynomial . One calls two elliptic curves and isomorphic, if the Weierstraß equation of from that of by a coordinate change of the form ${\displaystyle F(X,Y,Z)\in K[X,Y,Z]}$ ${\displaystyle f(x,y)\in K[x,y]}$ ${\displaystyle E_{1}}$ ${\displaystyle E_{2}}$ ${\displaystyle E_{2}}$ ${\displaystyle E_{1}}$

${\displaystyle x\mapsto u^{2}x+r}$

${\displaystyle y\mapsto u^{3}y+su^{2}x+t}$

with arises. The most important properties of elliptical curves do not change when such a coordinate change is carried out. ${\displaystyle u,r,s,t\in {\bar {K}},u\neq 0}$

Short Weierstrass equation

Is an elliptical curve over a body with the characteristics of the Weierstraß equation ${\displaystyle K}$ ${\displaystyle \operatorname {char} (K)\not \in \{2,3\}}$

${\displaystyle y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}}$

given, there is a change of coordinates that converts this Weierstraß equation into the equation

${\displaystyle y^{2}=x^{3}+ax+b}$

transformed. This is called a short Weierstrass equation. The elliptical curve defined by this short Weierstrass equation is isomorphic to the original curve. It is therefore often assumed, without restriction, that an elliptical curve is given from the outset by a short Weierstraß equation.

Another result of the theory of the Weierstrass equations is that an equation of form

${\displaystyle y^{2}=x^{3}+ax+b}$

describes a smooth curve if and only if the discriminant of the polynomial , ${\displaystyle \Delta _{E}}$ ${\displaystyle x^{3}+ax+b}$

${\displaystyle \Delta _{E}=-4a^{3}-27b^{2},}$

does not go away. The discriminant is proportional to the product with the roots of the cubic polynomial and does not vanish if the roots are different in pairs. ${\displaystyle {(\lambda _{1}-\lambda _{2})}^{2}\cdot {(\lambda _{1}-\lambda _{3})}^{2}\cdot {(\lambda _{2}-\lambda _{3})}^{2}}$ ${\displaystyle \lambda _{i}}$

Examples

Graph of exemplary curves

• ${\displaystyle E_{1}\colon y^{2}=x^{3}-x+1}$and are elliptic curves over , there and are. ${\displaystyle E_{2}\colon y^{2}=x^{3}+2x-{\sqrt {3}}}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \Delta _{E_{1}}=4-27=-23\neq 0}$ ${\displaystyle \Delta _{E_{2}}=-32-81=-113\neq 0}$
• ${\displaystyle E\colon y^{2}=x^{3}-x}$is an elliptic curve both over and over since is the discriminant . On the other hand, over a body with a characteristic and is singular, i.e. not an elliptic curve. ${\displaystyle \mathbb {Q} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \Delta _{E}=4\neq 0}$ ${\displaystyle 2}$ ${\displaystyle \Delta _{E}=0}$ ${\displaystyle E}$
• ${\displaystyle E\colon y^{2}=x^{3}+1}$there is an elliptic curve above every body with characteristic unequal , there is. ${\displaystyle 3}$ ${\displaystyle \Delta _{E}=-27=-3^{3}\neq 0}$

Via the real numbers, the discriminant gives information about the shape of the curve in the affine plane. For , the graph of the elliptic curve consists of two components (left figure), for, however, only a single component (right figure). ${\displaystyle \Delta _{E}>0}$ ${\displaystyle E}$ ${\displaystyle \Delta _{E}<0}$

Group operation

The special feature of elliptic curves is that they are commutative groups with respect to the pointwise addition described in this section . This addition is illustrated geometrically in the first subsection, before it is further formalized in the following sections.

Geometric interpretation

Geometrically, the addition of two points on an elliptical curve can be described as follows: The point at infinity is the neutral element . The reflection of a rational point on the -axis again yields a rational point on the curve, the inverse of . The straight line through the rational points intersects the curve at a third point; reflection of this point on the -axis yields the rational point . ${\displaystyle \infty }$ ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle -P}$ ${\displaystyle P}$ ${\displaystyle P,Q}$ ${\displaystyle x}$ ${\displaystyle P+Q}$

In the case of a tangent to the point (i.e. the borderline case on the curve), the point is obtained with this construction (intersection of the tangent with the curve, then reflection) . If no corresponding intersection points can be found, the point at infinity is used as an aid, and one has e.g. As in the case of the tangent without a second intersection: . The neutral point is often referred to as. ${\displaystyle P}$ ${\displaystyle Q\to P}$ ${\displaystyle P+P}$ ${\displaystyle P+P=\infty }$ ${\displaystyle {\mathcal {O}}}$

It can be shown that this "addition" is both commutative and associative , so that it actually obeys the laws of an Abelian group. Cayley-Bacharach's theorem can be used to prove the associative law.

Now be a rational point on the elliptic curve. The point is designated with , correspondingly it is defined as the k -fold addition of the point . If this is not the point , any rational point on the curve can be reached in this way (i.e., for every point on the curve there is a natural number with ), if one knows the correct generators of the group. ${\displaystyle P}$ ${\displaystyle P+P}$ ${\displaystyle 2P}$ ${\displaystyle kP=P+\dotsb +P}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle E}$ ${\displaystyle Q}$ ${\displaystyle k}$ ${\displaystyle Q=kP}$ ${\displaystyle P}$

The task of determining this value from given points is referred to as the discrete logarithm problem of elliptic curves ( ECDLP for short ). It is believed that the ECDLP (with proper curve choice) is heavy; H. cannot be resolved efficiently. This means that elliptical curves are ideal for implementing asymmetrical cryptosystems on them (e.g. a Diffie-Hellman key exchange or an Elgamal cryptosystem ). ${\displaystyle P,Q}$ ${\displaystyle k}$

Adding two different points

Addition on the elliptic curve ${\displaystyle y^{2}=x^{3}+1}$

Be and the components of points and . The result of the addition is designated with. So this point has the components . Also set ${\displaystyle P=(x_{P},y_{P})}$ ${\displaystyle Q=(x_{Q},y_{Q})}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle R}$ ${\displaystyle R:=P+Q:=(x_{R},y_{R})}$ ${\displaystyle R}$ ${\displaystyle (x_{R},y_{R})}$

${\displaystyle s:={\frac {y_{P}-y_{Q}}{x_{P}-x_{Q}}}}$.

Then the addition is over ${\displaystyle P+Q=(x_{R},y_{R})}$

• ${\displaystyle x_{R}:=s^{2}-x_{P}-x_{Q}}$ and
• ${\displaystyle y_{R}:=-y_{P}+s(x_{P}-x_{R})}$

Are defined.

The two points and must not have the same coordinate, otherwise it is not possible to calculate the slope , since either or applies. The addition gives you what defines the result as ( neutral element ). This also means that and are inverse to one another with respect to the point addition. If it is, it is a doubling of the point. ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle x}$ ${\displaystyle s}$ ${\displaystyle P=Q}$ ${\displaystyle P=-Q}$ ${\displaystyle P+(-P)}$ ${\displaystyle s={\tfrac {2y_{P}}{0}}}$ ${\displaystyle \infty }$ ${\displaystyle P}$ ${\displaystyle -P}$ ${\displaystyle P=Q}$

Doubling a point

There are two cases for doubling a point (adding a point to itself) . ${\displaystyle P=(x_{P},y_{P})}$

Case 1: ${\displaystyle y_{P}\neq 0}$

• ${\displaystyle P+P=R=(x_{R},y_{R})}$
• ${\displaystyle s=(3x_{P}^{2}+a)/(2y_{P})}$. In this case, from the curve equation ( used). ${\displaystyle a}$ ${\displaystyle y^{2}=x^{3}+ax+b}$
• ${\displaystyle x_{R}=s^{2}-2x_{P}}$
• ${\displaystyle y_{R}=-y_{P}+s(x_{P}-x_{R})}$

The only difference to adding two different points is in the calculation of the slope .

Case 2: ${\displaystyle y_{P}=0}$

• ${\displaystyle P+P=\infty }$

Because of is clearly recognizable that is inverse to itself . ${\displaystyle y_{P}=0\Rightarrow P=(-P)}$ ${\displaystyle P}$

Calculation rules for the "addition" of points on the curve

Analytical description about the coordinates:

Be

• ${\displaystyle P,Q}$ two different points,
• ${\displaystyle P=(x_{P},y_{P}),}$
• ${\displaystyle Q=(x_{Q},y_{Q}),}$
• ${\displaystyle x_{P}\neq x_{Q},}$
• ${\displaystyle +}$ the addition of two points and
• ${\displaystyle \infty }$the neutral element (also called the infinity point).

The following rules apply:

• ${\displaystyle P+Q=Q+P}$
• ${\displaystyle P+(-P)=\infty }$
• ${\displaystyle P+\infty =P}$
• ${\displaystyle -P=(x_{P},-y_{P})}$
• ${\displaystyle (P+Q)+R=P+(Q+R)}$

Scalar multiplication of a point

The scalar multiplication is just the repeated addition of this point. ${\displaystyle n\cdot P}$

• ${\displaystyle n\cdot P=P+\dotsb +P}$

This multiplication can be efficiently solved with the help of an adapted square & multiply method .

In the case of an elliptical curve over the finite body , the point addition overflows computationally in the same way as in the calculation , but the coordinates are over- calculated. ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathrm {GF} (q)}$

Elliptic curves over the complex numbers

If, as usual, the complex numbers are interpreted as elements of the Gaussian plane of numbers , then elliptic curves over the complex numbers represent a two-dimensional surface that is embedded in the four-dimensional . Although such surfaces cannot be seen, statements can still be made about their shape, such as the gender of the surface, in this case (torus) of gender 1. ${\displaystyle \mathbb {C} ^{2}}$

Complex tori

Let it be a (complete) grid in the complex number plane . The factor group is a one-dimensional abelian compact complex Lie group which, as a real Lie group, is isomorphic to the torus . For an illustration one can choose producers from ; the quotient then results from the basic mesh ${\displaystyle \Gamma }$ ${\displaystyle \mathbb {C} }$ ${\displaystyle \mathbb {C} /\Gamma }$ ${\displaystyle S^{1}\times S^{1}}$ ${\displaystyle v,w}$ ${\displaystyle \Gamma }$ ${\displaystyle \mathbb {C} /\Gamma }$

${\displaystyle \{\lambda v+\mu w\mid 0\leq \lambda ,\ \mu \leq 1\}}$,

by gluing opposite sides.

Relation to flat cubes

An elliptic curve is defined in the complex plane by an elliptic function using its values ​​in a grid that is spanned by the complex periods and . The 4 torsion points that correspond to a grid are also drawn in ${\displaystyle \Gamma }$ ${\displaystyle \omega _{1}}$ ${\displaystyle \omega _{2}}$ ${\displaystyle 1/4\ \Gamma }$

If a grid is in the complex plane of numbers, the associated Weierstrasse stra-function and its derivative define an embedding ${\displaystyle \Gamma }$

${\displaystyle \mathbb {C} /\Gamma \to \mathbb {P} ^{2}(\mathbb {C} ),\quad z\mapsto (1:\wp (z):\wp '(z))}$,

whose image is the non-singular cubic

${\displaystyle y^{2}=4x^{3}-g_{2}(\Gamma )x-g_{3}(\Gamma )}$

is. Any nonsingular plane cube is isomorphic to a cube that is created this way.

This can be illustrated by the illustration on the right. The elliptic function, through its Weierstrass shape in a grid defined on the complex plane, since the function is doubly periodic (periods , , both complex numbers, for a real ). The edges of the grid are identified, which geometrically results in a torus. The above figure shows the lattice in the complex projective plane and the addition of points in the quotient space (torus) is transferred as a group homomorphism to the elliptic curve in the projective plane, which results in the "law of addition" of points on the curve explained above . ${\displaystyle \Gamma }$ ${\displaystyle \omega _{1}}$ ${\displaystyle \omega _{2}}$ ${\displaystyle r\cdot \omega _{1}\neq \omega _{2}}$ ${\displaystyle r}$ ${\displaystyle \mathbb {C} /\Gamma }$

Points of finite order in the lattice are called torsion points . A torsion point -th order corresponds to the points ${\displaystyle n}$

${\displaystyle {\frac {k}{n}}\omega _{1}+{\frac {l}{n}}\omega _{2}}$

with . The illustration shows the case . With regard to the law of addition defined above for points on elliptic curves, a torsion point applies . ${\displaystyle k,l=0,\dotsc ,n-1}$ ${\displaystyle n=4}$ ${\displaystyle n}$ ${\displaystyle P}$ ${\displaystyle n\cdot P=\infty }$

classification

Two one-dimensional complex tori and for lattices are isomorphic (as complex Lie groups) if and only if the two lattices are similar , i.e. H. emerge apart by a twisting stretch. Each grid is similar to a grid of shape , one element being the upper half-plane ; are producers, you can choose as or . The various options for producers correspond to the operation of the group on the upper half-plane that is carried out by ${\displaystyle \mathbb {C} /\Gamma _{1}}$ ${\displaystyle \mathbb {C} /\Gamma _{2}}$ ${\displaystyle \Gamma _{1},\Gamma _{2}}$ ${\displaystyle \langle 1,\tau \rangle _{\mathbb {Z} }}$ ${\displaystyle \tau }$ ${\displaystyle \mathbb {H} =\{z\in \mathbb {C} \mid \operatorname {Im} z>0\}}$ ${\displaystyle v,w}$ ${\displaystyle \tau }$ ${\displaystyle v/w}$ ${\displaystyle w/v}$ ${\displaystyle \mathrm {SL} _{2}(\mathbb {Z} )}$

${\displaystyle {\begin{pmatrix}a&b\\c&d\end{pmatrix}}\tau ={\frac {a\tau +b}{c\tau +d}}}$

is given ( module group ). Two elements define the upper half plane if and isomorphic elliptic curves and when and in the same lie Bahn; the set of isomorphism classes of elliptic curves thus corresponds to the orbital space ${\displaystyle \tau _{1},\tau _{2}}$ ${\displaystyle \mathbb {C} /\langle 1,\tau _{1}\rangle }$ ${\displaystyle \mathbb {C} /\langle 1,\tau _{2}\rangle }$ ${\displaystyle \tau _{1}}$ ${\displaystyle \tau _{2}}$ ${\displaystyle \mathrm {SL} _{2}(\mathbb {Z} )}$

${\displaystyle \mathrm {SL} _{2}(\mathbb {Z} )\backslash \mathbb {H} ;}$

this space is mapped bijectively by the function , a module function ; where the value of the function is equal to the invariants of the cubic given above. ${\displaystyle j}$ ${\displaystyle \mathbb {C} }$ ${\displaystyle j}$ ${\displaystyle j}$

Elliptic curves over the rational numbers

The addition of points of elliptical curves makes it possible to calculate further solutions from simple (guessed) solutions of a cubic equation, which usually have far larger numerators and denominators than the initial solutions (and therefore could hardly be found by systematic trial and error).

For example for the elliptic curve defined above ${\displaystyle \mathbb {Q} }$

${\displaystyle y^{2}=x^{3}-63}$

one finds the solution by guessing and from this the solution by adding on the elliptic curve and then by adding on the elliptic curve still considerably "larger" solutions. That follows from ${\displaystyle P=(x,y)=(4,1)}$ ${\displaystyle 2P=(568,-13537)}$

${\displaystyle h(2P)=4h(P)+O(1)}$

for points with integer coordinates on elliptic curves using the coordinate form of the law of addition (see above). The height defined for integer points by . ${\displaystyle \mathbb {Q} }$ ${\displaystyle h}$ ${\displaystyle h(x,y)=\log(\mid x\mid )}$

According to Mordell-Weil's theorem , finite is generated and it is true , where are the torsion subsets and denote the rank of the elliptic curve. According to the theorem of Lutz and Nagell ( Élisabeth Lutz , Trygve Nagell , mid-1930s) it holds for the points of finite order (i.e. the elements of the torsion subgroups) that and either (then is of order 2) or , that is, divides (where is the discriminant). This enables the torsion subgroups to be calculated. ${\displaystyle E(\mathbb {Q} )}$ ${\displaystyle E(\mathbb {Q} )=T\times \mathbb {Z} ^{r}}$ ${\displaystyle T}$ ${\displaystyle r}$ ${\displaystyle P=(x,y)}$ ${\displaystyle x,y\in \mathbb {Z} }$ ${\displaystyle y=0}$ ${\displaystyle P}$ ${\displaystyle y^{2}\mid D}$ ${\displaystyle y^{2}}$ ${\displaystyle D}$ ${\displaystyle D}$

The possible torsion subsets for elliptic curves over the rational numbers were classified by Barry Mazur in a difficult proof ( Mazur's Theorem (Elliptic Curves) ). After that, the number can assume one of the values ​​1 to 10 or 12 at a point in the order . ${\displaystyle N}$ ${\displaystyle N}$

With the theorem of Lutz and Nagell and that of Mazur one has an algorithm for determining the elements of the torsion groups of an elliptic curve over the rational numbers: ${\displaystyle P=(x,y)}$ ${\displaystyle y^{2}=f(x)}$

• Find the curve with the discriminant . ${\displaystyle y^{2}\mid D}$ ${\displaystyle D}$
• Determine the associated ones from the equation of the curve and thus have the coordinates of . ${\displaystyle x}$ ${\displaystyle P}$
• If you calculate with (according to Mazur's theorem), is (where the notation for the neutral element is used here), you have a torsion point. If, on the other hand, it has no integer coordinates, it does not belong to the torsion points. ${\displaystyle nP}$ ${\displaystyle n=1,\dotsc ,10,12}$ ${\displaystyle nP={\mathcal {O}}}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle nP}$

According to Mordell's conjecture (Faltings' theorem, they correspond to the case of gender ), elliptic curves have a special position; they can have an infinite number (rank not equal to zero) or a finite number of rational solutions (torsion subgroups). On the other hand, curves with only have a finite number of solutions. In the case there are no or an infinite number of solutions (for example, in the case of a circle, an infinite number of Pythagorean triples ). ${\displaystyle g=1}$ ${\displaystyle g>1}$ ${\displaystyle g=0}$

The theory of elliptic curves over the field of rational numbers is an active research area of ​​number theory (arithmetic algebraic geometry) with some famous open conjectures such as the Birch and Swinnerton-Dyer conjecture , which is a proposition about the analytic behavior of the Hasse-Weil-L- Makes a function of an elliptical curve, in the definition of which the number of points of the curve over finite bodies is included. According to the conjecture in its simplest form, the rank of the elliptic curve is equal to the order of the zero of at . ${\displaystyle L(E,s)}$ ${\displaystyle L(E,s)}$ ${\displaystyle s=1}$

Elliptic curves over finite bodies

Affine points of the elliptic curve over ${\displaystyle y^{2}=x^{3}-x}$ ${\displaystyle \mathbf {F} _{61}}$

Instead of using the rational numbers, one can also consider elliptic curves over finite fields . In this case the plane, more precisely the projective plane in which the elliptic curve lies, consists only of a finite number of points. Therefore the elliptic curve itself can only contain a finite number of elements, which can simplify many considerations. For the number of points on an elliptical curve over a body with elements, Helmut Hasse (1936) gave the estimate (Riemann hypothesis) ${\displaystyle N}$ ${\displaystyle E}$ ${\displaystyle q}$

${\displaystyle |N-(q+1)|\leq 2{\sqrt {q}}}$

and thus proved a conjecture from Emil Artin's dissertation (1924).

More generally, it follows from the Weil conjectures (a series of conjectures on the Hasse-Weil zeta function, proven in the 1960s and 1970s) for the number of points above a body extension with elements, the equation ${\displaystyle N_{m}}$ ${\displaystyle E}$ ${\displaystyle q^{m}}$

${\displaystyle N_{m}=q^{m}+1-\alpha ^{m}-\beta ^{m}}$,

where and the two zeros of the characteristic polynomial of the Frobenius homomorphism on the elliptic curve are above . René Schoof (1985) developed the first efficient algorithm for calculating . Improvements by A. O. L. Atkin (1992) and Noam Elkies (1990) followed. ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \phi _{q}}$ ${\displaystyle \mathbf {F} _{q^{m}}}$ ${\displaystyle N_{m}}$

Elliptic curves over finite fields are z. B. used in cryptography ( elliptical curve cryptosystem ).

The (as yet unproven) conjecture by Birch and Swinnerton-Dyer tries to obtain statements about certain properties of elliptic curves over the rational numbers by examining corresponding properties of elliptic curves over finite bodies (so-called "reduced elliptic curves").

Hasse-Weil zeta function and L function for elliptic curves

The elliptic curve over suppose to be given by the equation ${\displaystyle E}$ ${\displaystyle \mathbb {Q} }$

${\displaystyle y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}}$

given with integer coefficients . The reduction of the coefficients modulo a prime number defining an elliptic curve over the finite field (except for a finite set of prime numbers , for which the reduced curve singularities and being therefore not elliptical, in which case one says, have poor reduction in ). ${\displaystyle a_{i}}$ ${\displaystyle p}$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle p}$ ${\displaystyle E}$ ${\displaystyle p}$

The zeta function of an elliptic curve over a finite field is the formal power series

${\displaystyle Z(E(\mathbb {F} _{p}))=\exp \left(\sum \mathrm {card} \left[E({\mathbb {F} }_{p^{n}})\right]{\frac {T^{n}}{n}}\right).}$

It is a rational function of form

${\displaystyle Z(E(\mathbb {F} _{p}))={\frac {1-a_{p}T+pT^{2}}{(1-T)(1-pT)}}.}$

(This equation defines the coefficient if there is good reduction at , the definition in the case of bad reduction is different.) ${\displaystyle a_{p}}$ ${\displaystyle E}$ ${\displaystyle p}$

The function of over stores this information for all prime numbers . It is defined by ${\displaystyle L}$ ${\displaystyle E}$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle p}$

${\displaystyle L(E(\mathbb {Q} ),s)=\prod _{p}\left(1-a_{p}p^{-s}+\varepsilon (p)p^{1-2s}\right)^{-1}}$

with , if good reduction has, and otherwise. ${\displaystyle \varepsilon (p)=1}$ ${\displaystyle E}$ ${\displaystyle p}$ ${\displaystyle \varepsilon (p)=0}$

The product converges for . Hasse hypothesized that the function has an analytical continuation to the entire complex level and satisfies a functional equation with a relationship between and . Hasse's conjecture was proven in 1999 as a consequence of proving the modularity theorem. This states that every elliptic curve is above a modular curve , and the analytical continuability of the functions of modular curves is known. ${\displaystyle \textstyle \Re (s)\;>\;{\frac {3}{2}}}$ ${\displaystyle L}$ ${\displaystyle L(E,s)}$ ${\displaystyle L(E,2-s)}$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle L}$

Application in cryptography

→ Main article : Elliptic Curve Cryptography

In January 2009, the US foreign secret service NSA recommended switching encryption on the Internet from RSA to ECC (Elliptic Curve Cryptography) by 2020 .

ECC is a public key cryptosystem (or asymmetric cryptosystem) in which, in contrast to a symmetric cryptosystem, the communicating parties do not need to know a shared secret key. Asymmetric cryptosystems in general work with trapdoor functions , ie functions that are easy to calculate, but are practically impossible to invert without a secret (the “trapdoor”).

The principle of encryption using elliptic curves works by assigning the elements of the message to be encrypted (i.e. the individual bits) to the points of a (fixed) elliptic curve in some way and then applying the encryption function with a (fixed) natural number . For this method to be secure, the decryption function must be difficult to calculate. ${\displaystyle P\mapsto nP}$ ${\displaystyle n>1}$ ${\displaystyle (nP,P)\mapsto n}$

Since the problem of the discrete logarithm in elliptic curves (ECDLP) is significantly more difficult than the computation of the discrete logarithm in finite fields or the factorization of whole numbers, cryptosystems based on elliptic curves get by with considerably shorter keys than these - with comparable security conventional asymmetric cryptographic methods, such as B. the RSA cryptosystem . The fastest algorithms currently available are the Babystep-Giantstep-Algorithm and the Pollard-Rho-Method , the running time of which is, where the bit length is the size of the underlying body. ${\displaystyle O\left(2^{n/2}\right)}$ ${\displaystyle n}$

literature

• Annette Werner : Elliptic Curves in Cryptography. Springer , 2002, ISBN 978-3-540-42518-2 .
• Peter Meier, Jörn Steuding and Rasa Steuding: Elliptical curves and a bold guess. In: Spectrum of Science . Dossier: “The greatest puzzles in mathematics” (6/2009), ISBN 978-3-941205-34-5 , pages 40–47.
• Joseph H. Silverman: The Arithmetic of Elliptic Curves . Springer, 2009, ISBN 978-0-387-09493-9 .

Web links

Commons : Elliptic curves  - collection of images, videos and audio files

• Simple introduction to elliptic curves (in connection with ECC)
• Comprehensive introduction to elliptic curves and ECC as a Sage notebook. ( Memento from June 21, 2010 in the Internet Archive )
• Software to visualize elliptical curves and their group structure. ( Memento from March 14, 2010 in the Internet Archive )
• F. Lemmermeyer: Elliptic Curves 1. (PDF; 1.1 MB).
• A. Huber-Klawitter: What we (don't) know for equations of degree three - elliptic curves and the conjecture of Birch and Swinnerton-Dyer.

Footnotes

1. ↑ Elliptic curve . In: Guido Walz (Ed.): Lexicon of Mathematics . 1st edition. Spectrum Academic Publishing House, Mannheim / Heidelberg 2000, ISBN 3-8274-0439-8 .
2. ^ Zachary DeStefano: On the torsion subgroup of an elliptic curve. Lecture, New York University 2010, PDF.
3. ↑ Helmut Hasse: On the theory of abstract elliptical function bodies. I, II & III . In: Journal for pure and applied mathematics . tape 1936 , no. 175 , 1936, doi : 10.1515 / crll.1936.175.193 .
4. ^ Emil Artin: Square bodies in the area of ​​higher congruences. II. Analytical part . In: Mathematical Journal . tape 19 , no. 1 , 1924, p. 207-246 , doi : 10.1007 / BF01181075 .
5. ↑ Chapter V, Theorem 2.3.1 in Joseph H. Silverman: The Arithmetic of Elliptic Curves . 2nd Edition. Springer, 2009, ISBN 978-0-387-09493-9 .
6. ^ The Case for Elliptic Curve Cryptography. In: nsa.gov . January 15, 2009, archived from the original on January 19, 2009 ; accessed on April 28, 2016 .