Rappel :

   A modulo M  ( A % M) est le reste de la division de A par M 
  ce reste est fatalement entre 0 et M-1

   A est donc la Forme  A = (A % M) + K * M   (entiers)
  Donc (A + B) % M  = ((A % M) + ( B % M))  % M  + 0 = (A % M ) + ( B % M )
  Donc (A * B) % M  = ((A % M) * ( B % M))  % M  + 0 = (A % M ) * ( B % M )
  Donc ( A % (P1 * P2) ) % P1  = A % P1
          soit A % M % M % M = A % M

   On vois que le % M a tendance a ce retouver un peut partous
  il passe de interieur d'une expresion vers exterieurs et reciproquement
  par associativite, distributivite, nilpotance ....
  et donc on est tente d'ecrire :

    ((A^e)*(A^d))%M  =   (A ^(e + d)) % M

    ((A^e)%M)^d) %M  =   (A ^(e * d)) % M

   En calculant des puissances sucessives de X modulo M on s'attend 
  a retouver le meme reste au plus toutes les M-1 operations
  ou meme avant (puisque le nombre de restes est finis ) :

...

   ISOMORPHISMES

     Ethimologiquement cela caracterise 
    des trucs qui on a peut pret la "meme geule" d'une representation a l'autre
    ou dans lequel on retrouve des invarianst plus ou moins caracteristiques 

 On vas s'interesser au puissance sucessives de X (le nombre a coder ) :

  X1   X2   X3   X4    X5     X6     X7      X8       X9       X10        X11

   0    0    0    0     0      0      0       0        0         0          0
   1    1    1    1     1      1      1       1        1         1          1
   2    4    8   16    32     64    128     256      512      1024       2048
   3    9   27   81   243    729   2187    6561    19683     59049     177147
   4   16   64  256  1024   4096  16384   65536   262144   1048576    4194304
   5   25  125  625  3125  15625  78125  390625  1953125   9765625   48828125
   6   36  216 1296  7776  46656 279936 1679616 10077696  60466176  362797056
   7   49  343 2401 16807 117649 823543 5764801 40353607 282475249 1977326743


  Ensuite on considere ces memes nombres
 dans divers systemes de representations de type modulo 2 3 4 5 ...

  Cette suite images numeriques est un peut etre un peut longue
 mais c'est pour ce rendre compte qu'il y a des criteres numerique
 qui fait que l'image est partfois un peut transparente
 et que l'on arrive parfois a devine la geule du X qui y est code 


---

soit les memes valeurs lues en modulo 2 (M=2) (phi = 1)
   les colonnes veticales sont identiques : se repetent par groupe de 1
      les lignes horizontales se repetent par groupe de 2
          une ligne sur 2 est nulle (x multiples de 2)

  X1   X2   X3   X4    X5     X6     X7      X8       X9       X10        X11

0  0    0    0    0     0      0      0       0        0         0          0
1  1    1    1    1     1      1      1       1        1         1          1
2  0    0    0    0     0      0      0       0        0         0          0
3  1    1    1    1     1      1      1       1        1         1          1
4  0    0    0    0     0      0      0       0        0         0          0
5  1    1    1    1     1      1      1       1        1         1          1
6  0    0    0    0     0      0      0       0        0         0          0
7  1    1    1    1     1      1      1       1        1         1          1

---

soit les memes valeurs lues en modulo 3  (M=3)  (phi = 2)
    les colonnes verticales se repetent par groupe de 2
       les lignes horizontales se repetent par groupe de 3
          une ligne sur 3 est nulle (x multiples de 3)
          une ligne sur 3 est a 1

  X1   X2   X3   X4    X5     X6     X7      X8       X9       X10        X11

0  0    0    0    0     0      0      0       0        0         0          0
1  1    1    1    1     1      1      1       1        1         1          1
2  2    1    2    1     2      1      2       1        2         1          2
3  0    0    0    0     0      0      0       0        0         0          0
4  1    1    1    1     1      1      1       1        1         1          1
5  2    1    2    1     2      1      2       1        2         1          2
6  0    0    0    0     0      0      0       0        0         0          0
7  1    1    1    1     1      1      1       1        1         1          1

---

soit les memes valeurs lues en modulo 4 = 2 * 2 ( M=4) (phi = 2)
    les colonnes verticales se repetent par groupe de 2
      les lignes horizontales se repetent par groupe de 4
        une ligne sur 4 est nulle (x multiples de 4)
          une ligne sur 4 est a 1

              la ligne 2 est incodable presque nulle

  X1   X2   X3   X4    X5     X6     X7      X8       X9       X10        X11

0  0    0    0    0     0      0      0       0        0         0          0
1  1    1    1    1     1      1      1       1        1         1          1
2  2    0    0    0     0      0      0       0        0         0          0
3  3    1    3    1     3      1      3       1        3         1          3
4  0    0    0    0     0      0      0       0        0         0          0
5  1    1    1    1     1      1      1       1        1         1          1
6  2    0    0    0     0      0      0       0        0         0          0
7  3    1    3    1     3      1      3       1        3         1          3

---

soit les memes valeurs lues en modulo 5  ( M=5) (phi = 4 = 2 * 2)
    les colonnes verticales se repetent par groupe de 4
        ceraines lignes verticale ( ex  4) sont egale a 1  toutes les 2 colonnes
       les lignes horizontales se repetent par groupe de 5
          une ligne sur 5 est nulle (x multiples de 5)
          une ligne sur 5 est a 1

  X1   X2   X3   X4    X5     X6     X7      X8       X9       X10        X11

0  0    0    0    0     0      0      0       0        0         0          0
1  1    1    1    1     1      1      1       1        1         1          1
2  2    4    3    1     2      4      3       1        2         4          3
3  3    4    2    1     3      4      2       1        3         4          2
4  4    1    4    1     4      1      4       1        4         1          4
5  0    0    0    0     0      0      0       0        0         0          0
6  1    1    1    1     1      1      1       1        1         1          1
7  2    4    3    1     2      4      3       1        2         4          3



---

soit les memes valeurs lues en modulo 6 = 2 * 3    (phi = 2)
    les colonnes verticales se repetent par groupe de 2
    les colonnes verticales sont egale  a 1 par multiples de 2 
      les lignes horizontales se repetent par groupe de 6
          une ligne sur 6 est nulle 
          une ligne sur 6 est a 1
          une ligne sur 6 est a 3
          une ligne sur 6 est a 4

          les lignes 2 4 et 3  manquent de diversitee

  X1   X2   X3   X4    X5     X6     X7      X8       X9       X10        X11

0  0    0    0    0     0      0      0       0        0         0          0
1  1    1    1    1     1      1      1       1        1         1          1
2  2    4    2    4     2      4      2       4        2         4          2
3  3    3    3    3     3      3      3       3        3         3          3
4  4    4    4    4     4      4      4       4        4         4          4
5  5    1    5    1     5      1      5       1        5         1          5
6  0    0    0    0     0      0      0       0        0         0          0
7  1    1    1    1     1      1      1       1        1         1          1

---

soit les memes valeurs lues en modulo 7    (phi = 6 = 2 * 3)
    les colonnes verticales se repetent par groupe de 6
     mais sont parfoix egale a 1 par multiples de 3 ou 2
      les lignes horizontales se repetent par groupe de 7
          une ligne sur 7 est nulle (x multiples de 7)
          une ligne sur 7 est a 1

  X1   X2   X3   X4    X5     X6     X7      X8       X9       X10        X11

0  0    0    0    0     0      0      0       0        0         0          0
1  1    1    1    1     1      1      1       1        1         1          1
2  2    4    1    2     4      1      2       4        1         2          4
3  3    2    6    4     5      1      3       2        6         4          5
4  4    2    1    4     2      1      4       2        1         4          2
5  5    4    6    2     3      1      5       4        6         2          3
6  6    1    6    1     6      1      6       1        6         1          6
7  0    0    0    0     0      0      0       0        0         0          0

  On constante ici que la deuxieme moitie des lignes ce deduit des premieres

   en effet 6 % 7 c'est aussi -1 % 7
  donc 6 quand on le multilis par lui meme donne une suite de 6 1 6 1 6 1
  c'est a dire -1 +1 -1 +1 -1 +1 ....

   de meme pour 5  qui est auusi -2 % 7
  donc pour ecrire la ligne 5 il suffit de recopier la 2
  en rajoutant un signe moins (le complement a 7)
  sur toutes les puissances impaires :

   4 c'est aussi -3 % 7 ....

   de plus la ligne 4 ce deduit de la 2 en sautant un element sur deux

   la ligne 6 est aussi  le produit des termes de lignes  2 et 3 ( %7)

    Bref : il ne reste environ que la motie des lignes premieres !!!

   et on constante que tous les (X^6)%7 sont egal a 1 (element neutre)


---

soit les memes valeurs lues en modulo 9 = 3 * 3
                             (phi = 6 = 2 * 3 ) !=  phi(3) * phi(3) = 2 * 2

    les colonnes verticales se repetent par groupe de 6  ( pas de 3 ou 9 ou  2)
                              (si on exclus les x multiples de 3)
     les lignes horizontales se repetent par groupe de 9
          une ligne sur 3 est nulle

  X1   X2   X3   X4    X5     X6     X7      X8       X9       X10        X11

0  0    0    0    0     0      0      0       0        0         0          0
1  1    1    1    1     1      1      1       1        1         1          1
2  2    4    8    7     5      1      2       4        8         7          5
3  3    0    0    0     0      0      0       0        0         0          0
4  4    7    1    4     7      1      4       7        1         4          7
5  5    7    8    4     2      1      5       7        8         4          2
6  6    0    0    0     0      0      0       0        0         0          0
7  7    4    1    7     4      1      7       4        1         7          4
8  8    1    8    1     8      1      8       1        8         1          8
9  0    0    0    0     0      0      0       0        0         0          0


---

soit les memes valeurs lues en modulo 15 = 3 * 5  (phi = 8 = 2 * 2 * 2)

   les colonnes verticales se repetent par groupe de 8 ( 4 ?)
      mais sont parfopis egale a 1 par multpiles de 2
     les lignes horizontales se repetent par groupe de 15

          une ligne sur 15 est nulle (x multiples de 15)
          une ligne sur 15 est a 1


   X1   X2   X3   X4    X5     X6     X7      X8       X9       X10        X11

 0  0    0    0    0     0      0      0       0        0         0          0
 1  1    1    1    1     1      1      1       1        1         1          1
 2  2    4    8    1     2      4      8       1        2         4          8
 3  3    9   12    6     3      9     12       6        3         9         12
 4  4    1    4    1     4      1      4       1        4         1          4
 5  5   10    5   10     5     10      5      10        5        10          5
 6  6    6    6    6     6      6      6       6        6         6          6
 7  7    4   13    1     7      4     13       1        7         4         13
 8  8    4    2    1     8      4      2       1        8         4          2
 9  9    6    9    6     9      6      9       6        9         6          9
10 10   10   10   10    10     10     10      10       10        10         10
11 11    1   11    1    11      1     11       1       11         1         11
12 12    9    3    6    12      9      3       6       12         9          3

  la aussi on vois que les lignes  1 et 4 
            sont liees en complement a 5 et alternees
  de meme les lignes 7 et  8 sont liees en complement a 15 et alternees
          les lignes 6 et  9 sont liees en complement a 15 et alternees
          les lignes 5 et 10 sont liees en complement a 15 et alternees
          les lignes 4 et 11 sont liees en complement a 15 et alternees
          les lignes 3 et 12 sont liees en complement a 15 et alternees ...

---

soit les memes valeurs lues en modulo 35 = 7 * 5  (phi = 24 = 2 * 2 * 2 * 3)

   X1   X2   X3   X4    X5     X6     X7      X8       X9       X10        X11

 0  0    0    0    0     0      0      0       0        0         0          0
 1  1    1    1    1     1      1      1       1        1         1          1
 2  2    4    8    16   32     29     23      11       22         9         18
 3  3    9   27    11   33     29     17      16       13         4         12
 4  4   16   29    11    9      1      4      16       29        11          9
 5  5   25   20    30   10     15      5      25       20        30         10
 6  6    1    6     1    6      1      6       1        6         1          6
 7  7   14   28    21    7     14     28      21        7        14         28

   la ligne 6 ce deduit de la 3 et de la 2 !
   Comme tous X peut etre decompose en facteur premier
 on peut se contempter de garder que les lignes
 correspondant a des nombre premier 1 2 3 5 7 11
  la multiplication etant associative on peut reconstituer
 les autres lignes .

---

synthese 

  X1   X2   X3   X4    X5     X6     X7      X8       X9       X10        X11

   0    0    0    0     0      0      0       0        0         0          0

   1    1    1    1     1      1      1       1        1         1          1

   2    4    8   16    32     64    128     256      512      1024       2048
%2 0    0    0    0     0      0      0       0        0         0          0
%3 2    1    2    1     2      1      2       1        2         1          2
%4 2    0    0    0     0      0      0       0        0         0          0
%5 2    4    3    1     2      4      3       1        2         4          3
%6 2    4    2    4     2      4      2       4        2         4          2
%7 2    4    1    2     4      1      2       4        1         2          4

   3    9   27   81   243    729   2187    6561    19683     59049     177147
%2 1    1    1    1     1      1      1       1        1         1          1
%3 0    0    0    0     0      0      0       0        0         0          0
%4 3    1    3    1     3      1      3       1        3         1          3
%5 3    4    2    1     3      4      2       1        3         4          2
%6 3    3    3    3     3      3      3       3        3         3          3
%7 3    2    6    4     5      1      3       2        6         4          5

   4   16   64  256  1024   4096  16384   65536   262144   1048576    4194304
%2 0    0    0    0     0      0      0       0        0         0          0
%3 1    1    1    1     1      1      1       1        1         1          1
%4 0    0    0    0     0      0      0       0        0         0          0
%5 4    1    4    1     4      1      4       1        4         1          4
%6 4    4    4    4     4      4      4       4        4         4          4
%7 4    2    1    4     2      1      4       2        1         4          2

   5   25  125  625  3125  15625  78125  390625  1953125   9765625   48828125
%2 1    1    1    1     1      1      1       1        1         1          1
%3 2    1    2    1     2      1      2       1        2         1          2
%4 1    1    1    1     1      1      1       1        1         1          1
%5 0    0    0    0     0      0      0       0        0         0          0
%6 5    1    5    1     5      1      5       1        5         1          5
%7 5    4    6    2     3      1      5       4        6         2          3

   6   36  216 1296  7776  46656 279936 1679616 10077696  60466176   36279056
%2 0    0    0    0     0      0      0       0        0         0          0
%3 0    0    0    0     0      0      0       0        0         0          0
%4 2    0    0    0     0      0      0       0        0         0          0
%5 1    1    1    1     1      1      1       1        1         1          1
%6 0    0    0    0     0      0      0       0        0         0          0
%7 6    1    6    1     6      1      6       1        6         1          6

   7   49  343 2401 16807 117649 823543 5764801 40353607 282475249 1977326743
%2 1    1    1    1     1      1      1       1        1         1          1
%3 1    1    1    1     1      1      1       1        1         1          1
%4 3    1    3    1     3      1      3       1        3         1          3
%5 2    4    3    1     2      4      3       1        2         4          3
%6 1    1    1    1     1      1      1       1        1         1          1
%7 0    0    0    0     0      0      0       0        0         0          0


   Rq : Quand le modulo choisi est composite (non premier)
       on constate des tables de codage moins diversifiees !!!

        Et indicateur Euler PHI semble interresant !

   Rq :  En utilisant le theoreme des restes chinois on fini par decouvrir X !!!




 DEFINITIONS 

 * NOMBRES PREMIERS ENTRE EUX  (relativ prim) :

  deux nombres sont premiers entre eux si n'on aucun diviseur commun 
  (autre que 1)
   ex :
       5 et 6 sont premier entre eux !
       ( leurs plus petit commun multiple PPCM est egal a leur produit 30)
       ( leurs plus grand commun diviseur PGCD est 1)

       10 et 6 ne sont pas premier entre eux
           on peut les diviser chaqun par 2
           ( leurs plus grand commun diviseur PGCD est 2)
             et leur PPCM est 30 (est pas 60)
             ( 10 * 6 = pgcd *ppcm )

   Un nombre premier en absolu
  ne peut pas se decomposer en produit de plusieurs nombres
  ( il est donc premier relatif avec tous les autres )

   un nombre en general est le produit (la factorisation)
  de un ou plusieurs nombres premiers
    par exemple   9 est egal a   3 * 3 
    par exemple  63 est egal a   3 * 3 * 7


   on a en general
  A * B = PGCD(A,B) * PPCM(A,B)


     DIRE QUE DEUX NOMBRES SONT PREMIER ENTRE EUX
    EST EQUIVALENT A DIRE QUE LEUR PGCD EST 1 


 * POLYNOME DE NEWTON, TRIANGLE DE PASCAL, COMBINAISONS

   Polynome de Newton (A+B)^P

     (A+B)^2 = A^2  + 2 * A   * B  +  B^2
     (A+B)^3 = A^3  + 3 * A^2 * B  + 3 * A   * B^2   + B^3
     (A+B)^4 = A^4  + 4 * A^3 * B  + 6 * A^2 * B^2   + 4 * A^3 * B  + B^4  


      les coefficiant entiers des termes multpilicatif sont C(N,P) :
     Donnes dans le triangle de Pascal :

     C(N,P)    0   1    2    3    4    5    6    7    8    9   10   N

         0     1
      -  1     1   1
         2     1   2    1
      -  3     1   3    3    1
         4     1   4    6    4    1
      -  5     1   5   10   10    5    1
         6     1   6   15   20   15    6    1
      -  7     1   7   21   35   35   21    7    1
         8     1   8   28   56   70   56   28    8    1
         9     1   9   36   84  126  126   84   36    9    1
        10     1  10   45  120  210  252  210  120   45   10    1
      - 11     1  11   55  165  330  462  462  330  165   55   11    1
        12     1  12   66  220  495  792  924  792  495  220   66   12    1
      - 13     1  13   78  286  715 1287 1716 1716 1287  715  286   78   13    1

         P                                           N inf ou egal a P


            RQ  lignes avec un P premiers
           1, 3,  5, 7, 11 ...
           ne contiennent que des multipes de P 
            ou des 1 ( au deux extremitees )
 
              Si le nombre est nom premier, comme par exemple 6 = 2 * 3 
             on a des coef egaux a 1 , et des multiples de 3 , de 5 , de 4 ...

            ON reporte la demonstration juste apres,
           la definition et le calcul des combinaisons .

   Combinaisons :

        Comment choisir 2 fois A dans (A+B)(A+B)(A+B)(A+B)
       je peut choisir le premier A dans un des 4 termes 
       le deuxieme A dans les 3 termes restant  soit 4*3 arragement;
       ( ensuite  je choisi 2 foix B )
           A * A * B * B
           A * B * A * B
           A * B * B * A

           B * A * A * B
           B * A * B * A
           A * A * B * B  !

           B * B * A * A
           A * B * A * B  !
           B * A * A * B  !

           A * B * B * A  !
           B * A * B * A  !
           B * B * A * A  !

        Mais peut importe l'ordre que le premier A soit dans le 1 terme
       et le deuxieme soit dans  le 3 eme terme
       ou que le premier soit le 3 eme et les segond dans le premier ;
        C'est pareil
       on va tous diviser par 2 

       C(2,4)  =  4*3 / 2  = 6

       C(N,P)  comment choisir N elements dans une liste de P elements
                sans tenire compte de l'ordre :

       C(N,P) =  P * (P-1) * (P-2 ) ...  /  P * (P-1)  * (P-2) ...

           soit en utilsant le symbole ! factorielle :
               C(N,P) =  P !  / ( (P-N) ! *  N ! )

        on retrouve tous les coefficiant du triangle de Pascal
                                            dans le polynome de Newton :

         symetrie :
           C(P-N,P) = C(N,P) ; (choisir N terme c'est comme en elliminer P-N )

         extrmitees :
           C(0,P) = 1    C(M,P) = 1; 

         calculs :
           C(N+1,P+1) =  C(N,P) + C(N,P+1) 
             Dans le triangle de Pascal un nombre est la somme des deux nombres
            qui le precede et du meme rang, sur la ligne precedante !

        et on peut ecrire le polynome

         (A+B)^P =   C(0,P)         * B^P
                   + C(1,P)  * A^1  * B^(P-1)
                   + C(2,P)  * A^2  * B^(P-2)
                   + C(3,P)  * A^3  * B^(P-3)
                   +  ....
                   + C(P,P)  * A^P


 * INDICATEUR EULER ( ex pour N = 63 = 3 * 3 * 7) 

    Combien un Nombre N a il de nombre inferieur ou egal a lui meme ( ici 63)
   et premier avec lui (PGCD 1) ?
    A priori,  pas plus de N ( ici 63 )(en comptant aussi 1 et 63 ) !
   mais on doit enlever tous les mutiples de 3 : 3  6  9
    donc il en reste 2/3 de 63
   idem pour les multiples de 7
     il en reste donc 6/7 ...
    soit donc 63 * 2/3  * 6/7 =  3 * 3 * 7 * 2/3  * 6/7 =  3 * 2 * 6  =  36
    PHI(63)=36

    Ce nombre est indicateur Euler PHI utilise precedament qui denombre
   l'ensemble des nombres I non elimines, qui  verifis donc  pgcd(I,63) =  1
   (il reste : 1 2 4 5 8 10 11 13 16 17 19 20 ..... 62.)
    On connais donc leur nombre sans les connaitres individuellement !

    Dans le cas general Pour N= p1^A * p2^B  * p3^C  ....
      ( p1 p2 p3 etant les nombres premiers de factorisation de N )
      on trouve  PHI(N)  = N * (1 - 1/p1)  * (1 - 1/p2) * (1 - 1/p3)  ....

    Dans le cas ou N est le produit de
      Deux nombres premiers differents p1 et p2
       PHI(n=p1*p2) = (p1-1) * (p2-1)
         ( par definition PHI(1) = 1)

 * Ordre_multiplicatif_M( A ) : C'est le plus petit entier K
     tel que (A^K) %M  = 1  ( pour A non null )
     on a vus precedament que ce nombre ne peut pas depasser M-1
     du fait que les restes d'une division modulo M sont limite a M-1

 * associativite  commutativite des operateur %

      A priory X ^P  % M = ( X % M) ^ P % M = .

        et on peut faire la calcul dans ordre que l'on veut
       et parfois la notation %m (deviends sous entendu ou optionnelle)

        certain mathematicien utilise de preferance operateur d'egalite modulo
       note par trois trait horizontal  (non disponible en ASCII de base ) !

        exemple  5 "est egal a" 11 (en modulo 3 )

         puisque ils sont egaux leur differance  11 - 5  =  6  est donc nulle !
           (ce qui est vrai : 6 en modulo 3 est bien nul )

        Bref on doit faire tres attention de quoi on parle
       pour ce debaraser de ces anbiguites et eviter la notation modulo
       on peut transformerr la notation A % M = H  en   A = H + K * M 
       avec des entier relatif

        Mais il y des contraintes ou des simplifications
       si pendant les calculs on tombe sur
         le 0 zero ou le  1 (l'ellement neutre de la multiplication)
        on peut trouver le resultat tres(trop) rapidement ! .....


 THEOREME FERMAT

   si X==0   alors X^?  est null 

   si X est non nul et pour peut que M soit premier  :
   alors on a :

    X^M % M   =  X % M  ( en fait il sagit de egalite modulo M )

     * SOIT LA FORME GENERALE SUIVANTE DU THEOREME DE FERMAT
        =====================================
          X^M - X =  K * M    QQ SOIT X 
            POUR PEUT QUE M SOIT PREMIER !
        =====================================

          ( RQ on peut demontre le petit th de Fermat
               par recurance X X+1 .....
                avec le developpemnt du polynome de newton (X+1)^M
                 donc les coefficiant, 
                  qui sont dans le triangle de Pascal CiM,
                   sont tous des multiples de M 
                    (sauf le premier et le dernier qui sont egaux a 1 :

           -----

              C(N,M) est un nombre entier de conbinaisons,
             c'est  la maniere  de choisir N (facteur X) 
            dans les M termes du polynome 
                (X+1) (X+1) (X+1) ...
              on a la choix entre X ou 1 a chaqun des  M termes
              ( N inferieur ou egal a M)

               C(3,M)   =  M * (M-1)  * (M-3)  /  1 * 2 * 3 
                   ( le nombre de combinaison non ordonees 
                              = arrangement / permutatations )

               C(i,M)    = M!  /  (M-i)!   /  i!

                   le nombre M ce trouve au numerateur
                  et pas au diviseur !!!!!!!!!!!!!!

                           ( sauf C(0,M) et C(M,M) qui sont egaux a 1)
                     C(3,7)  = 7 * 6 * 5 / 1 * 2 * 3 = 5 * 7

                   Si M est premier il n'a pas de diviseur au denominateur
                  (ni ailleurs de par definition)
                   Dans ce cas la C(i,M) est  :
                          soit  1 soit un multiple de M ,
                                  car c'est un entier et que M est premier

                Donc    si X^M % M  = X  (X inferieur a M)

                  supposont que  X^M - X = K * M
                   alors 
                    ((X+1)^M       = X^M  + M * (....    )  + 1
                       on remplace X^M  par ca valeur pecedante X + K * M
                     on a (X+1)^M  =  1 +  X  + K * M  +  M * (....    )
                     avec Y = X+1 
                       on a la memem forme  Y^M  =  Y +  Z * M

                Donc si la relation est vrai pour X=1
                   elle est vrai aussi pour tous X+1 

                Pour X=1 c'est vrai ( 1 % M = 1 )
                 donc ....c'est vrai quel que soit X !
                  pour M premier

             On demontre bien alors que
           X^M - X =  K * M  qq soit X
           pour peut que M soit premier  ! 

                Pour faire la demonstrations
                par recursion du theoreme de Pascal :
                M doit etre premier !                 )

               Plusieur autre demonstrations par recurance peuvent etre abordees
              par cette methode .... 


           -----

      *  RQ : si M est premier alors on a  PHI(M)  = M - 1


      *  On peut vouloir etendre et generaliser ce theoreme
            a un nombre non premier !
              par exemple  produit de
              deux nombres premiers  M = P1 * P2  (differants) :

                 -----

                On se rends compte que approche methodologique precedante 
               ne marche pas, car il y a des C(i,M)
               qui ne sont pas multiples de M (ou egal 1)
                Pour peut que i soit  un multiple  uniquement d'un seul
               des composants P1 ou de P2 et pas de l'autre 
                Car ils vont etre divises par un des termes P1 ou P2  ;
               mais pas par l'autre (puisque  P1 et P2 sont differants)

               (ces termes ne sont plus egaux a 0 en modulo M)
               (evidament C(0,M) et C(M,M) reste egal a 1)

                  un exemple avec  M = 3 * 5  :

                   C(3,15) =  15 * 14 * 13 / 3 * 2 *1 
                           =  455 = 30 * 15 + 5 ; 
                              C(3,15) % 15 =  5
                   C(12,15)=  5

                   C(6,15) =  15 * 14 * 13 * 12 * 11 * 10 / 6 * 5 * 4* 3 *2 
                           =  5005 = 333 * 15 + 10 ;
                              C(6,15) % 15 = 10
                   C(9,15) =  10

                   C(5,15) =  15! / 10!  / 5!  = 3003 = 200 * 15 + 3;
                              C(5,15) % 15 =  3
                   C(10,15)=  3

                         ? ? ?

                 on doit changer de methode :

                 ----

            VARIANTE TH FERMAT

               On peut ecrire le Th de Fermat sous une autre forme
              pour essayer de resoudre le probleme
              ( par un petit coup de marche arriere )
              (en divisent tous par X ( c'est la division % M ))
              (X^(m-1)) % M  = 1  ( si x est NON NULL % M !!!) 

                  Cette variante du TH de Fermat est moins generale
                 car pour diviser par X il est necessaire 
                 que X%M soit different de zero
                 soit PGCD(X,M) == 1

                 X^(M-1)  =   1  +  Q * M  
                 si   PGCD(X,M) == 1 ( X et M premiers enter eux )
                 X^(M-1) % M == 1

                   RQ si X= K*P1  ou  X=L*P2  cela ne marche pas !!!!

                  =========================================================

                   RQ si M est premier alors PHI(M) = M-1 
                     alors le th. precedant  prends la forme 
                        X^PHI(M) % M  = 1
                        si PGCD(X,M) == 1 ( X et M premiers enter eux )! 
                  =========================================================


               Mais cette forme du theoreme a l'avantage de se generaliser dans
              le cas ou M est le produit de deux nombres premiers differents
              P1 et P2
               sous la forme   (X^((P1 - 1) * (P2 - 1)) = 1 + S * (P1 * P2)

                 ----

                  Il suffit de develloper le calcul
                        S = X^((P1-1)*(P2-1)

                           =  (X^(P1-1))^(P2-1)  = (X^(P2-1))^(P1-1)
                 en utilisant deux fois le theoreme precedant de Pascal, 
                  que l'on peut toujours utiliser
                    vus que P1 est suppose etre premier 
                    vus que P2 est suppose etre premier 
                            X^P1 = X + K * P1    
                           X^P2 = X + L * P2    
                      si X % P1 != 0 et X % P2 != 0 
                           (pour eviter des multiplication par zero)
                    alors 
                       X^(P1-1) est de la forme 
                                  1+ K/X * P1 = un entier non nul = 1 + V * P1
                       X^(P2-1) est de la forme
                                  1+ L/X * P2 = un entier non nul = 1 + W * P2
                    donc 
                      S = (X^(P1-1)  ) ^(P2-1) est de la forme  1+ W * P2  
                    par symetrie
                      S = (X^(P2-1)  ) ^(P1-1) est de la forme  1+ V * P1  

                    on en deduit que K * P2  = L * P1  
                          et commme P1 est different de P2
                           P2 ne divise pas P1 donc il divise  L
                         autrement dit  S = 1 + R * P1 * P2 

                Donc ( X^((P1-1)*(P2-1) ) % M  = 1
               pour peut que X % P1 != 0 et X % P2 != 0
               avec P1 et P2  des nombres premiers differants 

                 ----

                DONC SI M = P1 * P2  ( P1 ET P2 DEUX NOMBRES PREMIERS DIFFERENTS )
               ( X^((P1-1)*(P2-1) ) % M  = 1
               POUR PEUT QUE  X % P1 != 0 et X % P2 != 0
 
                 RQ : si X= K*P1  ou X=L*P2  cela ne marche pas !!!!

             =========================================================
              On peut generaliser a M =  P1 *  P2  * P3 ...
               ou P1 P2 P3 sont des nombres premiers tous differants
                On peut alors verifier que  :
                    (X ^ PHI[M)) % M = 1   si PGCD(X,M) == 1
             ==========================================================


                RQ : si X= K*P1  ou X=L*P2  cela ne marche pas !!!!
                    on ne trouve pas 1  : mais K un inverse de X  en modulo M 
                            K*X % M == 1

                     Ce qui donne bien au rang suivant la forme classique
                    du th de Fermat
                    X ^( 1 + Z * PHI(M))  % M = X % M  

                 dans le cadre du RSA le filtre PHI(M) 
                 est simplement (P1 -1) * (P2 -1) * ....


            Ordre multiplicatif de X tel que PGCD(X,M) == 1
           est egal a PHI(M)
            PGCD(X,M) == 1 est la pour eviter les ZERO !

            Elliminer les 1 :

               Comment etre Franc et eviter les Un
              soit X^K == 1 + S * M (ceci est possible si PGCD(X,M) != 0)
              ceci est possible si P est egal a  (P1- 1) ou  (P2 -1)
              ceci est possible si PGCD(P,PHI(M)) != 1

               Pour eviter avoir  X^K %M  == 1
              il est preferable  que PGCD(P,PHI(M)) == 1
              il est preferable  que P soit premeir !



 OPTIMISATION DES CALCULS


    RQ    A%(m1*M2) % M2 =  A % M2  :  operateur % modulo est distributif


    Exemple je veux calculer X^17 :

     * La methode bete :  X2 = X * X  X3 = X2 * X  .... 17 multiplications

     * Plus evolue  : j'ecrit 17 en base 2  : 10001   =  2^4 + 1
        je calcule la suite
           X2 = X * X ; X4=  X2 *X2;  X8 = X4 * X4;  X16 = X8 * X8;
             en 4 multiplication j'ai reconstitue la base 
           et j'ai plus qu'a multiplie entre eux 
                 ce qui sont marque par des 1 binaires :
           X17 = X16  * X    (5 multiplication en tout,  au lieu de 17 !)

       ( RQ Dans ces calculs suivants je ne precisse plus % M ,
          ce n est pas tres utile,
          car  A %( F * H) = A %H  = A %H %H %H ... !)

         RQ  ici pour obtimiser les calculs
           on a utilise une decomposition en binaire
           parce que les utilisateurs et les ordinteurs
           sont habitues a ca !
             Mais on pourrais faire ces calculs dans
            n'importe quelle base ou representation numerique  !

     * Mais il y a beaucoup d'autres variantes pour optimiser 
       les calculs de cryptage ( et de decryptage ) ...
         dont une que l'on vas decrire ici :

         Exemplez X^161 (10100001)
            ce truc la vas couter a priory 7+2 soit 9 multiplications !

         mais je peut aussi ecrire 161 = 23 * 7  = 7 * 23

          (x^7)^23=  X^161

          codage   7  (111)   
                   X2 = X * X  ; X4 = X2 * X2; ...  ; Y = X4 *X2 * X ;
                           total 4 multiplications

          decodage 23 (10111) 
                   Y2 = Y * Y  ; Y4= Y2 * Y2 ; Y8 = ..., Y16= 
                     4 multiplications
                   Y23 =  Y16  *   Y4  * Y2 * Y;
                     3 multipliucations
                           total 7 multiplications  (* au plus !)

                 (resultat Z = Y^23  = (X^7)^23 = X^161
                   (et si j'ai fait le calcul en modulo M 
                       tel que 1+ K * phi(M) = 161 !!!!
                   alors x^161%M == X   trouvez donc X !!! )

             le calcul global semble plus long (11 multiplications au lieu de 9);
          Mais il permet en reception de calculer la valeur de X sans la connaitre !

           Resultat en ecrivant 161 = 7 * 23   :

             * on peut coder Y=X^7
                 et on a besoin de connaitre X pour cela !

             * Mais Pour decoder  Z= (Y^23) (et obtenir x^161) 
                 ON N'A PAS BESOIN DE CONNAITRE X
                     (sinon c'est plus du decodage !!!);

                  Mais on doit etre sur que Y n'est jamais egal a 1
                   ( pour tous X != 1 )
                     ( sinon l'adn de X est perdu dans le pseudo codage !)
                   c'est pour cela que l'on verifis 
                        que 7 est premier avec PHI !

              global  ((x^7)^23 ) % ...

           c'est cette methode qui est a la basse du codage RSA !!!!


       RSA EXEMPLE NUMERIQUE 

            Soit donc   M =  5 * 11  =  55
           on a PHI(55)   =  4 * 10  =  40

            on verifis que avec  E=7   et D=23
           E*D= 161 = 1 +  K * PHI  = 1 + 4 * 40

                Pour etre sur que E a un inverse D modulo PHI
               il ne doit etre premier avec les composant de PHI 
               ( ici 7 est un nombre premier absolu 
                 qui verifis aussi : pgcd (7,40) = 1  ! )

                Ce controle avec indicateur Euler s'assure que X^7
               ne vas pas devenir element neutre 1 (en %M ) ! ( car 1 ^N = 1 )
               sinon on a perdu X en codent !!!

                   Comme le raisonnement est symetrique 
                  X^23 est different de 1%M (pour X >1 )
                  ce qui permet la signature 
                  ( qui sera decode par Y^7 la clef publique )


            *  RQ: quand on calcule pour le RSA 
                   les deux nombres premiers P1 P2,  
                   les deux nombres  E D
                       on peut garder ces infos dans la clef privee
                            pour obtimiser le decodage  Y^D ....

          X^ 161 % 55    = X    si pgcd(X,55) = 1
          X^   7 % 55   != 1    si X % M != 1


 THEORME 

     Euler Fermat ameliore 
     C'est une genralisation pour M = P1 * P2,
    avec P1 et P2 des premiers distincts :

       (X^PHI(M) ) % M  = 1  si X non null   et  PGCD (X,M) = 1 
        qui ce deduit simplement du TH de Fermat par distributivitee !

        Pgcd (X,P1*P2) permet de selectionner les X qui vont bien;
       en elliminent les mutiples indesirable !


   (  Dans le cas du RSA  M= P1 * P2,
     DEUX nombres premiers differents P1 et P2
      Si X est non null est inferieur a P1 et P2 ca marche aussi ! )

    L'ordre multiplicatif K de certain A modulo M
   est au plus egal a PHI,
    Il peut se reduire dans certain cas X  a des sous multiples de PHI 

    Par exemple si M est egale a 5 * 11 
   ordre multiplicatif pour %5  est 4 = 2 * 2
   ordre multiplicatif pour %11 est 10 = 2 * 5

    Par associativite on deduit que certain X^P peuvent se neutraliser
   pour       P multiple de 4  en %5
   ou pour    P multiple de 10 en %11
    On en deduit que pour modulo %55
   les neutralisation a 1 pourrais se produire
   sur les multiples 2 et 5 ( au plus tard a 40)

    Donc on choisi E ( pour coder les X  ( pour Y= X^E%M ))
   tel que PGCD(E ,PHI) = 1
   ce qui evite de tomber sur element neutre pour tous les Y

    On choisi ensuite D tel que ED soit 1 + K * de PHI
   ( pour retrouver X au decodage )

    Autrement dit dans le RSA on passe sont temps a eviter les zero et les un :

        le X a coder doit avoir un pgcd(X,M) == 1
       pour eviter que les multiplications, modulo ne devienne jammais nulle
        Le Y=X^E%M doit etre different de 1 
       on s'assure alors que PGCD(E,PHI(M)) == 1
        Une methode gagnante et de choisir E premier


 COEFFICIANTS DE BEZZOU

   Soit deux nombre entier A et B
   il existe  deux entiers U et V
   tel que   U*A + V*B  =  K * PGCD(A,B)

       si on rapport cela a equation de l'ordre multiplicatif

          E * D   =  1 + K * PHI(M)

        on trouve que D est egal au coefficiant de Bezzou U
        de   (  E,PHI  )
           U * E  + V * PHI   = PGCD(E,PHI) = 1 (si E et PHI sont premeir)

           D *  E  = 1  - V* PHI

               donc X^(E*D)%M   = X

 ALOGORITHME EUCLIDE

   Le PGCD(A,B) plus grand commun multiples de A et de B

   Si A et B sont premier entre eux alors leur PDGCD(A,B) est egal a 1
  et reciproquement

   On peut calculre le PGCD par recurance 
  PGCD(A,B) = PGCD(B, A%B)

   pseudo code
     avec A>B

      while(B) do

          NB  =   A % B
          A   =   B
          B   =   NB

        done
      return(A)


   On sait qu'il existe U et V les coef. de Bezzou tel que
  U * A + V * B = PGCD(A,B)

   On peut calculer ces coefficient en meme temps que le pgcd
  par algorithme Euclide etendu

   pseudo code
     avec A>B

     U  = 1    V = 0      ( A0 = 1 * A0 + 0 * B0) les deux vecteurs
     UU = 0   VV = 1      ( B0 = 0 * A0 + 1 * B0) initiaux

     while(B) do

          Q  =   A // B   division entiere  ( A % B  =  A - Q * B )

          NB  =   A % B
          A   =   B 
          B   =  NB

          NUU =  U - Q * UU
          U   =  UU
          UU  = NUU

          NVV =  V - Q * VV
          V   =  VV
          VV  = NVV

     done
     return (PGCD=A  ,  U ,   V)

        les 3 groupes iterations ci-dessus   A  B      U UU    V VV
       sont similaires et peuvent etre traites simultanement
       par une notation vectorielle
        on utilise deux vecteurs que l'on combine lineairement
       pour obtenir un troiseme (qui est le reste de la division A % B ) ,
        on recommence a iterer sur le 2 eme et le 3 eme ...

           A=A0  U=1   V=0     
           B=B0  UU=0  VV=1

           while(B) do

                Q= A//B
                (nB nUU nVV)  =     ( A  U   V )  - Q * ( B  UU  VV)
                (A U V)   =   ( B UU VV)
                (B UU VV) =   (nB nUU nVV)

           done 
           return (PGCD=A  ,  U ,   V)

           PGCD(A0,B0) =  U * A0 + V * B0


 TESTS DE PRIMALITEE


   Il est necesaire dans les calculs RSA
  de trouver deux nombres premier P1 et P2 differants et tres grands !
   Ce qui permet de valider les algorithme de Fermat ....

   Ceci peut etre long et doit donner des resultats variees
  (non predictibles) et on n'a pas pour le momemnt 
   algorithme rapide et sur  (heureusement *) :

    On n'est pas sur en fait que les nombres trouves
   son vraiment premiers :
       Il existe des nombres dit de Kermichel
      qui peuvent etre utilise dans le RSA
      sans etre premier !
        M pourrais etre alors le produit de trois nombres premiers differents ...

    Dans le cadre du RSA on prends le probleme a l'envers
   on verifis que les nombres trouves pour le moment
   fonctionnent en testant un cycle cryptant decryptant 
   sur des  valeur de X de test special
   les nombres premier 1 3 5 7 11...
   et puis c'est tous !!!
    Si ca plante on continus a chercher d'autres nombres premiers
   compatible RSA ....
    Si ca ne plante pas on espere alors que cela va marcher !

    (* En matier de securitee cryptage :
           le mieux peut etre ennemis du bien !)


 RESUME RSA


   On sait que les puissances sucessives de X 
    finissent par redonner X ( en modulo M )
     au bout d'un certains temps !

  M est a priori le produit de deux nombres premiers differants P1 et P2
    on calcule sont indicateur Euler PHI= (P1 - 1) * (P2 - 1)

  Y=  (x^E) % M   cryptage
  Z=  (y^D) % M   decryptage

    on veut que Z soit egal a X 
      au minimum on doit avoir (X ^(E*D) ) % M  egal  X % M

          Ceci est vrai avec th Euler Fermat si (E*D) = 1 + K * PHI(M)
         ( E et D sont des genres d'inverses modulo PHI )

          Mais cela n'est pas suffisant ;
         Il est necessaire en plus que Y ne soit pas egal a 1
         ( car sinon on perd X )
         Pour eviter cela, E doit etre premier
         avec tous les composant de PHI(M) !

            Traditionellement on prends E de la forme 2^K+1  
           3  5  32767  .....
           qui sont  aussi des nombres premier dans l'absolu
           (donc ils ne sont pas des diviseurs de PHI )

         Il reste a calculer D l'inverse de E modulo phi(M) !!!!
        si pgcd (E,PHI) = 1 alors D existe, pour le trouver,
        on utilise le TH Euclide etendu ( calcul pgcd et des coef Bezzou)

          Par iterations on trouve D , N  , PGCD  (algo euclide etendu)
         pour  N * PHI + D * E  = pgcd(PHI,E) = 1
              ( pgcd = 1 par choix de E premier )

        Algo Euclide etendu permet de trouver D ( le coef Bezzou  V )
       et verifis que le PGCD est bien 1 ( D et E sont alors premiers avec PHI )

   La celf publique se resume a M et a E !
  tous le reste n'est connus que dans la clef prive !!!


 LIMITES DU CRYPTAGE RSA


   * 0 est toujours code 0

   * 1 est toujours code 1

   * si on code un X trop grand superieur a  M 
      apres decodage on ne retrouvera pas le meme
        mais plutot son equivalant X % M

     si par Hazard X=P1 ( ou P2) il sera code O, 
     il faudrai que X soit plus petit que P1 et P2
     ( que l'on peut extimer a racine carre de M )
     et garder un peut de place pour faire les calculs

       * limiter la taille du X a coder
          typiquement pour une clef de 1024 (128 octets) bits
          on peut se limites a 880 bits (110 octets)

   * inversement si le nombre a coder X est
       trop petit il est transmis sans etre 'crypte'

      La norme 509 prevois :
         Que l'on utilise pour exposant public un nombre
        premier de la forme 2^? + 1 :
            3,   5,    2^16 + 1 = 65537  ....

      Si le nombre a coder n'a pas suffisament de bits significatif
     ( LB2 (X) est le log base 2 de x )
     compare a la taille de la clef ( son modulo M ) :

        Donc si LB2(X)  * 16  est inferieur a LB2(M)

        Alors le 'crypage' peut se faire
       sans avoir a utiliser le %M 
       ( donc independament de la clef privee utilisee)
        il se reduit a X^65537

        De fait on peut decrypter :
       avec n'importe quelle autre clef
       de taille superieur ( avec un M plus grand )!

         Il suffit alors de  recrypter le nombre obtenue
        avec la premiere clef publique initiale
        et de comparer les resultats pour verifier !!!

     En premiere approximations :

       pour une clef de 1024 bit le nombre a coder doit avoir
             au moins  64 bits significatif  (8 octes)  (1024/16)
       pour une clef de 2048 bit le nombre a coder doit avoir
             au moins 128 bits significatif (16 octes)  (2048/16)

       RQ : Une signature MD5 utilisee
           juste 16 octets (un peut plus en SHA !)
             donc pour instant signer un document en MD5
               avec une clef de 2048 bits
                 n'est pas vraiment garantis (usurpation possible)
            Prenez donc habitude de signer simultanement en MD5 et SHA 
           et d'utiliser des mots de passe suffisament long !!!