def decompose(n): #retournera une liste qui contient les facteurs premiers d'un nombre """ Exemple : decompose(561) retourne [3, 11, 17] """ liste_facteurs = [] i=2 while n>1: while n%i==0: liste_facteurs.append(i) n=n/i i=i+1 return liste_facteurs def expmodrap(a, e, n): #exponentiation modulaire rapide """ Permet de calculer a exposant e modulo n """ p=1 while e>0: if e % 2 == 1: p = (p*a)%n a=(a*a)%n e=e//2 return p def multiple_test(nb, l): #retourne vrai si pas multiple d'un facteur premier de nb (l est la liste des facteurs premiers) if True in [nb%i==0 for i in l]: return True else: return False nombre = int(input("Entrez le nombre à tester")) liste_facteurs = decompose(nombre) carmichael = True #passera à False si non i-pseudo-premier for i in range (2, nombre): if not multiple_test(i, liste_facteurs): if expmodrap(i, nombre-1, nombre) == 1: print(nombre, "est "+str(i)+"-pseudo-premier") else: print(nombre, "n'est PAS "+str(i)+"-pseudo-premier") carmichael = False if carmichael: print(nombre, " est un nombre pseudo-premier (de Carmichael)") else: print(nombre, " n'est PAS un nombre pseudo-premier (de Carmichael)")