Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
Discussion fermée
#1 02-11-2008 21:42:06
- Golgup
- Membre actif
- Inscription : 09-07-2008
- Messages : 574
Fermat et son test..
Bonjour,
Pourquoi s'embêter avec des tests de primalité probabilistes.. ou autres.. alors que celui de Fermat qui est très simple nous assure á 100% de la primalité/non primalité d'un nombre? Pourquoi ne pas s'en tenir á celui là? D'autant plus que nous ne sommes même pas bloqué par la taille des nombres (raisonnablement) puisque on peut utiliser l'exponnentiation binaire?
a+
[édit]
Je précise que je parle du test qui dit que si un nombre n est 1er, alors (2^(n-1))-1 = 0 mod n
Dernière modification par Golgup (02-11-2008 22:03:54)
« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »
Hors ligne
#2 02-11-2008 22:19:24
- Barbichu
- Membre actif
- Inscription : 15-12-2007
- Messages : 405
Re : Fermat et son test..
Salut,
Ceci est vrai : Si n est premier, alors (2^(n-1))-1 = 0 mod n
Ceci est faux : Si (2^(n-1))-1 = 0 mod n, alors n est premier
Ceci est vrai : Si (2^(n-1))-1 != 0 mod n, alors n non premier
A=>B ne signifie pas non A => non B
par contre on a : non B => non A.
Du coup ça nous assure la non primalité et absolument pas la primalité.
++
Barbichu
Hors ligne
#3 05-11-2008 22:43:20
- Golgup
- Membre actif
- Inscription : 09-07-2008
- Messages : 574
Re : Fermat et son test..
Re,
Ok! merci
et,
Ceci est faux : Si (2^(n-1))-1 = 0 mod n, alors n est premier
J'ai cherché trés loin (dans les nombres impairs), et tous les n qui répondent à cette réciproque étaient des nombre 1er. Alors? On en a trouvé un au moins de contre exemple?
Et, ca a été prouvé que ceci était faux?
a+
« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »
Hors ligne
#4 05-11-2008 23:38:06
- Barbichu
- Membre actif
- Inscription : 15-12-2007
- Messages : 405
Re : Fermat et son test..
Hello,
pour prouver que c'est faux, il suffit de trouver un contre-exemple, on peut en trouver un sur la page wikipédia : http://fr.wikipedia.org/wiki/Test_de_pr … _de_Fermat
(C'est un contre-exemple plus fort, car il dit que (a^(n-1))-1 = 0 mod n pour tous les a premiers avec 561, la page http://fr.wikipedia.org/wiki/Nombre_pseudopremier te dit que le premier contre-exemple pour ton cas particulier est 341, l'avais-tu testé ?).
++
Dernière modification par Barbichu (05-11-2008 23:38:24)
Barbichu
Hors ligne
#5 07-11-2008 19:41:19
- Golgup
- Membre actif
- Inscription : 09-07-2008
- Messages : 574
Re : Fermat et son test..
Re,
Bizarre! je l'ai forcement testé.. Je vaischercher l'erreur dans le prog.
En tous cas, merci pour tes réponses.
@+
« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »
Hors ligne
#6 05-12-2008 10:11:19
- sinuspax
- Membre
- Inscription : 19-08-2008
- Messages : 47
Re : Fermat et son test..
Bonjour,
En faisant ton test tu dois tomber sur ce que l'on nomme des "pseudo-premiers", c'est-à-dire des entiers qui se comportent comme des premiers (dans le test) mais qui sont composés.
Ex : 341, 561, 2047 ...
C'est la pouasse des tests de primalité. Lorsque tu trouves ces nombres indésirables, tu peux tester chaque entier impair à la fois en base 2 et en base 3. Par exemple, si n est premier : 3 ^ n - 1 mod n = 1. On s'aperçoit que 341 et 2047 sont composés, car 3 ^ n - 1 mod 341 et mod 2047 donne autre chose que 1.
Mais, malheureusement, un nombre tel que 561 passe TOUTES les bases du test de Fermat : 2, 3, 5, 7, etc.
Un tel nombre est dit "nombre de Carmichael".
Pour éviter ces empêcheurs de tourner en rond, il faut utiliser le test de Rabin-Miller, qui les reconnait comme composés.
Mais là encore, ce test très efficace ne reconnait pas à 100% les premiers, seulement les composés.
Toutefois la probabilité pour qu'ils ne soient pas premiers est très faible.
Hors ligne
#7 05-12-2008 22:36:57
- Golgup
- Membre actif
- Inscription : 09-07-2008
- Messages : 574
Re : Fermat et son test..
'Jour,
Oui merci, j'ai appris justement ça pas loin aprés avoir posté le com..
++
« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »
Hors ligne
Pages : 1
Discussion fermée