Calcul formel : Mode d'emploi - Exemples en Maple

Claude Gomez, Bruno Salvy, Paul Zimmermann

Masson, 1995

Chapitre IV, section 1, exercice 4, page 107.

Philippe.Dumas@inria.fr
http://algo.inria.fr/dumas/Maple/

Page du Projet Algorithmes | Page de Philippe Dumas | Page Maple de Philippe Dumas

Retour en page principale
Table des matières
Index
Maple V.3 worksheet
Maple V.4 worksheet
Maple V.5 worksheet


La grande difficulté de l'exercice est de recopier correctement le code fourni dans le texte et l'énoncé. Nous le traitons en Maple V.3 et en Maple V.5.

Calcul en Maple V.3 | Calcul en Maple V.5

Calcul en Maple V.3. L'alphabet choisi comporte les vingt-six lettres minuscules de l'alphabet latin et l'espace.

> Alphabet:=`abcdefghijklmnopqrstuvwxyz `:

> nb_lettres:=length(Alphabet);

[Maple Math]

> for i to nb_lettres do lettre[i-1]:=substring(Alphabet,i..i) od:

> lettre[0];

[Maple Math]

On note qu'une lettre est aussi un nom. C'est ce qui explique l'emploi d'un second argument dans l'eval qui suit, comme indiqué en note de bas de page.

> for i to nb_lettres do codage[eval(lettre[i-1],1)]:=i-1 od:

> transforme:=proc(s:string)
local i;
convert([seq(codage[substring(s,i..i)]*nb_lettres^(i-1),
i=1..length(s))],`+`)
end:

> detransforme:=proc(l:posint) 
local i;
cat(seq(eval(lettre[i],1),
i=convert(l,base,nb_lettres)))
end:

> encode:=proc(a,e,n)
local i;
[seq(Power(i,e) mod n,
i=convert(transforme(a),base,n))]
end:

On note au passage l'emploi de la procédure inerte Power en liaison avec le calcul modulaire, dans un souci d'efficacité.

> decode:=proc(b,d,n)
local mess,i;
mess:=map(Power,b,d) mod n;
detransforme(convert([seq(mess[i]*n^(i-1),
i=1..nops(mess))],`+`))
end:

On définit ensuite les entiers de l'exemple.

> n:=289589985965965651459:

> e:=324803928042397:

> code:=[71115087473551843419,53212936362331915368]:

Nous constatons que l'entier n n'est pas premier. Nous tentons donc une factorisation. Elle réussit parce que l'entier choisi est petit. C'est en fait l'obstacle infranchissable en pratique qui défend la confidentialité du message. Deux facteurs premiers apparaissent et le reste n'est qu'une recopie de l'exemple traité.

> isprime(n);

[Maple Math]

> readlib(ifactors)(n):

> p:="[2][1][1]:

> q:=""[2][2][1]:

> d:=1/e mod (p-1)*(q-1):

> decode(code,d,n);

[Maple Math]

Calcul en Maple V.5. En Maple V.5, la différence est faite entre les noms et les chaînes de caractères. Le code précédent doit donc être légérement adaptée. La modification est d'ailleurs assez bénigne.

> Alphabet:="abcdefghijklmnopqrstuvwxyz ":

> nb_lettres:=length(Alphabet):

> for i to nb_lettres do lettre[i-1]:=substring(Alphabet,i..i) od:

> lettre[0];

[Maple Math]

Chaque lettre de l'alphabet est maintenant une chaîne de caractères et n'est pas un nom. Du coup l'emploi astucieux d'eval n'a plus lieu d'être.

> for i to nb_lettres do codage[eval(lettre[i-1])]:=i-1 od:

> transforme:=proc(s::string)
local i;
convert([seq(codage[substring(s,i..i)]*nb_lettres^(i-1),
i=1..length(s))],`+`)
end:

> detransforme:=proc(l::posint) 
local i;
cat(seq(eval(lettre[i],1),
i=convert(l,base,nb_lettres)))
end:

> encode:=proc(a,e,n)
local i;
[seq(Power(i,e) mod n,
i=convert(transforme(a),base,n))]
end:

> decode:=proc(b,d,n)
local mess,i;
mess:=map(Power,b,d) mod n;
detransforme(convert([seq(mess[i]*n^(i-1),
i=1..nops(mess))],`+`))
end:

> n:=289589985965965651459;

> e:=324803928042397;

> code:=[71115087473551843419,53212936362331915368];

[Maple Math]

[Maple Math]

[Maple Math]

> isprime(n);

[Maple Math]

> readlib(ifactors)(n);

[Maple Math]

> p:=%[2][1][1];

[Maple Math]

> q:=%%[2][2][1];

[Maple Math]

> d:=1/e mod (p-1)*(q-1);

[Maple Math]

> decode(code,d,n);

[Maple Math]

Si les deux facteurs premiers avaient été pris plus grands, par exemple de l'ordre de 10^20 (au lieu de 10^10), il y a fort à parier que le message serait resté secret (en employant Maple).

Retour en page principale