Chargement de l'audio en cours
Plus

Plus

TP1. Test de primalité de Fermat
P.154

Mode édition
Ajouter

Ajouter

Terminer

Terminer

TP INFO


1
Test de primalité de Fermat





Objectif

Utiliser un test probabiliste de primalité afin d’évaluer si un entier est premier ou non, à l’aide d’une des deux méthodes.
MÉTHODE DE RÉSOLUTION 1
TABLEUR

1. a. Dans un tableur, entrer la liste des 46 premiers nombres entiers strictement supérieurs à dans la colonne A.
Dans la cellule B3, entrer la formule : =MOD(2^(A3-1);A3).
Étendre ensuite la formule à toute la colonne. (Fichier téléchargeable ici.)

maths expertes - chapitre 5 - Nombres premiers - TP1. Test de primalité de Fermat - méthode 1

b. À quoi la commande MOD sert‑elle ?


2. D’après le petit théorème de Fermat, quel nombre est affiché dans la colonne B lorsque est premier ?


3. Si une cellule de la colonne B n’est pas égale à , que peut‑on dire du nombre correspondant ?


4. a. Lister l’ensemble des entiers inférieurs à dont la cellule de la colonne B est égale à .
Que remarque‑t‑on ?


b. Combien vaut modulo  ? En déduire . Le nombre est‑il premier ?


c. Finalement, que peut‑on dire lorsque la cellule de la colonne B est égale à  ?
Voir les réponses
MÉTHODE DE RÉSOLUTION 2
PYTHON

1. Dans la fonction ci‑dessous on considère un entier .

maths expertes - chapitre 5 - Nombres premiers - TP1. Test de primalité de Fermat - méthode 2

À quoi sert la commande % ?


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


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


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




3. Les observations ci‑dessus servent à élaborer un test permettant de déterminer si le nombre 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 .

c. Quel est l’avantage et l’inconvénient de cet algorithme par rapport à celui consistant à tester l’ensemble des diviseurs possibles entre et  ?
Voir les réponses

Histoire des maths

Les entiers qui ne sont pas premiers mais qui vérifient , dès lors que et 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.