Test de primalité de Fermat

Utiliser un test probabiliste de primalité afin d'évaluer si un entier $\mathbf{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⩾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=154515677$.

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.