# Inverses using Bezout

def inverse(a,n):
    a=a%n
    if gcd(a,n)!=1:
        raise ValueError("Inverse does not exist")
    return bezout(a,n)[0]%n

####################################################

# Addition of points on a pseudo EC

def EC_addition(E,P,Q):
# E = [A,B,p] corresponds to y^2 = x^3+Ax+B modulo p
# Output is P+Q, or evidence that this is not possible when E is a pseudo EC
    [A, B, p] = [E[0]%E[2], E[1]%E[2], E[2]];

# Verify that E is non-singular;
    #Complete with an 'if' statement involving fastExp
      #print('E is singular')
      #return None

# Verify that P,Q are points on E, provided they have coordinates
    if P!=0:
        [xP, yP]  = [P[0]%p, P[1]%p];
        #Complete with an 'if' statement involving fastExp
            #print(str(P)+' is not on the elliptic curve E')
            #return None

    if Q!=0:
        [xQ, yQ]  = [Q[0]%p, Q[1]%p];
        #Complete with an 'if' statement involving fastExp
            #print(str(Q)+' is not on the elliptic curve E')
            #return None

# Deal with the trivial cases
    if P == 0: return Q
    if Q == 0: return P

# Deal with the symmetric cases
    if P != Q and xP == xQ: return 0  # P and Q different, but symmetric
    if P == Q and yP == 0:  return 0  # P and Q same, and symmetric

# Deal with the non-symmetric cases
        #if P != Q:
        #Fill in each of the following values.  Remember to involve %p
        #num = ??;  # numerator of M
        #den = ??;  # denominator of M

    #if P == Q:
        #num = ??;  # numerator of M
        #den = ??;  # denominator of M

    witness = gcd(den,p);                     # Checks that d is a unit modulo p
    if witness != 1: return [None, witness]   # Only possible when E is a pseudo EC

    M = (num*inverse(den,p))%p;
    %xR = ??
    %yR = ??
    %return [xR, (-yR)%p]
    return None # Delete once you complete previous line
####################################################
# Computing a positive multiple of a point on an elliptic curve

def bitList(e): #Already used before
    B=bin(e)
    b=len(B)
    L=[]
    for i in range(1,b-1):
        L=L+[int(B[b-i])]
    return L

def doublesList(E,P,k): # Computes P, 2P, ... (2^k)P or evidence that this is not possible
    L = [P];
    for i in range(0,k):
        A = EC_addition(E,L[i],L[i]);
        if A[0]==None:
            return A
        L = L +[A]
    return L

def EC_multiple(E,P,e):  #Output is eP
    B=bitList(e)
    k=len(E)-1
    L=doublesList(E,P,k)
    if L[0]==None:
        return L
    m = 0;
    for i in range(0,k+1):
        if B[i]!= 0:
            m = EC_addition(E,m,L[i])
            if m!= 0 and m[0]==None:
                break
    return m

####################################################

def EC_random(p):
# Generates a random EC, and a random point P on this EC.
    [x, y] = [randint(0, p - 1), randint(0, p - 1)];
    A = randint(0, p - 1);
    B = (fastExp(y,2,p)-fastExp(x,3,p)-A*x)%p;
    return([[A,B,p],[x,y]])

####################################################

def factorial_lenstra(E,P,b):
# Implementation of Lenstra's factoring algorithm using factorials;  b specifies how hard to try
# In other words, attempt to compute P, (2!)P, (3!)P, ... (b!)P in an attempt to factor p
# Assumes that P lies on E
    i=1;
    Q=P;
    # while Q[0]!=None and i<b:
    # Write 'while' loop that iteratively computes P_k = (k!)P as described in the math component
    # Keep track of i by augmenting it
    if i == b:
        print('No luck.  Try again, maybe increase b?')
        return None
    return [E,P,i,Q[1]] # What is being returned?

####################################################

def random_factorial_lenstra(n,b):
# Lenstra's algorithm with a randomly generated pseudo EC modulo n;  b specifices how hard to try
# Call functions you've already written
  return None #remove this once you've finished