Nombres de Fermat, algorithme de casse des nombres premiers.

[Lemniscate]

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]

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]

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]

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]

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.

[leon1789]

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

[leon1789]

Quelques divisibilités au hasard des papillons...

[uztop]

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).

[leon1789]

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]

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

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