ECCHacks

Edwards addition

[Python snippets]

The Edwards addition law explains how to add points on the Edwards curve x²+y²=1+dx²y².

The following Python function, edwardsadd, returns the sum of two clock points P1 and P2:

     def edwardsadd(P1,P2):
       x1,y1 = P1
       x2,y2 = P2
       x3 = (x1*y2+y1*x2)/(one+d*x1*y1*x2*y2)
       y3 = (y1*y2-x1*x2)/(one-d*x1*y1*x2*y2)
       return x3,y3
     
     # example:
     one = 1
     d = -300
     P1 = (0.8,-0.043188945044921672046)
     P2 = (-0.4,0.130930734141595428759)
     
     print edwardsadd(P1,P2)
     # output: (0.26691902067523626, 0.20374230558087345)
     print edwardsadd(P2,P1)
     # output: (0.26691902067523626, 0.20374230558087345)

As before, these functions aren't perfectly accurate for real numbers, because Python isn't performing exact computations on real numbers.

The formulas also work for finite fields, and this time are perfectly accurate:

# example:
     F1009 = F(1009)
     d = F1009(-11)
     one = F1009(1)
     
     P1 = (F1009(7),F1009(415))
     P2 = (F1009(23),F1009(487))
     
     print edwardsadd(P1,P2)
     # output: (944, 175)
     print edwardsadd(P2,P1)
     # output: (944, 175)