# Rohan Sangani
# 11/3/2025
# Simple Class to support Elliptic Curves
# Adapted from https://www.cs.ucf.edu/~dmarino/ucf/cis3362/progs/EllipticCurve.java

import random

# Should all be self-explanatory
class EllipticCurve:
    def __init__(self, prime, a, b):
        self.p = prime
        self.a = a
        self.b = b

    def __copy__(self):
        return EllipticCurve(self.p, self.a, self.b)

    def __eq__(self, other):
        return (self.p == other.p and
                self.a == other.a and
                self.b == other.b)

    ''' Added by Arup to get ECC El-Gamal to work. '''
    # Pre-condition, prime for curve is 3 mod 4.
    # Returns None if there's no point on the curve with x coordinate myx, otherwise
    # returns the point myx and the first matching y the algorithm gives.
    def getMatchingY(self, myx):

        # First calculate correct RHS on this curve equation for this x.
        c = (myx*myx*myx + self.a*myx + self.b)%self.p

        # Now, do the Legendre symbol.
        rem = pow(c, (self.p-1)//2, self.p)

        # One matching y value so (x, 0) on curve.
        if rem == 0:
            return 0

        # Not a quadratic residue at all.
        elif rem != 1:
            return None

        # Yes, it's a quadratic residue and this is one matching value of y.
        # out of two.
        return pow(c, (self.p+1)//4, self.p)

    # Returns a random point on this curve. Since I can't do circular
    # imports, I return the point as a tuple.
    def getRandomPoint(self):

        x = 0
        y = 0

        # Loops till we successfully generate a point.
        while True:

            # Try a random x and find its matching y.
            x = random.randint(1, self.p-1)
            y = self.getMatchingY(x)

            # Success.
            if y != None:
                break
            
        # This is our point.
        return (x,y)