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 n\boldsymbol{n} 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 à 22 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 nn est premier ?


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


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


b. Combien vaut 2402^{40} modulo 561561 ? En déduire 2560[561]2^{560} [561]. Le nombre 561561 est‑il premier ?


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

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

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 nn est un nombre premier ?


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


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




3. Les observations ci‑dessus servent à élaborer un test permettant de déterminer si le nombre nn 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 677n=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 11 et n\sqrt{n} ?
Voir les réponses

Histoire des maths

Les entiers pp qui ne sont pas premiers mais qui vérifient ap11[p]a^{p-1} \equiv 1[p], dès lors que aa et pp 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.
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.