Cryptographie!

Le théorème des restes chinois

Théorème : Prenons m1, ..., mn des entiers supérieurs à 2 deux à deux premiers entre eux, et a1,...,an des entiers. Le système d'équations : $$\left\{ \begin{array}{rcl} x&=&a_1\mod m_1\\ x&=&a_1\mod m_1\\ \vdots&\vdots&\vdots\\ x&=&a_n\mod m_n \end{array}\right. $$ admet une unique solution modulo $M=m_1\times\dots\times m_n$ qui est donnée par la formule : $$x=a_1M_1y_1+\dots+a_nM_ny_n$$ où $M_i=\frac{M}{m_i}$ et $y_i=M_i^{-1}\mod m_i$ pour tout $i$ compris entre 1 et n.

Exemple : Une bande de 17 pirates s'est emparée d'un butin composé de pièces d'or d'égale valeur. Ils décident de se les partager également, et de donner le reste au cuisinier chinois. Celui-ci recevrait alors 3 pièces. Mais les pirates se querellent, et six d'entre eux sont tués. Le cuisinier recevrait alors 4 pièces. Dans un naufrage ultérieur, seuls le butin, six pirates et le cuisinier sont sauvés, et le partage donnerait alors 5 pièces d'or à ce dernier. Quelle est la fortune minimale que peut espérer le cuisinier quand il décide d'empoisonner le reste des pirates?


Si x est ce nombre, x est le plus petit entier positif tel que :
  • x=3 mod 17.
  • x=4 mod 11.
  • x=5 mod 6.
On applique le théorème chinois : on a M=17×11×6=1122, M1=66, M2=102, M3=187. L'inversion de chaque Mi (par l'algorithme d'Euclide) donne y1=8, y2=4, y3=1.

On obtient donc :
x=3×66×8+4×102×4+5×187×1 mod 1122 = 785 mod 1122.

785 pièces d'or, voila qui reste particulièrement motivant!
Consulter aussi