Le théorème des restes chinois

Résumé du document

Par son histoire et sa religion, la Chine a toujours mis l'accent sur l'astronomie. Ainsi, dans le but de prévoir des dates ou événements astronomiques, les astronomes chinois ont découverts le théorème des restes chinois. D'après certains textes, on peut évaluer l'apparition du théorème au 3ème siècle.

Le théorème a évolué au cours du temps sous diverses formes et avec l'apparition de nouveaux dérivés du théorème initial.

Ce théorème, permettant de calculer des systèmes de congruences, peut servir à la résolution de petits problèmes courants mais est également appliqué à des projets de plus grande envergure.

Aujourd'hui, le théorème des restes chinois a pris beaucoup d'importance dans la cryptographie. En effet, sans le savoir, ce sont des millions de personnes qui l'utilise chaque jour. Certains modes de paiement sécurisé, par exemple, font appel au système de cryptage RSA qui utilise le théorème des restes chinois (...)

Extraits

[...] Néanmoins pour obtenir un déchiffrement efficace on utilise le théorème des restes chinois. En général, nous avons : mod ( mod p ) ( y mod p ) mod ( mod q ) ( y mod q ) Supposons qu'on nous envoie un texte encrypté C et que nous voulons calculer efficacement : M = Cd ( mod n ) Posons y = Cd et x = M = y ( mod n on a alors : a Cd ( mod p ) b Cd ( mod q ) M a ( mod p ) M b ( mod q ) Soient r Є ℤ/(p-1)ℤ d r ( mod p-1 ) et s Є ℤ/(q-1)ℤ d s ( mod Ainsi Ǝ Є ℤ² d = + r = + s Donc on a : a C ( + r ) ( mod p ) b C ( + s ) ( mod q ) D'après le théorème de Fermat / Euler on a : Є ℕxℙ ap a (mod Supposons que pgcd pgcd(a,p)=1 donc d'après le théorème de Bezout Ǝ a-1Є ℤ a.a-1≡1 (mod Donc Є ℕxℙ avec pgcd(a,p) = 1 1 (mod Donc si pgcd(C,n) = pgcd(C,p) = pgcd(P,q) = 1 on a : a . [...]

[...] Dans la conception du monde, le pôle symbolise le souvertain autour duquel la société est organisé et l'étoile polaire est nommée le grand empereur céleste ou le pivot céleste. La première tache d'un nouveau souverain est de promulguer un calendrier et de ce fait, il y a toujours eu de nombreux astrologues et astronomes attachés au service du gouvernement. Entre le IVème siècle avant J.C et la fin de la dynastie mandchoue en 1911, on compte plusieurs centaines de calendriers. Il faut organiser le calendrier et prédire de manière aussi précise que possible les événements astronomiques en liaison avec les succès du gouvernement. [...]

[...] + an.Mn.en vérifie donc : i Є x0 ai x solution de i Є x-x0 0 x-x0 0 [ ppcm(m1, ] Comme ppcm(m1, = m1 x . x mn, l'ensemble des solutions de est : { x0 + m1 x m2 x . x mn x k Є ℤ } Exemples d'applications Exemple simple Problème : Déterminer tous les entiers x dans ℤ qui vérifient : x 2 (mod 15) et x 8 (mod 28) Résolution : x 2 x 8 15= 3.5 et 28=2².7 pgcd(15,28)= divise a1-a2=-6 Donc admet des solutions. [...]

[...] Les nombres n et e forment ici notre clé publique que l'on notera Il nous faut calculer le nombre d qui sera nécessaire au décryptage. Selon la théorie de RSA, nous devons avoir d e.d mod m ) c'est a dire qu'on cherche un couple Є ℕ² e.d + k.m = 1. Comme e et m sont premiers entre eux, le théorème de Bezout prouve qu'il existe d et k dans ℤ tel que e.d+k.m=1 On pourra résoudre l'équation grâce à l'algorithme d'Euclide. [...]

[...] Math. Mag Jones, Phillip S. From Ancient China 'til Today!. [...]