Edwards curve
In mathematics, the Edwards curves are a family of elliptic curves studied by Harold Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography. Applications of Edwards curves to cryptography were developed by Daniel J. Bernstein and Tanja Lange: they pointed out several advantages of the Edwards form in comparison to the more well known Weierstrass form. Definition. The equation of an Edwards curve over a field "K" which does not have characteristic 2 is: for some scalar formula_2. Also the following form with parameters "c" and "d" is called  an Edwards curve: where "c", "d" ∈ "K" with "cd"(1 − "c"·"d") ≠ 0. Every Edwards curve is birationally equivalent to an elliptic curve in Weierstrass form, and thus admits an algebraic group law once one chooses a point to serve as a neutral element. If "K" is finite, then a sizeable fraction of all elliptic curves over "K" can be written as Edwards curves. Often elliptic curves in Edwards form are defined having c=1, without loss of generality. In the following sections, it is assumed that c=1. The group law. Every Edwards curve formula_4 over field "K" with characteristic  not equal to 2 with formula_5 is birationally equivalent to an elliptic curve over the same field: formula_6, where formula_7 and the point formula_8 is mapped to the infinity "O". This birational mapping induces a group on any Edwards curve. Edwards addition law. On any elliptic curve the sum of two points is given by a rational expression of the coordinates of the points, although in general one may need to use several formulas to cover all possible pairs. For the Edwards curve, taking the neutral element to be the point (0, 1), the sum of the points formula_9 and  formula_10 is given by the formula The opposite of any point formula_12 is formula_13. The point formula_14 has order 2, and the points formula_15 have order 4. In particular, an Edwards curve always has a point of order 4 with coordinates in "K". If "d is not a square" in "K" and formula_16, then there are no exceptional points: the denominators formula_17 and formula_18 are always nonzero. Therefore, the Edwards addition law is complete when "d" is not a square in "K". This means that the formulas work for all pairs of input points on the Edwards curve with no  exceptions for doubling, no exception for the neutral element, no exception for negatives, etc. In other words, it is defined for all pairs of input points on the Edwards curve over "K" and the result gives the sum of the input points. If "d is a square" in "K", then the same operation can have exceptional points, i.e. there can be pairs of points formula_19 such that one of the denominators becomes zero: either formula_20 or formula_21. One of the attractive feature of the Edwards Addition law is that it is strongly "unified" i.e. it can also be used to  double a point, simplifying protection against side-channel attack. The addition formula above is faster than other unified formulas and has the strong property of completeness Example of addition law : Consider the elliptic curve in the Edwards form with "d"=2 and the point formula_23 on it. It is possible to prove that the sum of "P" with the neutral element (0,1) gives again P. Indeed, using the formula given above, the coordinates of the point given by this sum are: An analogue on the circle. To understand better the concept of "addition" of points on a curve, a nice example  is given by the classical circle group: take the circle of radius 1 and consider two points P=(x,y), P=(x,y) on it. Let α and α be the angles such that: The sum of P and P is, thus, given by the sum of "their angles". That is, the point P=P+P is a point on the circle with coordinates (x,y), where: In this way, the addition formula for points on the circle of radius 1 is: Addition on Edwards curves. The points on an elliptic curve form an abelian group: one can add points and take  integer multiples of a single point. When an elliptic curve is described by a non-singular cubic equation, then the sum of two points "P" and "Q", denoted "P" + "Q", is directly related to third point of intersection between the curve and the line that passes through "P" and "Q". The birational mapping between an Edwards curve and the corresponding cubic elliptic curve maps the straight lines into conic sections formula_32. In other words, for the Edwards curves the three points formula_33, formula_34 and formula_35 lay on a hyperbola. Given two distinct non-identity points formula_36, the coefficients of  the quadratic form are (up to scalars): formula_37, formula_38, formula_39 In the case of doubling a point formula_40 the inverse point formula_41 lays on the conic that touches the curve at the point formula_33. The coefficients of the quadratic form that defines the conic are (up to scalars): formula_43, formula_44, formula_45 Projective homogeneous coordinates. In the context of cryptography, homogeneous coordinates are used to prevent field inversions that appear in the affine formula. To avoid inversions in the original Edwards addition formulas, the curve equation can be written in projective coordinates as: formula_46. A projective point formula_47 corresponds to the  affine point formula_48 on the Edwards curve. The identity element is represented by formula_49. The inverse of formula_47 is formula_51. The addition formula in homogeneous coordinates is given by: formula_52 where formula_53 formula_54 formula_55 Algorithm. Addition of two points on the Edwards curve could be computed more efficiently in the extended Edwards form formula_56, where formula_57: formula_58 formula_59 formula_60 formula_61 Doubling. "Doubling" can be performed with exactly the same formula as addition. Doubling refers to the case in which the inputs ("x", "y") and ("x", "y") are equal. Doubling a point formula_40: formula_63 The denominators were simplified based on the  curve equation formula_4. Further speedup is achieved by computing formula_65 as formula_66. This reduces the cost of doubling in homomorphic coordinates to 3M + 4S + 3C + 6a, while general addition costs 10M + 1S + 1C + 1D + 7a. Here M is field multiplications, S is field squarings, D is the cost of multiplying by the curve parameter "d", and a is field addition. As in the previous example for the addition law, consider the Edwards curve with d=2: formula_67 and the point formula_68. The coordinates of the point formula_69 are: formula_70 formula_71 The point  obtained from doubling "P" is thus formula_72. Mixed addition. Mixed addition is the case when Z is known to be 1. In such a case A=ZZ can be eliminated and the total cost reduces to 9M+1S+1C+1D+7a Algorithm. A= ZZ // in other words, A= Z B= Z C=X.X D=YY E=dCD F=B-E G=B+E X= AF((X+Y)(X+Y)-C-D) Y= AG(D-C) Z=CFG Tripling. "Tripling" can be done by first doubling the point and then adding the result to itself. By applying the curve equation as in doubling, we obtain  There are two sets of formulas for this operation in standard Edwards coordinates. The first one costs 9M + 4S while the second needs 7M + 7S. If the S/M ratio is very small, specifically below 2/3, then the second set is better while for larger ratios the first one is to be preferred. Using the addition and doubling formulas (as mentioned above) the point ("X" : "Y" : "Z") is symbolically computed as 3("X" : "Y" : "Z") and compared with ("X" : "Y" : "Z") Giving the Edwards curve with d=2, and the point P=(1,0), the point 3P has coordinates: formula_74  formula_75 So, 3P=(-1,0)=P-. This result can also be found considering the doubling example: 2P=(0,1), so 3P = 2P + P = (0,-1) + P = -P. A=X B=Y C=(2Z) D=A+B E=D F=2D.(A-B) G=E-B.C H=E-A.C I=F+H J=F-G X=G.J.X1 Y=H.I.Y1 Z=I.J.Z1 This formula costs 9M + 4S Inverted Edwards coordinates. Bernstein and Lange introduced an even faster coordinate system for elliptic curves called the "Inverted Edward coordinates" in which the coordinates ("X" : "Y" : "Z") satisfy the  curve ("X" + "Y")"Z" = ("dZ" + "X""Y") and corresponds to the affine point ("Z"/"X", "Z"/"Y") on the Edwards curve "x" + "y" = 1 + "dx""y" with XYZ ≠ 0. Inverted Edwards coordinates, unlike standard Edwards coordinates, do not have complete addition formulas: some points, such as the neutral element, must be handled separately. But the addition formulas still have the advantage of strong unification: they can be used without change to double a point. For more information about operations with these coordinates see http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html Extended Coordinates for Edward Curves. There is another coordinates system with which an Edwards  curve can be represented; these new coordinates are called extended coordinates and are even faster than inverted coordinates. For more information about the time-cost required in the operations with these coordinates see: http://hyperelliptic.org/EFD/g1p/auto-edwards.html For more information about the running-time required in a specific case, see Table of costs of operations in elliptic curves.