from random import *

def nombre_premier(n,k):  # trouver un nombre premier N à n chiffres avec k tests, tel que N (mod 4) = 3
    s = 0
    while s == 0:
        N = 0
        while (N%10 in [0,2,4,5,6,8]) or sum(int(c) for c in str(N))%3 == 0 or N%4 != 3:
            N = randint(10**(n-1),10**n-1)
        s = 1
        for i in range(k):
            A = randint(2,N-1)
            if pow(A,N-1,N) != 1:
                s = 0
    return(N)

n = 50
k = 30
P = nombre_premier(n,k)
Q = nombre_premier(n,k)
N = P * Q

print("Nombre N:",N,"\n")

# tiré de https://www.techiedelight.com/fr/extended-euclidean-algorithm-implementation/ :
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = extended_gcd(b % a, a)
        return gcd, y - (b // a) * x, x

s = 0
while s == 0:
    C = randint(2,N-1)
    DP = pow(C,(P-1)//2,P)
    DQ = pow(C,(Q-1)//2,Q)
    if DP == 1 and DQ == 1:
        s = 1
        MP = pow(C,(P+1)//4,P)
        MQ = pow(C,(Q+1)//4,Q)

print("Nombre C:",C,"\n")

PGDC,XP,XQ = extended_gcd(P,Q)

R1 = (XP*P*MQ+XQ*Q*MP)%N
R2 = N-R1
R3 = (XP*P*MQ-XQ*Q*MP)%N
R4 = N-R3

print("Voici les quatre racines de C modulo N:")
print(R1)
print(R2)
print(R3)
print(R4)
print("\n")