Skip to content

Instantly share code, notes, and snippets.

@PJensen

PJensen/ECurve.py

Created July 13, 2009 15:52
Show Gist options
  • Save PJensen/146209 to your computer and use it in GitHub Desktop.
Save PJensen/146209 to your computer and use it in GitHub Desktop.
Download ZIP
Elliptic Curves
Raw
ECurve.py
# Authors: Pete Jensen, Natasha Mandryk (math)
class ECurve:
def __init__(self, p, a, b):
# Define basic variables, coefficients and prime p.
# (y^2 mod p) = (x^3 + ax + b) mod p
self.__a = a # The coefficient: a
self.__b = b # The coefficient: b
self.__p = p # The prime p.
self.__INIFINITY = Point(None, None)
self.points = [] # Create an array that will contain all Points
# on this Curve.
self.__findPoints() # Find all points on this curve.
return
##
# __findPoints
#
# The purpose of this method is to determine from (0,0) to (p - 1, p - 1)
# Currently this is simply a trivial brute force algorithm to find all of
# the points on the curve.
#
# Since as mentioned above, we're checking all points from
# (0, 0) to (p-1, p-1) the running time of this algorithm is (p - 1) ^ 2
# Therefore the algorithm is of O(n^2)
#
def __findPoints(self):
# Here lies a VERY hacky O(n^2) algorithm to find all points on
# the given p, a, b : e-curve.
for x in range(0, self.__p):
for y in range(0, self.__p):
if self.onCurve(x, y) == True:
self.points.append( Point(x,y) )
##
# __str__
#
# Returns a basic string representation of the Curve.
# (e.g) Given, a = 1, b = 1, p = 23; this function returns the string
# "E_23(1, 1)"
#
# @param
# self - THIS curve.
#
# @returns
# The string representation of this curve.
def __str__(self):
return "E_" + str(self.__p) + \
"(" + str(self.__a) + ", " + str(self.__b) + ")"
def __repr__(self):
return str(self)
def inverseSlope(self, n):
for a in range(0, self.__p):
if ( (n * a) % self.__p == 1):
return a
##
# onCurve
#
# This method determines weather or not a given (x, y) point IS or
# is NOT on THIS curve.
#
# @param
# x - The x-coordinate
# y - The y-coordinate
#
# @return
# A boolean True, yes (x, y) IS on the curve.
# A boolean False, no (x, y) is NOT on the curve.
def onCurve(self, x, y):
return ((y ** 2) % self.__p) ==\
((((x ** 3) + self.__a * x + self.__b) % self.__p) )
def __specialSlope(self, point):
return ((3.0 * point.getX() ** 2) + self.__a) * self.inverseSlope(2 * point.getY())
def addPoints(self, pointP, pointQ):
# Set up an initial value for lamda
lamda = 0
#
# Take care of the identity: The case where either or both points are
# at INFINITY. We handle it here, and return. PERIOD.
#
# P + Point(None, None) => P
# Q + Point(None, None) => Q
#
# NOTE: Point(None, None) = self.__INIFINITY
# lets, call self.__INIFINITY, "INFINITY" for the rest of this note.
#
# Lastly: INFINITY + INFINITY => INFINITY
if (pointP == self.__INIFINITY and pointQ == self.__INIFINITY):
return self.__INIFINITY
elif (pointP == self.__INIFINITY):
if (self.onCurve(pointQ.getX(), pointQ.getY())):
return pointQ
elif (pointQ == self.__INIFINITY):
if (self.onCurve(pointP.getX(), pointP.getY())):
return pointP
## We know now, that neither point is @ INFINITY.
# Make sure point P is on the curve.
if (self.onCurve(pointP.getX(), pointP.getY()) == False):
raise "Point: " + str(pointP)+ "not on curve."
# Make sure point Q is on the curve.
elif (self.onCurve(pointQ.getX(), pointQ.getY()) == False):
raise "Point: " + str(pointQ)+ "not on curve."
## We know here, that both points are indeed ON the curve.
# The next case is when x-coordinates are
# equal & y-coordinates unequal. We return a point @ INFINITY.
#
# x1 == x2 AND y1 <> y2 ==> INFINITY
if (pointP.getX() == pointQ.getX() and \
pointP.getY() <> pointQ.getY()):
return self.__INIFINITY
# (x1, y1) <> (x2, y2)
if (pointP != pointQ):
# Compute the rise & the run. Numerator & Denominator respectively.
rise = (pointQ.getY() ) - pointP.getY()
run = (pointQ.getX() ) - pointP.getX()
# Set the lamda for P <> Q
lamda = (self.inverseSlope( run ) * rise)
else:
# Set the lamda for P == Q
lamda = (3 * pointP.getX() ** 2 + self.__a) * self.inverseSlope(2 * pointP.getY())
x3 = (lamda ** 2.0 - pointP.getX() - pointQ.getX()) % (self.__p)
y3 = ((lamda * (pointP.getX() - x3) - pointP.getY() ) % self.__p )
# Return the computed point.
return Point(x3, y3)
Raw
Point.py
class Point:
def __init__(self, x, y):
# Initialize x-coord, y-coord.
self.__x = x
self.__y = y
return
def getSlope(self, pointB):
# Make sure the slope isn't undefined.
if (self.__x == pointB.getX()):
raise "Infinite Slope."
# y2 - y1
rise = pointB.getY() - self.getY()
# x2 - x1
run = pointB.getX() - self.getX()
# (y2 - y1) / (x2 - x1)
return rise / run
def getPoint(self):
# Return the tuple representing the point.\
return (self.__x, self.__y)
def getX(self):
# Return the x-coord (only)
return self.__x
def getY(self):
# Return the y-coord (only)
return self.__y
def __getitem__(self, index):
if index == 0:
return self.__x
elif index == 1:
return self.__y
else:
raise "Index " + str(index) + " out of bounds."
def resetX(self, newX):
# Reset only the x-coordinate.
self.__x = newX
def resetY(self, newY):
# Reset only the y-coordinate.
self.__y = newY
def resetP(self, newX, newY):
# Reset both x, y values.
self.__x = newX
self.__y = newY
def __eq__(self, b):
if self.__x == b.getX() and self.__y == b.getY():
return True
else:
return False
def __str__(self):
# Return the tuple (x, y) as a string.
return str((self.__x, self.__y))
def __repr__(self):
# Return the string representation of the point.
# @See __repr__ from global module index.
return str(self)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment