Question 11: Maths, le retour.

 1 - factorisation

   42 = 2*3*7
   10199 = 7*31*47
   319933 = 463*691
   406901494 = 2*17*29*563*733
   4705347917 = 47279*99523
   753942687551 = 753942687551
   15173550175166 = 2*487*57859*269251
   255817035245483909 = 5479921319*46682611
   52893458254464113697469 = 885805483831*59712272299
   4911069111545487265760898482887 = 992433563618671*4948511710585897

   Pour factoriser ses nombres, la methode la plus simple etait de tester si ils etait divisibles par 2 et tous les impairs compris entre 3 et sqrt(n). On pouvait optimiser encore plus en ne testant que les nombres comgrus a 1 et 5 modulo 6. 
  Pour les 2 derniers nombres, il falait utiliser un autre algorithme ( crible algebrique ou crible quadratique ), ou bien disposer d'une tres grosse machine.

 2 - Le message crypte

 Le R.S.A. n'est pas un virus. C'est un systeme de cryptage a clef publique. Cela veux dire que l'encodage peut etre fait avec des information en moins que lors du decodage. Il est donc possible de diffuser une cle qui permettra a tout le monde de coder un message, mais seul le destinateur du message pourra le decoder. C'est sur cette methode qu'est basse le PGP.

 Ce systeme est basse sur la theorie des nombres, qu'il nous serra difficile d'expliquer ici. Mais la pratique est plus simple. 
 On prend 2 grands nombres premiers p et q. On note n leurs produits.
  
 n=p*q
 
 On prend ensuite un grand nombre d premier avec (p-1)*(q-1) et on calcul e, a l'aide de l'algorithme etendu d'euclide, l'inverse de e modulo (p-1)*(q-1)
 
 e*d=1 mod (p-1)*(q-1)
 
 d et n represente la clef publique, et e et n represente la clef privee.
 
 Pour chiffrer un message m, il faut le diviser en blocs numeriques
 m(i) plus petits que n. Ensuite, le message chiffre c est obtenu de la
 facon suivante :

 c(i)=m(i)^d mod n

 Pour decrypter le message, on procede de la facon suivante:

 m(i)=c(i)^e mod n

 La difficulte est de pouvoir travailler sur des nombres grands. 
 
Le programme ( fonctionnant sous linux )