Tu peux regarder la page Wikipédia sur les tests de primalité. Dans certains cas, on utilise des méthodes probabilistes (Miller-Rabin par exemple) et donc on n'a pas la réponse avec une certitude absolue. Il existe des algorithmes non probabilistes en temps polynomial (en la taille du nombre) comme le test AKS et ses variantes.
une multitude tests ont été développés avec les moyens de calcul de plus en plus performants. Il y a énormément de liens sur le sujet sur le net. La compréhension de certains algorithme peut demander des connaissances relativement avancées en arithmétique voire au delà ( tests basés sur les fonctions elliptiques, utilisation de la transformée de Fourier rapide etc...)
Les algorithmes les plus efficaces en temps de calcul ne donnent pas nécessairement une certitude sur la primalité mais une probabilité très faible d'erreur, probabilité que on peut rendre aussi faible que on veut pour certains ( qui se paie évidemment en temps de calcul).
Un test très classique est celui de Miller- Rabin qui est un raffinement du petit théorème de Fermat \(a^{p-1}\equiv 1 mod(p)\) diminuant significativement le risque que \(p\) vérifie Fermat sans être premier. Mais ce test ne garantie pas à 100% que le nombre testé est premier .
Il existe un test déterministe relativement efficace pour dire si un nombre de Mersenne \( 2^n -1\) est premier , utilisant la transformée de Fourier rapide. C'est pourquoi la presque totalité des derniers grands nombres premiers prouvés sont des nombres de Mersenne. Le dernier exhibé date de fin 2018. cf article wiki sur le sujet: https://fr.wikipedia.org/wiki/Plus_grand_nombre_premier_connu
tout ce qui est simple est faux, tout ce qui est compliqué est inutilisable
L'univers des nombres premiers est un univers complexe. Il y a des tas de gens très sérieux qui travaillent sur le sujet, qui trouvent des résultats, des petits résultats, peu exploitables par le commun des matheux.
Et il y a aussi des tas de gens qui travaillent sur le sujet et qui sont convaincus d'avoir des tas de preuves sur tel ou tel sujet, mais qui en fait n'ont ren du tout. Tous les pseudos mathématiciens qui se croient compétents mais qui ne savent pas ce qu'est une démonstration vont écrire un jour ou l'autre un truc sur les nombres premiers.
Donc, attention quand tu lis des choses sur le net sur le sujet, il y a à boire et à manger.
Ceci dit, les liens donnés par mes amis sont des liens très fiables.
Je vous remercie pour ces explications et et ces références.
Je ne connais rien en encryptage mais je me demandais comment ils font pour s'assurer que leur clé est bien un nombre premier.
Ce que j'en comprend, ils prennent une chance ...
Le Tout est souvent plus grand que la somme de ses parties.
Grands nombres premiers
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.