Nombres de Fermat, algorithme de casse des nombres premiers.

Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
Lemniscate
Membre Relatif
Messages: 300
Enregistré le: 18 Jan 2009, 21:55

Nombres de Fermat, algorithme de casse des nombres premiers.

par Lemniscate » 19 Fév 2009, 19:58

Bonjour,

Je voulais savoir pourquoi on ne connaissait pas la primalité des nombres de Fermat () à partir du rang n=33 (cf article de wikipedia) ?

Vu qu'on a des algorithmes de décomposition en facteurs premiers, en théorie (dussions nous y passer une éternité) on devrait connaître tous les nombres premiers de la forme de Fermat ? Ou au moins plus que 33 ?

Merci pour vos futures réactions !

Au revoir.

EDIT : Oui pardon pour le "+1" oublié à Fn, j'étais tellement content d'avoit mis le ^{2^{n}} que j'ai oublié le "+1" :)



uztop
Membre Complexe
Messages: 2396
Enregistré le: 12 Sep 2007, 13:00

par uztop » 20 Fév 2009, 01:22

Bonjour,

il manque le +1 à la fin, sinon il ne risque pas d'être premier !
Sinon c'est déjà beaucoup (plus de 8 milliards); donc Or, comme on a , on peut dire en gros que est de l'ordre de soit quelque chose comme .
En contant à la louche comme ça, aurait donc 2 milliards 400 millions de chiffres ! On ne risque pas de pouvoir tester tous les nombres pour voir s'il est premier.

Lemniscate
Membre Relatif
Messages: 300
Enregistré le: 18 Jan 2009, 21:55

par Lemniscate » 20 Fév 2009, 17:49

Oui c'est un très grand nombre ! Mais ne peut-on pas imaginer que dans le futur les ordinateurs connaissent un bond dans leur rapidité de calcul, et que l'on puisse faire (par exemple) les calculs fois plus vite que maintenant ? (avec n supérieur ou égal à 1 :) )

Ou si l'on pose le problème autrement : si un ordinateur surpuissant (à l'heure actuelle) passe disons 1 millénaire (ou plus) sur l'algorithme de décomposition en premiers le plus rapide que l'on connaisse à l'heure actuelle appliqué à , ne peut-on pas imaginer qu'on résolve le problème ?

De plus pourquoi sait-on que n'est pas premier alors que est aussi très grand !?

Merci pour ta réponse cependant uztop !

Au fait, dans ton message, c'est ça ?

Eh dites : Au fait d'où vient le dessin de trèfle de ton avatar uztop ? Est-ce juste une figure au hasard ou un objet mathématique bien précis ?

uztop
Membre Complexe
Messages: 2396
Enregistré le: 12 Sep 2007, 13:00

par uztop » 20 Fév 2009, 23:38

je ne sais pas comment on a déterminé que est composé mais c'est un nombre beaucoup plus petit que ; en gros il contient deux fois moins de chiffres.
La puissance de calcul des ordinateurs augmente, mais ne permettra jamais de tester tous les facteurs de manière exhaustive. Si on considère qu'elle double tous les deux ans (c'est une approximation basée sur la loi de Moore, bien entendu on y arrivera pas vu qu'on sera bloqués avant par des effets quantiques entre autres), dans un millénaire, on l'aura multipliée par , c'est pas mal mais le rapport entre et est plutôt de l'ordre de .
Sinon, mes calculs sont basés sur le fait que ; ce n'est pas tout à fait vrai mais ça donne un ordre de grandeur.

En ce qui concerne mon avatar, le trèfle est le symbole de l'Irlande. J'ai trouvé ce dessin avec un recherche google du genre "shamrock + maths"; je ne sais pas si ça représente quelque chose.

ThSQ
Membre Complexe
Messages: 2077
Enregistré le: 10 Oct 2007, 19:40

par ThSQ » 21 Fév 2009, 22:37

Je doute qu'on teste la primalité des nombres de Fermat en divisant de manière exhaustive. Il y a plein de tests (tests de Pépin, Inkeri, ...) et on connait exactement la forme des diviseurs.

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5336
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 21 Fév 2009, 23:45

Lemniscate a écrit:Je voulais savoir pourquoi on ne connaissait pas la primalité des nombres de Fermat () à partir du rang n=33 (cf article de wikipedia) ?


Dans une "chasse au papillon" (critère heuristique simpliste), on obtient rapidement que 6597069766657 divise F_38

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5336
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 22 Fév 2009, 00:26

Quelques divisibilités au hasard des papillons...

uztop
Membre Complexe
Messages: 2396
Enregistré le: 12 Sep 2007, 13:00

par uztop » 22 Fév 2009, 01:26

je ne voudrais pas dire de bêtises mais les algos de tests de primalité qu'on connait sont probabilistes. En gros, soit l'algo trouve un diviseur et le nombre n'est pas premier, soit il n'en trouve pas et on ne peut pas répondre (on sait juste qu'il a une probabilité très élevé d'être premier).

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5336
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 22 Fév 2009, 01:39

uztop a écrit:je ne voudrais pas dire de bêtises mais les algos de tests de primalité qu'on connait sont probabilistes. En gros, soit l'algo trouve un diviseur et le nombre n'est pas premier, soit il n'en trouve pas et on ne peut pas répondre (on sait juste qu'il a une probabilité très élevé d'être premier).

Ce n'est pas tout à fait comme ça : les tests de primalité (bcp sont probabilistes, mais certains ne le sont pas je crois) sont capables de certifier qu'un nombre n'est pas premier sans en général donner de diviseur. C'est la différence entre test de primalité et factorisation explicite. C'est là-dessus que reposent certains algos de cryptage.

Par exemple, un premier test assez efficace malgré sa simplicité : soit q>5

-- calculer 2^(q-1) mod q :
si c'est différent de 1, alors q n'est pas premier (mais cela ne donne aucun diviseur de q).
si c'est égal à 1, alors je dirais qu'il y a 98 % de chance que q soit premier.

-- calculer 2^(q-1) mod q et 3^(q-1) mod q :
si les deux valent 1, alors je dirais qu'il y a 99.5 % de chance que q soit premier

Navis
Messages: 5
Enregistré le: 10 Aoû 2019, 14:35

Re: Nombres de Fermat, algorithme de casse des nombres premi

par Navis » 10 Aoû 2019, 20:10

Il y a aussi le théorème de Wilson, mais il introduit le calcul de factorielle:

p est premier <=> (p-1)!=-1[p]

 

Retourner vers ⚜ Salon Mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 5 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite