Utiliser un test probabiliste de primalité afin d'évaluer si un entier \boldsymbol{n} est premier ou non, à l'aide d'une des deux méthodes.

1. Dans la fonction ci‑dessous on considère un entier n \geqslant 3.


À quoi sert la commande % ?

2. a. D'après le petit théorème de Fermat, que renvoie l'algorithme lorsque n est un nombre premier ?

b. Que peut‑on dire lorsque la valeur de F affichée en sortie d'algorithme n'est pas égale à 1 ?

c. Tester cet algorithme pour une dizaine de valeurs afin de vérifier les observations. Que remarque‑t‑on pour n=561 ? Cet entier est‑il premier ?

3. Les observations ci‑dessus servent à élaborer un test permettant de déterminer si le nombre n a des chances d'être premier.

def testfermat2(n):
	F = 2**(n-1) % n
	if ... :
		return("Peut-être premier")
	else :
		return ("Pas premier")

a. Compléter la condition à tester ligne 3.

b. Tester l'algorithme avec quelques valeurs puis tester l'algorithme pour n=154 515 677.

c. Quel est l'avantage et l'inconvénient de cet algorithme par rapport à celui consistant à tester l'ensemble des diviseurs possibles entre 1 et \sqrt{n} ?

Les entiers p qui ne sont pas premiers mais qui vérifient a^{p-1} \equiv 1[p], dès lors que a et p sont premiers entre eux, sont appelés les nombres de Carmichael, du nom du mathématicien américain Robert Daniel Carmichael (1879‑1967), qui s'est tout particulièrement intéressé aux propriétés de ces nombres. Il a été démontré en 1994 qu'il existe en fait une infinité de nombres de Carmichael.