X Informatique MP/PC 2008

ÉCOLE POLYTECHNIQUE
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES
CONCOURS D'ADMISSION 2008

FILIÈRE

MP - OPTION PHYSIQUE ET SCIENCES DE L'INGÉNIEUR

FILIÈRE

PC

COMPOSITION D'INFORMATIQUE
(Durée : 2 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête 
de la copie.

Ave Cesar (zud bdrzq)
On cherche à crypter un texte t de longueur n composé de caractères en 
minuscules (soit 26
lettres différentes) représentés par des entiers compris entre 0 et 25 (0  a, 1 
 b, . . . 25  z).
Nous ne tenons pas compte des éventuels espaces.
Ainsi, le texte ecolepolytechnique est représenté par le tableau suivant où la 
première
ligne représente le texte, la seconde les entiers correspondants, et la 
troisième les indices dans le
tableau t.
e
4
0

c
2
1

o
14
2

l
11
3

e
4
4

p
15
5

o
14
6

l
11
7

y
24
8

t
19
9

e
4
10

c
2
11

h
7
12

n
13
13

i
8
14

q
16
15

u
20
16

e
4
17

Codage de César
Ce codage est le plus rudimentaire que l'on puisse imaginer. Il a été utilisé 
par Jules César (et
même auparavant) pour certaines de ses correspondances. Le principe est de 
décaler les lettres
de l'alphabet vers la gauche de 1 ou plusieurs positions. Par exemple, en 
décalant les lettres de
1 position, le caractère a se transforme en z, le b en a, ... le z en y. Le 
texte avecesar devient
donc zudbdrzq.
Question 1 Que donne le codage du texte maitrecorbeau en utilisant un décalage 
de 5 ?
Question 2 Écrire la fonction codageCesar(t, n, d) qui prend en arguments le 
tableau t, sa
longueur n et un entier d ; et qui retourne un tableau de même taille que t 
contenant le texte t
décalé de d positions.
Question 3 Écrire de même la fonction decodageCesar(t, n, d) prenant les mêmes 
arguments
mais qui réalise le décalage dans l'autre sens.

1

Pour réaliser ce décodage, il faut connaître la valeur du décalage. Une manière 
de la déterminer
automatiquement est d'essayer de deviner cette valeur. L'approche la plus 
couramment employée
est de regarder la fréquence d'apparition de chaque lettre dans le texte 
crypté. En effet, la lettre
la plus fréquente dans un texte suffisamment long en français est la lettre e.
Question 4 Écrire la fonction frequences(t , n) qui prend en argument un 
tableau t de taille
n représentant le texte crypté ; et qui retourne un tableau de taille 26 dont 
la case d'indice i
contient le nombre d'apparitions du nombre i dans t (0  i < 26).
Question 5 Écrire la fonction decodageAuto(t , n) qui prend en argument le 
tableau t de taille
n représentant le texte crypté ; et qui retourne le texte t d'origine (en 
calculant la clé pour que
la lettre e soit la plus fréquente dans le texte décrypté).

Codage de Vigenère
Au XVIème siècle, Blaise de Vigenère a modernisé le codage de César très peu 
résistant de la
manière suivante. Au lieu de décaler toutes les lettres du texte de la même 
manière, on utilise
un texte clé qui donne une suite de décalages.
Prenons par exemple la clé concours. Pour crypter un texte, on code la première 
lettre en
utilisant le décalage qui envoie le a sur le c (la première lettre de la clé). 
Pour la deuxième lettre,
on prend le décalage qui envoie le a sur le o (la seconde lettre de la clé) et 
ainsi de suite. Pour la
huitième lettre, on utilise le décalage a vers s, puis, pour la neuvième, on 
reprend la clé à partir
de sa première lettre. Sur l'exemple ecolepolytechnique avec la clé concours, 
on obtient : (la
première ligne donne le texte, la seconde le texte crypté et la troisième la 
lettre de la clé utilisée
pour le décalage)
e
g
c

c
q
o

o
b
n

l
n
c

e
s
o

p
j
u

o
f
r

l
d
s

y
a
c

t
h
o

e
r
n

c
e
c

h
v
o

n
h
u

i
z
r

q
i
s

u
w
c

e
s
o

Question 6 Donner le codage du texte becunfromage en utilisant la clé de codage 
jean.
Question 7 Écrire la fonction codageVigenere(t, n, c, k) qui prend comme 
arguments un tableau
t de taille n représentant le texte à crypter, et un tableau d'entiers c de 
longueur k donnant la
clé servant au codage ; et qui retourne un tableau de taille n contenant le 
texte crypté t .
Maintenant, on suppose disposer d'un texte t assez long crypté par la méthode 
de Vigenère,
et on veut retrouver le texte t d'origine. Pour cela, on doit trouver la clé c 
ayant servi au codage.
On procède en deux temps : 1) détermination de la longueur k de la clé c, 2) 
détermination des
lettres composant c.
La première étape est la plus difficile. On remarque que deux lettres 
identiques dans t espacées
de  × k caractères (où  est un entier et k la taille de la clé) sont codées par 
la même lettre dans
t . Mais cette condition n'est pas suffisante pour déterminer la longueur k de 
la clé c puisque des
répétitions peuvent apparaître dans t sans qu'elles existent dans t. Par 
exemple, les lettres t et
n sont toutes deux codées par la lettre h dans le texte crypté à partir de 
ecolepolytechnique
avec concours comme clé. Pour éviter ce problème, on recherche les répétitions 
non pas d'une
2

lettre mais de séquences de lettres dans t puisque deux séquences de lettres 
répétées dans t,
dont les premières lettres sont espacées par  × k caractères, sont aussi 
cryptées par deux mêmes
séquences dans t .
Dans la suite de l'énoncé, on ne considère que des séquences de taille 3 en 
supposant que
toute répétition d'une séquence de 3 lettres dans t provient exclusivement 
d'une séquence de 3
lettres répétée dans t. Ainsi, la distance séparant ces répétitions donne des 
multiples de k.
La valeur de k est obtenue en prenant le PGCD de tous ces multiples. Si le 
nombre de
répétitions est suffisant, on a de bonnes chances d'obtenir la valeur de k. On 
suppose donc que
cette assertion est vraie.
Question 8 Écrire la fonction pgcd(a, b) qui calcule le PGCD des deux entiers 
strictement
positifs a et b par soustractions successives de ses arguments.
Question 9 Écrire la fonction pgcdDesDistancesEntreRepetitions(t , n, i) qui 
prend en argument
le texte crypté t de longueur n et un entier i (0  i < n - 2) qui est l'indice 
d'une lettre dans
t ; et qui retourne le pgcd de toutes les distances entre les répétitions de la 
séquence de 3 lettres
ht[i], t[i + 1], t[i + 2]i dans la suite du texte ht[i + 3], t[i + 4], . . . 
t[n - 1]i. Cette fonction retourne
0 s'il n'y a pas de répétition.
Question 10 Écrire la fonction longueurDeLaCle(t , n) qui prend en argument le 
texte crypté
t de longueur n ; et qui retourne la longueur k de la clé de codage.
Question 11 Donner le nombre d'opérations réalisées par la fonction 
longueurDeLaCle en
fonction de la longueur n ? (On ne comptera que le nombre d'appels à la 
fonction PGCD).
Question 12 Une fois la longueur de la clé connue, donner une idée d'algorithme 
permettant
de retrouver chacune des lettres de la clé. (Il s'agit de décrire assez 
précisément l'algorithme
plutôt que d'écrire le programme).
Question 13 Écrire la fonction decodageVigenereAuto(t , n) qui prend en 
argument le tableau
t de taille n représentant le texte crypté ; et qui retourne le texte t 
d'origine. (On n'hésitera pas
à recopier des parties de texte dans des tableaux intermédiaires).

3

X Informatique MP/PC 2008 -- Corrigé
Ce corrigé est proposé par Arnaud Borde (École Polytechnique) ; il a été relu 
par
Céline Chevalier (ENS Cachan) et Vincent Puyhaubert (Professeur en CPGE).

Le sujet propose l'étude de deux méthodes de codage de texte basées sur le 
décalage des lettres dans l'alphabet. On travaille cependant sur une 
représentation
simpliste d'un texte par des tableaux d'entiers. Dans les deux méthodes, on 
commence par écrire les fonctions simples qui permettent de coder un texte à 
partir
d'une clé. Puis on étudie des techniques pour décoder le texte automatiquement,
c'est-à-dire sans connaître la clé. Il s'agit du travail qu'est amené à faire 
tout pirate
qui se respecte.
La plupart des questions demandent d'écrire du code. Il est rédigé en Maple
dans ce corrigé car ce langage est le plus utilisé en classe préparatoire, même 
s'il
est plus destiné au calcul formel qu'à la programmation. D'autres langages comme
C, C++, Caml, Pascal et Java étaient autorisés pour cette épreuve. Les fonctions
écrites n'utilisant que la syntaxe de base, vous pourrez sans difficulté les 
réécrire
dans le langage de votre choix.
· La première partie a pour objectif l'étude du codage de César. Ce codage 
basique paraîtra familier à tout le monde puisqu'il consiste simplement à 
choisir un entier k (une lettre en fait, mais peu importe) et à remplacer chaque
lettre du texte par la k e qui la suit dans l'alphabet. Par exemple, pour k = 1,
on remplace « a » par « b », « b » par « c », et ainsi de suite jusqu'au « z »
remplacé par « a ».
Comme mentionné précédemment, l'objectif de cette partie est non seulement
de rédiger les programmes qui codent un texte, mais aussi de trouver une 
méthode de décodage automatique, basée sur l'hypothèse (souvent vérifiée) que
la lettre « e » est la plus présente dans le texte original. Elle ne devrait 
poser
aucun problème à tout candidat familier avec l'usage des boucles.
· La seconde partie étudie le codage de Vigenère, qui est une amélioration de la
méthode de César. Il s'agit cette fois d'utiliser non pas un unique entier, 
mais p
entiers k1 , . . . , kp (en fait, un mot de p lettres). On code alors la ne 
lettre du
texte grâce à un décalage de k(n mod p) caractères.
À nouveau, la difficulté de cette partie réside essentiellement dans l'écriture 
de
la fonction de décodage automatique. Heureusement, le travail est en grande
partie facilité par l'énoncé, qui détaille de façon précise les hypothèses à 
effectuer sur le texte et l'algorithme à employer.
Au final, le problème est assez long, mais en étant efficace il est possible 
d'en
venir à bout dans les deux heures imparties. Il est bien écrit et très agréable 
à suivre.
On peut passer pas mal de temps à s'amuser avec les fonctions de codage/décodage
une fois le problème résolu en totalité.

Indications
2 Écrire dès maintenant une fonction reste(a,b) qui renvoie le reste de la 
division
de a par b.
3 Penser à réutiliser le code de la question 2 sans tout refaire.
4 Initialiser le tableau contenant les fréquences avec des 0. Parcourir le 
tableau de
sorte que pour chaque nouvelle lettre lue, on mette à jour la case 
correspondante
dans le tableau des fréquences.
5 Pour trouver la lettre qui code « e », rechercher la lettre dont l'entrée 
dans le
tableau frequences est maximale. C'est cette lettre qui servira à calculer la 
clé
de décodage.
7 Utiliser la fonction reste afin d'associer le bon décalage à chaque lettre du 
texte
original.
8 Utiliser une méthode récursive. A partir d'un couple d'entier donné en 
argument,
retrancher le plus petit au plus grand jusqu'à ce que le résultat de la 
soustraction
soit nul.
9 Passer en revue tous les triplets de lettres qui suivent t[i], t[i+1], t[i+2] 
et les
comparer à ce dernier. Faire attention aux indices de début et de fin de la 
boucle.
Utiliser la propriété d'associativité du pgcd pour mettre à jour le résultat au 
fur
et à mesure du parcours.
10 Utiliser les fonctions des questions 8 et 9. Utiliser encore la propriété 
d'associativité du pgcd et appliquer l'algorithme donné par l'énoncé.
11 Bien compter le nombre d'itérations dans les boucles.
12 Voir les différents tableaux t[j], t[j+k], t[j+2k],..., pour j  {0, k - 1}, 
comme
des textes codés par la méthode de César.
13 Conserver la vision de t comme un ensemble de textes codés par la méthode 
César
et les décoder successivement comme dans la première partie. Utiliser une 
matrice
(un tableau de tableaux) pour faciliter la remise en ordre du texte.

Codage de César
Ce corrigé introduit deux fonctions locales (reste et quotient) qui ne
sont pas indispensables pour cette épreuve mais qui permettent de gagner du
temps et évitent d'utiliser des fonctions de Maple qui ne sont peut-être pas
connues de tous.
Rappelons également que tout ce qui est précédé d'un # dans un programme en 
Maple n'est pas interprété par le compilateur, ce qui permet
d'insérer des commentaires dans le code.
1 Représentons les phases du codage dans un tableau. Les différentes lignes 
représentent : le texte d'origine, les entiers correspondants, les entiers 
après décalage,
le texte codé.
m
12
7
h

a
0
21
v

i
8
3
d

t
19
14
o

r
17
12
m

e
4
25
z

c
2
23
x

o
14
9
j

r
17
12
m

b
1
22
w

e
4
25
z

a
0
21
v

u
20
15
p

Le codage de maitrecorbeau avec un décalage de 5 vers la gauche est donc :
hvdomzxjmwzvp

Il faut être attentif au fait que le décalage se fait vers la gauche.
2 Commençons par écrire une fonction reste(a,b) qui renvoie le reste de la 
division
de a par b. On programme cette fonction de manière récursive, en partant de a
et en soustrayant b autant de fois qu'il le faut pour le résultat devienne égal 
à b.
Notons qu'il faut aussi penser à prendre en compte le cas où a est négatif.
reste:=proc(a,b)
if 0<=a and a=b then RETURN(reste(a-b,b));
else RETURN(reste(a+26,b));
# correspond au cas où a est négatif
fi;
end;
Cette fonction peut être remplacée par la fonction Maple irem(a,b).
Cette fonction va principalement servir dans le cas particulier b = 26 pour se
ramener à un entier compris entre 0 et 25 dès qu'on effectue un décalage.
Pour coder un texte, chaque lettre doit être décalée vers la gauche du nombre d.
Pour cela, on construit au moyen d'une boucle for un tableau resultat de même
taille que le tableau t donné en entrée, dans lequel on stocke le texte chiffré.
Pour chaque indice, l'élément rajouté au tableau est le reste de la division 
par 26
du chiffre t[i] auquel on a soustrait d.

codageCesar:=proc(t,n,d)
local resultat,i;
resultat:=[seq(0,i=0..n-1)];
for i from 0 to n-1 do
resultat[i+1]:=reste(t[i+1]-d,26);
od;
RETURN(resultat);
end;
Dans Maple, contrairement aux autres langages de programmation, les
indices de tableaux commencent par défaut à 1 et non à 0. Si vous utilisez ce
langage, il est bien de préciser la convention que vous adoptez pour les indices
car le sujet suppose qu'ils débutent à 0. On respecte ici la convention utilisée
par l'énoncé pour les boucles tout en conservant un code exécutable en 
réajustant les indices dans le corps de la boucle avec la syntaxe tableau[i+1].
La commande seq permet de fabriquer une séquence. Sa syntaxe générale est 
seq(f(compteur),compteur=début..fin). Elle produit alors la
séquence f(début), f(début+1), ..., f(fin). Ici, cette séquence est placée 
entre crochets afin de fabriquer une liste.
Il existe une fonction de Maple, nops(), qui permet de récupérer la longueur du 
tableau ou de la liste placé en argument. On aurait donc pu se
passer du second argument de la fonction (et de même pour beaucoup de
fonctions demandées par l'énoncé). Mais il y a fort à parier que les 
concepteurs du sujet n'ont pas voulu pénaliser les élèves qui ne connaîtraient 
pas
cette fonction.
3 Il suffit d'utiliser la fonction précédente avec un décalage opposé.
decodageCesar:=proc(t,n,d)
codageCesar(t,n,-d);
end;
4 On remplit en premier lieu le tableau des fréquences appelé freq à l'aide de 0
avant de parcourir le texte et de le mettre à jour au fur et à mesure. À chaque 
fois
que l'on rencontre une lettre, on augmente la case correspondante (à savoir 
celle dont
l'indice est t'[i]) dans le tableau des fréquences de 1.
frequences:=proc(tprime,n)
local freq,i;
# on crée le tableau des fréquences avec des 0
freq:=[seq(0,i=0..26)];
# on met à jour le tableau des fréquences
for i from 0 to n-1 do
freq[tprime[i+1]+1]:=freq[tprime[i+1]+1]+1;
od;
RETURN(freq);
end;