-
Notifications
You must be signed in to change notification settings - Fork 0
/
elliptic.py
152 lines (112 loc) · 3.98 KB
/
elliptic.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
# An elliptic curve with generalized Weierstrass normal form
class GeneralizedEllipticCurve(object):
def __init__(self, a1=0, a2=0, a3=0, a4=0, a6=0):
#Coefficients are for y^2 + a1xy + a3y = x^3 + a2x^2 + a4x + a6
self.a1 = a1
self.a2 = a2
self.a3 = a3
self.a4 = a4
self.a6 = a6
b2 = self.a1**2 + 4*self.a2
b4 = 2*self.a4 + self.a1*self.a3
b6 = self.a3**2 + 4*self.a6
b8 = (self.a1**2)*self.a6 + 4*self.a2*self.a6 - self.a1*self.a3*self.a4 + self.a2*(self.a3**2) - self.a4**2
c4 = b2*b2 - 24*b4
c6 = -b2*b2*b2 + 36*b2*b4 - 216*b6
self.disc = -b2*b2*b8 - 8*b4*b4*b4 - 27*b6*b6 + 9*b2*b4*b6
self.j = c4*c4*c4/self.disc
def testPoint(self, x, y):
return y*y + self.a1*x*y + self.a3*y - x*x*x - self.a2*(x*x) - self.a4*x - self.a6 == 0
class Point(object):
def __init__ (self, curve, x, y):
self.curve = curve # the curve containing this point
self.x = x
self.y = y
def __str__(self):
return "(%r, %r)" % (self.x, self.y)
def __repr__(self):
return str(self)
def __neg__(self):
return Point(self.curve, self.x, -self.y - self.curve.a1*self.x - self.curve.a3)
def __add__(self, Q):
if isinstance(Q, Ideal):
return Point(self.curve, self.x, self.y)
a1,a2,a3,a4,a6 = (self.curve.a1, self.curve.a2, self.curve.a3, self.curve.a4, self.curve.a6)
if self.x == Q.x:
x = self.x
if self.y + Q.y + a1*x + a3 == 0:
return Ideal(self.curve)
else:
c = ((3*x*x + 2*a2*x + a4 - a1*self.y) / (2*self.y + a1*x + a3))
d = (-(x*x*x) + a4*x + 2*a6 - a3*self.y) / (2*self.y + a1*x + a3)
Sum_x = c*c + a1*c - a2 - 2*self.x
Sum_y = -(c + a1) * Sum_x - d - a3
return Point(self.curve, Sum_x, Sum_y)
else:
c = (Q.y - self.y) / (Q.x - self.x)
d = (self.y*Q.x - Q.y*self.x) / (Q.x - self.x)
Sum_x = c*c + a1*c - a2 - self.x - Q.x
Sum_y = -(c + a1)*Sum_x - d - a3
return Point(self.curve, Sum_x, Sum_y)
def __sub__(self, Q):
return self + -Q
def __mul__(self, n):
if not isinstance(n, int) and not isinstance(n, long):
raise Exception("Can't scale a point by something which isn't an int!")
else:
if n < 0:
return -self * -n
if n == 0:
return Ideal(self.curve)
else:
Q = self
R = self if n & 1 == 1 else Ideal(self.curve)
i = 2
while i <= n:
Q = Q + Q
if n & i == i:
R = Q + R
i = i << 1
return R
def __rmul__(self, n):
return self * n
def __list__(self):
return [self.x, self.y]
def __eq__(self, other):
if isinstance(other, Ideal):
return False
return list(self) == list(other)
def __ne__(self, other):
return not self == other
def __getitem__(self, index):
return [self.x, self.y][index]
# lexicographic ordering on points
def __lt__(self, other):
if isinstance(other, Ideal): return False
return list(self) < list(other)
def __gt__(self, other):
return other.__lt__(self)
def __ge__(self, other):
return not self < other
def __le__(self, other):
return not other < self
class Ideal(Point):
def __init__(self, curve):
self.curve = curve
def __neg__(self):
return self
def __repr__(self):
return "Ideal"
def __add__(self, Q):
if self.curve != Q.curve:
raise Exception("Can't add points on different curves!")
return Q
def __mul__(self, n):
if not isinstance(n, int):
raise Exception("Can't scale a point by something which isn't an int!")
else:
return self
def __eq__(self, other):
return isinstance(other, Ideal)
def __lt__(self, other):
return not isinstance(other, Ideal)