Un lipogramme sur la cryptanalyse
Alain Brobecker, du 28oct2002 au 15sep2004

Jadis on cryptait l'information par substitution: on codait tout "a" par un "m", tout "b" par un "t"... Puis, si on connaissait la combinaison, on trouvait aussi l'original par substitution. Sans blancs (ils sont courants: 99 ici), sans ponctuation, sans aucun invariant, il y a alors 148362637348470135821287825 choix distincts pour la combinaison, trop pour un importun ayant surpris la communication. Mais un individu sournois s'appuya sur la proportion d'apparition standard du "a", du "b"... trouvant ainsi la combinaison. Donc il fallut obscurcir plus l'information avant sa transmission, modifiant tout au moins la proportion d'apparition standard (mais pas aussi mal qu'ici).


Démontrons qu'il y a bien 148362637348470135821287825 combinaisons sans invariant. Commençons par donner un exemple: avec les 3 lettres ABC, il y a 3!=6 combinaisons possibles qui sont: ABC, ACB, BAC, BCA, CAB et CBA. Parmi celles-ci il y a 4 combinaisons avec une ou plusieurs lettres invariantes (qui restent à la même place), et 2 sans aucun invariant (en gras, aucune lettre ne conserve la même place).

Appelons NCI(n) le nombre de combinaisons de n lettres possédant au moins une lettre invariante, et f(n) le nombre de combinaisons de n lettres dont la première lettre n'est pas invariante mais possédant au moins une lettre invariante. Alors on a pour tout n>2:
NCI(n) = (n-1)! + f(n) avec f(2) = 0
et f(n) = (n-1) x [ NCI(n-2) + f(n-1) ]

Avec n lettres, pour qu'une combinaison possède au moins un invariant, soit la première lettre est invariante, auquel cas la disposition des n-1 autres lettres n'a pas d'importance et on a alors (n-1)! possibilités pour que la combinaison possède au moins un invariant, soit la première lettre n'est pas invariante et on a cette fois f(n) possibilités. Autrement dit NCI(n) = (n-1)! + f(n).

Pour trouver f(n) supposons que la combinaison possède au moins un invariant, mais que la première lettre ne soit pas invariante, alors celle-ci est envoyée à la place d'une des n-1 autres lettres. Supposons qu'elle soit envoyée sur la deuxième lettre (on notera A->B), alors on a deux cas possibles:

  1. Soit la deuxième lettre est elle même envoyée à la place de la première, alors aucune de ces deux lettres n'est invariante. Pour que la combinaison possède au moins un invariant, il faut que la combinaison des n-2 autres lettres en possède elle même au moins un, ce qui amène à NCI(n-2) possibilités.
  2. Soit la deuxième lettre est envoyée sur une des n-2 autres lettres. Supposons qu'elle soit envoyée sur C, alors on aura un cycle du genre A->B->C->...->A. La combinaison totale est alors la réunion disjointe de ce cycle et d'une permutation 'sigma' de toutes les lettres n'appartenant pas au cycle. Pour que cette combinaison poss&eagrave;de au moins un invariant, il faut et il suffit que la réunion disjointe du cycle B->C->...->B composé avec 'sigma' possède au moins un invariant autre que A. Autrement dit lorsqu'on considère la restriction de notre alphabet aux n-1 lettres à partir de B, cette dernière lettre n'est pas invariante, mais la combinaison possède au moins un invariant, et il y a alors par définition f(n-1) possibilités.
Le raisonnement est valable pour les n-1 lettres sur lesquelles on peut envoyer A, donc on a bien f(n) = (n-1) x [ NCI(n-2) + f(n-1) ].

On vérifie aisément que f(2) = 0 puisque les combinaisons pour deux lettres sont: AB et BA. On voit que si la première lettre n'est pas invariante (c'est BA), alors la combinaison ne possède aucune lettre invariante.

A partir de ces formules, et à l'aide d'un cours programme (voir plus loin), on peut calculer f(n), NCI(n) et en déduire NCS(n) = n! - NCI(n) le nombre de combinaisons de n lettres sans aucun invariant:

nf(n)NCI(n)NCS(n)
2011
3242
49159
5527644
6335455265
7246631861854
8204472548714833
9189064229384133496
10193095922938391334961
11216034302523223014684570
12262869959302786759176214841
13345722626839362278682290792932
14488801693515510719015132071101049
15739429561066826607852266481066515734
1611918051268255132257256362557697064251745
17203914545928336224837335816336130850092279664
18369138461659804740470720446940472355301661033953
19704919951434588947689436884918689444750731559645106
2014162422765749058791537887376983737879895014631192902121
21298627329084818554603229563491665849546018795307255050944540
22659413025994777460119710503968166486900119413496759611120779881
2315217590540051591022738163415912678291987027389510425471055777937262
24366346173689015792225711392198190427900768865711228250211305338670494289
25918450635896427978228277698049547606975192216427765706255282633466762357224
26239417613734804513778712175254928823778135499762712175148362637348470135821287825

Enfin voici le listing du programme permettant de calculer cette table. Il a été écrit en SockZ, un excellent langage de programmation basé sur le Forth, et qui permet de manipuler aisément les grands nombres et les rationnels. Et, euh... écrit par votre serviteur... ce qui explique sans doute pourquoi il est tellement bon! ;) Bref, le voici:

;2004sep13 - Alain Brobecker
;Count NCS(n) the number of permutations of n elements with no invariant.
;It uses NCI(n) the number of permutations of n elements with at least
;one invariant, f(n) the number of permutations of n elements where the
;first element varies but with at least one invariant. The formulas
;used then are, for every n>2:
;  NCS(n) = n! - NCI(n)
;  NCI(n) = (n-1)! + f(n)
;  f(2)= 0   and  f(n) = (n-1) * [ NCI(n-2) + f(n-1) ]
  "n f(n) NCI(n) NCS(n)" CR
  1 1       ;NCI(n-2) NCI(n-1)
  0         ;f(n-1)
  3         ;n
.loop
  COPY PRINT " "        ;print n
  COPY 1 - COPY ! SWAP2 ;... NCI(n-2) NCI(n-1) f(n-1) n (n-1)! n-1
  6 OVER 5 OVER + *     ;... n (n-1)! f(n)=(n-1)*(NCI(n-2)+f(n-1))
  COPY PRINT " "        ;print f(n)
  COPY 5 SWAP DROP      ;replace f(n-1) by f(n)
  +                     ;... NCI(n-2) NCI(n-1) f(n) n NCI(n)=(n-1)!+f(n)
  COPY PRINT " "        ;print NCI(n)
  OVER2 ! OVER2 -       ;... NCI(n-2) NCI(n-1) f(n) n NCI(n) NCS(n)=n!-NCI(n)
  PRINT CR              ;print and remove NCS(n)
  3 SWAP                ;... NCI(n-2) NCI(n-1) NCI(n) n f(n)
  SWAP2 1 +             ;... NCI(n-2) NCI(n-1) NCI(n) f(n) n+1
  COPY 26 SKIP> loop
END

;Compute n!, from the library
#! COPY SKIP>0 !end COPY 1 - ! * END
.!end DROP 1 END