Solutions for Scalar Multiplication

solution.py

def mod_inv(a, p):
    """ Calcule l'inverse modulaire de a modulo p """
    return pow(a, -1, p)

def add_points(x1, y1, x2, y2, a, p):
    """ Ajoute deux points sur une courbe elliptique """
    if x1 == x2 and y1 == (-y2 % p):  # Cas P + (-P) = O
        return None
    
    if x1 == x2 and y1 == y2:  # Doublage
        lambd = ((3 * x1**2 + a) * mod_inv(2 * y1, p)) % p
    else:  # Addition normale
        lambd = ((y2 - y1) * mod_inv(x2 - x1, p)) % p
    
    x3 = (lambd**2 - x1 - x2) % p
    y3 = (lambd * (x1 - x3) - y1) % p
    
    return (x3, y3)

def scalar_mult(k, x, y, a, p):
    """ Calcule k * P en utilisant l'algorithme Double-and-Add """
    R = None  # Point à l'infini (élément neutre)
    Q = (x, y)  # Initialisation avec P

    while k > 0:
        if k % 2 == 1:  # Si le bit de poids faible est 1, on ajoute Q à R
            R = add_points(R[0], R[1], Q[0], Q[1], a, p) if R else Q
        Q = add_points(Q[0], Q[1], Q[0], Q[1], a, p)  # Doublement de Q
        k //= 2  # Division entière de k par 2

    return R

# 📌 Paramètres de la courbe elliptique
p = 9739
a = 497
b = 1768

# Point donné
P = (2339, 2213)
k = 7863  # Scalaire

# 📌 Calcul de Q = [7863] * P
Q = scalar_mult(k, P[0], P[1], a, p)

print(f"[✅] Résultat Q = {Q}")