# ##########################################################################
#  Calcul des clés publique et privée pour le chiffrement asymétrique RSA
#  Mars 2025
#  nsi.gecif.net
# ##########################################################################

def euclide_etendu(a,b):
    if a==0:
        return (b,0,1)
    else:
        g,x1,y1 = euclide_etendu(b%a,a)
        x=y1-(b//a)*x1
        y=x1
        return (g,x,y)

# Saisissez une valeur pour p, q et e :
p=47
q=59
e=157

# Calcul automatique de n, phi et d :
n=p*q
phi=(p-1)*(q-1)
d=euclide_etendu(e,phi)[1]

# Affichage des clés pour le chiffrement RSA :
print("Clé publique : (%d,%d)" % (n,e))
print("Clé privée : (%d,%d)" % (n,d))