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 = 100
k = 30
N = nombre_premier(n,k)

# Tester que si N est un nombre premier, alors pour "tout" nombre C, C**((N-1)//2) (mod N) = 1 ou N-1
# ici, on tire 100 nombres C au hasard entre 2 et N-1

L = []
for i in range(100):
    C = randint(2,N)
    D = pow(C,(N-1)//2,N)
    if D == N-1:  # Si D vaut N-1, on remplace sa valeur par -1 (ce qui revient au même modulo N) 
        D = -1
    L += [D]
print("Nombre premier N = ",N,"\n")
print("Liste de C**((N-1)//2) avec C aléatoire:")
print(L,"\n")

# Calculer la racine M d'un nombre C modulo N si celui-ci satsifait le critère d'Euler

s = 0
while s == 0:
    C = randint(2,N-1)
    D = pow(C,(N-1)//2,N)
    if D == 1:
        s = 1
        M = pow(C,(N+1)//4,N)

print("Nombre C =",C)
print("Racine M =",M)
print("Check: M**2 (mod N) =",pow(M,2,N))