Utiliser un test probabiliste de primalité afin d’évaluer si un entier 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 à 2 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.)
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 n est premier ?
3. Si une cellule de la colonne B n’est pas égale à 1, que peut‑on dire du nombre n correspondant ?
4.a. Lister l’ensemble des entiers n inférieurs à 46 dont la cellule de la colonne B est égale à 1.
Que remarque‑t‑on ?
b. Combien vaut 240 modulo 561 ? En déduire 2560[561]. Le nombre 561 est‑il premier ?
c. Finalement, que peut‑on dire lorsque la cellule de la colonne B est égale à 1 ?
MÉTHODE DE RÉSOLUTION 2
PYTHON
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 n ?
Histoire des maths
Les entiers p qui ne sont pas premiers mais qui vérifient ap−1≡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.
Utilisation des cookies
Lors de votre navigation sur ce site, des cookies nécessaires au bon fonctionnement et exemptés de consentement sont déposés.