Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(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

Pied de page des forums