gistfile1.txt

# Import modular inverse from sympy
from sympy import mod_inverse

# Elliptic curve parameters
a = 497
b = 1768
p = 9739  # prime modulus

# Function to add two points on the elliptic curve
def elliptic_add(P, Q):
    # Handle special cases with point at infinity
    if P == 'O':  # Identity element
        return Q
    if Q == 'O':
        return P

    x1, y1 = P
    x2, y2 = Q

    # If x1 == x2 and y1 == -y2 (mod p), the result is the point at infinity
    if x1 == x2 and (y1 + y2) % p == 0:
        return 'O'

    # Compute the slope (lambda)
    if P != Q:
        numerator = (y2 - y1) % p
        denominator = (x2 - x1) % p
    else:
        numerator = (3 * x1**2 + a) % p
        denominator = (2 * y1) % p

    # Compute lambda using modular inverse
    lam = (numerator * mod_inverse(denominator, p)) % p

    # Calculate resulting point coordinates
    x3 = (lam**2 - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p

    return (x3, y3)

# Given points
P = (493, 5564)
Q = (1539, 4742)
R = (4403, 5202)

# Step-by-step computation: S = P + P + Q + R
S1 = elliptic_add(P, P)     # P + P
S2 = elliptic_add(S1, Q)    # (P + P) + Q
S = elliptic_add(S2, R)     # ((P + P) + Q) + R

# Verify if S lies on the curve
x, y = S
left_side = (y**2) % p
right_side = (x**3 + a*x + b) % p
on_curve = left_side == right_side

# Print the result
print("S =", S)
print("Is S on the curve?", on_curve)