Annuler
connectez vous
arithmétique en post-bac
- Arithmétique dans Z - supérieur
- Exercice : le petit théorème de Fermat
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Un best-of d'exos de probabilités (après le bac)
- Espaces vectoriels et Applications linéaires - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Licence Maths 1e ann ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
Test de primalité
Posté par freddou06
bonjour all!
j'ai une ptite question de comprehension sur le test suivant;
le but de ce test est de tester si un grand entier m (~1020) est premier.
On fait le test suivant:
on choisit a au hazard entre 1 et m-1 puis on calcul am-1
Si am-1
1[m] alors m n'est pas premier.
Si am-1
1[m] alors m est peut etre premier..
on dit ensuite que si m n'est pas premier alors il existe a compris entre 1 et m-1 qui ne sont pas premier avec m et pour ces a on a forcement am-11[m]
et pour les a premier avec m?!
on ne peut rien dire non?!
merci d'avance!
Bonjour
Non, on ne peut rien dire; mais si m est vraiment très grand, il est bon de l'éliminer des listes assez vite, si on trouve un a tel que
En effet on ne peut pas, sachant , conclure quant à la primalité de m : l'exemple des nombres de Carmichael (très rares et dont le plus petit est 561) est édifiant à ce sujet : ils sont non premiers et pourtant ils ne sont pas détectés comme tels par le test. Plusieurs sources sur le web détaillent leur construction assez épique...
[Au passage, et afin d'être lisibles pour un moteur de recherche, on parle dans ce topic du test de primalité de Fermat].
"l'exemple des nombres de Carmichael (très rares et dont le plus petit est 561) est édifiant à ce sujet : ils sont non premiers et pourtant ils ne sont pas détectés comme tels par le test. "
Les nombres de carmickael sont les nombres m non premiers qui verifient si a
{1,..,m-1} premier avec m alors am-11[m] quand tu dis qu'il ne sont pas detecté par ce typre de test c'est en general non?! car si on tombe sur un a qui n'est pas premier avec m le test montre que m n'est pas premier( bien que tomber sur un tel a est rare d'apres ce que jai vu)
par exemple si m = 561 et qu'on tombe sur a = 3 on va avoir a 1[561] car pgcd(3,561) 1 donc le test en deduira que m nest pas premier non?! donc ca peut marcher aussi avec un nombre de carmickael mais rarement c'est ca?!
Heu, reprenons calmement.
3 est premier, donc dire que pgcd(3,561) 1 c'est dire que 3 divise 561, n'est-ce pas ? En l'occurrence c'est vrai [critère de divisibilité].
Malheureusement le test de Fermat est bien plus dur à exécuter ici puisque il faut voir si ce qui est une autre paire de manches !
Le but des nombres de Carmichael, c'est vraiment que pour tout a que tu te choisis, on va bien avoir et pourtant il n'est pas premier.
m = 561 et a = 3 moi je suis sur que si a{1,...,m-1} n'est pas premier avec m alors on a forcement am-11[m]
en effet dans Z/mZ = {1',2',...,m-1'}
on sais que a' Z/mZ est invresible ssi pgcd (a,m) = 1
donc a' non inversible ssi pgcd(a,m) 1
et on a: am-1 = 1[p] <--> a.am-2 = 1[m] --> pgcd(a,m) = 1 --> a' est inversible
donc on en deduit a non premier avec m ---> a' non inversible --> am-1 1[p].. donc mm pour un nombre de carmickael je pense que 35601[560]
apres comme il est dit dans mon cours lorsque m est tres grand, la probabilité d'avoir un nombre a non premier avec m est tres petites... c'est peut etre pourquoi on dit que ce type de test ne marche pas avec les nombres de carmickael car le plus souvent a sera premier avec m...
vous en pensez quoi?
Ok Freddou06, ça y est je vois ce que tu voulais dire. En effet (modulo quelques coquilles dans ton dernier post, notamment fait gaffe quand tu définis Z/mZ qui a m éléments !) tu m'éclaires sur quelque chose que je n'avais pas vu dans un premier temps : en fait on a pas équivalence entre et
. Le deuxième implique le premier (donc la négation du premier implique celle du deuxième).
Du coup, les nombres de Carmichael s'éloignent un petit peu du sujet de ce post (cf leur définition). Snif snif. J'ai perdu une occasion de me taire.
Pour éviter de les enchaîner, je ne vais pas prendre la liberté supplémentaire de confirmer ton affirmation du dernier post, même si au final j'ai l'impression que c'est plus toi qui a tout compris.
Pour me faire pardonner, petit récap' sur le sujet "test de Fermat" :
PTF (Petit Théorème de Fermat) : p premier et pgcd(p,a)=1
est multiple de p.
Corollaire : si p premier et pgcd(p,a)=1, alors est multiple de p.
Contraposée du PTF : si on trouve un tel que
n'est pas multiple de p, alors p est non premier.
Réciproque du PTF fausse : 561 = 3.11.17 est non premier mais pourtant pour tout a tel que pgcd(561,a)=1, on a .
Tout à fait, et donc vu ma révélation tardive deux posts plus haut, la fin du post 7 était fausse et a impliqué un imbroglio (en fait deux, cf un autre topic quasi simultané).
Je note dans mon petit carnet "ne plus intervenir sur les sujets d'arithmétique" (juste après "penser à réviser l'arithmétique pour l'agreg").