Cours arithmétique et cryptographie

Profitez de ce manuel de formation en PDF pour comprendre mieux le cryptographie et enrichir votre connaissance.

Commencez à télécharger ce cours adapté pour vous et à apprendre cryptographie.

24096+ 1 il donne une reponse negative en moins d’une seconde, pour 2 16384+ 1il met seize secondes.) L’ordinateur factorise instantanement :232+ 1 = 641 67004172 64+ 1 = 274177 672804213107212 128+ 1 = 59649589127497217 5704689200685129054721et il met moins de 5 secondes pour 2 256+ 1. En revanche, il cale sur lesuivant 13, a savoir 2 512+ 1 (qui a quand m^eme 150 chires, c’etait il n’ya pas si longtemps le record du monde de factorisation). En tous cas, onconstate sur cet exemple que la primalite est plus facile que la factorisation !On notera qu’a l’heure actuelle on ne sait pas exactement lesquels parmiles Fn sont premiers ou non. La reponse est seulement connue pour un nombreni de net, sauf pour les 5 premiers, tous les Fn en question sont composes.Cet exemple montre deja deux choses, d’abord qu’un grand mathematicienpeut dire des b^etises, et ensuite qu’il y a des questions, somme toute assezsimples, pour lesquelles on n’a pas de reponse. J’y reviens plus loin. Il y a donc des records du plus grand nombre premier connu qui sontdetenus par d’enormes ordinateurs 14(en general il s’agit de certains nombresde Mersenne (1588-1648) : Mn= 2 n 1). Le plus ancien record est celui deCataldi en 1588 avec M19 = 524287. Il y eut ensuite Lucas (1876) avecM127qui a 39 chires. Le record, en 1999, etait le nombre de Mersenne M6972593 quia tout de m^eme plus de 2 millions de chires ! Je ne vais pas l’ecrire 15, maisje peux tout de m^eme dire qu’il commence par 437075 et nit par 193791. Jevous laisse montrer cela a titre d’exercice (pas si facile, voir Annexe 2).En 2008, le record est M43112609 qui a 12 millions de chires.3.6 Factoriser des grands nombres ? Ce qu’il faut comprendre, c’est que les ordres de grandeur des nombrespremiers que l’on sait exhiber, d’une part, et des nombres que l’on sait fac-toriser, d’autre part, ne sont pas du tout les m^emes, comme on l’a deja sentia propos des nombres de Fermat. Pendant longtemps, factoriser un nombrede l’ordre d’un milliard etait considere comme a peu pres impossible. AinsiMersenne, en 1643, avait donne a Fermat, comme un de, de factoriser le 13. J’ai laisse tourner la machine toute une nuit sans succes. Il faut noter qu’il y a justeun an, xcasmettait 2 heures 7 minutes et 40 secondes pour factoriser 2 128+ 1 : on voit lesprogres des machines et des algorithmes ! 14. Ce n’est pas seulement la puissance des ordinateurs qui est en jeu, mais surtout laqualite des algorithmes qu’ils utilisent (donc des mathematiques qui sont derriere).15. Il y faudrait un livre de 500 pages !10