>

Arithmétique : calcul sur les entiers, calcul modulo

Dans cette série de travaux pratiques, on s'intéresse principalement à l'algorithmique sur des entiers (pgcd - algorithme d'euclide, crible d'érathostène) puis à de l'arithmétique modulaire. Enfin, on conclura par un exercice mélangeant interpolation et arithmétique sur le partage de secret en cryptographie (les schémas à seuil).

Les entiers

Voici quelques instructions utilisants des fonctions usuelles sur les entiers. La plupart du temps, la signification est claire suivant le contexte. Sinon, pensez à regarder l'aide.

> type(10,integer);

true

> whattype(12);

integer

> whattype(12.5);

float

> type(-6,nonnegint);

false

> type(-6,negint);type(2,posint);

true

true

> issqr(25);sqrt(25);

true

5

> issqr(3);sqrt(3);

false

3^(1/2)

> isprime(1); isprime(2); isprime(17); isprime(18);  

false

true

true

false

> iquo(25,4);iquo(25,7);iquo(25,5);

6

3

5

> irem(25,4); irem(25,7);irem(25,5);

1

4

0

> igcd(2,3); igcd(4,9); igcd(6,21);

1

1

3

> igcdex(6,21,'s','t');

3

> s,t;

-3, 1

> igcdex(18,30,'s','t');

6

> s,t;

2, -1

>

L'algorithme d'Euclide

L'algorithme d'Euclide permet de calculer le pgcd (plus grand commun diviseur) de deux nombres a et b selon le schéma suivant : On a

pgcd(a,b)=pgcd(|a|,|b|);

Si a>=b alors pgcd(a,b)=pgcd(a-b,b), sinon pgcd(a,b)=pgcd(a,b-a). Quand l'un des deux entiers devient nul, l'autre élément est le pgcd.

1) Vous devez écrire une procédure Maple permettant d'obtenir le pgcd de deux nombres (en d'autres terme, reprogrammer la fonction igcd (ou igcdex) de maple).

> pgcd:=proc(a::integer,b::integer)
local h,k;

h:=max(abs(a),abs(b));

k:=min(abs(a),abs(b));

if k=0 then return h

else return pgcd(h-k,k) end if;

end proc;

pgcd := proc (a::integer, b::integer) local h, k; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); if k = 0 then return h else return pgcd(h-k, k) end if end proc

> pgcd(6,21);

3

> pgcd(18,30);

6

>

2) Transformer la procédure qui calcule le pgcd de deux nombres a et b de façon à obtenir les entiers u et v de l'egalité de Bezout i.e. trouver u, v tels que: pgcd(a,b)=au+bv.

> bezout:=proc(a::integer,b::integer)
local h,k,r,q,u1,u2,u3,v1,v2,v3;

h:=max(abs(a),abs(b));

k:=min(abs(a),abs(b));

u1:=1;v1:=0;

u2:=0;v2:=1;

while k >0 do

q:=iquo(h,k); r:=irem(h,k); #r=h-kq

u3:=u1-q*u2;

v3:=v1-q*v2;

u1:=u2; v1:=v2;

u2:=u3; v2:=v3;

h:=k;k:=r;

end do;

return (h,u1,v1);

end proc;

bezout := proc (a::integer, b::integer) local h, k, r, q, u1, u2, u3, v1, v2, v3; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); u1 := 1; v1 := 0; u2 := 0; v2 := 1; while 0 < k do q := iquo(h, k)...bezout := proc (a::integer, b::integer) local h, k, r, q, u1, u2, u3, v1, v2, v3; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); u1 := 1; v1 := 0; u2 := 0; v2 := 1; while 0 < k do q := iquo(h, k)...bezout := proc (a::integer, b::integer) local h, k, r, q, u1, u2, u3, v1, v2, v3; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); u1 := 1; v1 := 0; u2 := 0; v2 := 1; while 0 < k do q := iquo(h, k)...bezout := proc (a::integer, b::integer) local h, k, r, q, u1, u2, u3, v1, v2, v3; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); u1 := 1; v1 := 0; u2 := 0; v2 := 1; while 0 < k do q := iquo(h, k)...bezout := proc (a::integer, b::integer) local h, k, r, q, u1, u2, u3, v1, v2, v3; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); u1 := 1; v1 := 0; u2 := 0; v2 := 1; while 0 < k do q := iquo(h, k)...bezout := proc (a::integer, b::integer) local h, k, r, q, u1, u2, u3, v1, v2, v3; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); u1 := 1; v1 := 0; u2 := 0; v2 := 1; while 0 < k do q := iquo(h, k)...bezout := proc (a::integer, b::integer) local h, k, r, q, u1, u2, u3, v1, v2, v3; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); u1 := 1; v1 := 0; u2 := 0; v2 := 1; while 0 < k do q := iquo(h, k)...bezout := proc (a::integer, b::integer) local h, k, r, q, u1, u2, u3, v1, v2, v3; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); u1 := 1; v1 := 0; u2 := 0; v2 := 1; while 0 < k do q := iquo(h, k)...bezout := proc (a::integer, b::integer) local h, k, r, q, u1, u2, u3, v1, v2, v3; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); u1 := 1; v1 := 0; u2 := 0; v2 := 1; while 0 < k do q := iquo(h, k)...bezout := proc (a::integer, b::integer) local h, k, r, q, u1, u2, u3, v1, v2, v3; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); u1 := 1; v1 := 0; u2 := 0; v2 := 1; while 0 < k do q := iquo(h, k)...bezout := proc (a::integer, b::integer) local h, k, r, q, u1, u2, u3, v1, v2, v3; h := max(abs(a), abs(b)); k := min(abs(a), abs(b)); u1 := 1; v1 := 0; u2 := 0; v2 := 1; while 0 < k do q := iquo(h, k)...

> bezout(585,247);

13, -8, 19

> bezout(2,3);

1, 1, -1

>

Le crible d'Erathostène

Le but est de pouvoir générer l'ensemble des nombres premiers inférieurs à une certaine borne n (donnée). Le principe est le suivant : dans un tableau T de taille n (dont on initialise toutes les entrées à vrai), on se positionne sur le premier nombre premier 2 et on élimine l'ensemble des multiples de 2 jusqu'à n (par exemple en mettant chaque entrée T[x] pour un tel x à faux), puis on se positionne sur le prochain nombre premier disponible (ici 3) et on élimine tous ses multiples. On recommence jusqu'à atteindre n. Les éléments du tableau T qui restent à vrai à la fin seront tous les nombres premiers. Cette méthode s'appelle le crible d'Erathostène.

3) écrivez une procdure qui prend en entrée un nombre entier n et calcule l'ensemble des nombres premiers inférieurs à n (bien entendu, il est

interdit d'utiliser la fonction Maple "isprime").

> erath:=proc(n)
local l,i,p :

l:=array(1..n,[seq(evalb(i<>1),i=1..n)]):

i:=2:

for p to n do

if l[p] then

printf("%d is prime. ",p):

for i from 2*p to n by p do

l[i]:=false:

od:

fi:

od:

eval(l); end:

>

>

>

Arithmétique modulaire

Interpolation et arithmétique : les schémas à seuil

Ce problème est issu de la cryptographie. On cherche à partager un secret (un nombre) entre n individus de telle sorte que n'importe quelle coalition de  k (k<n) individus puisse en s'unissant reconstituer le secret mais que n'importe quel groupe de seulement (k-1) ne puisse pas le faire (et même ne puisse rien apprendre sur celui-ci). On retrouve cette problématique dans de nombreuses applications.

Un tel schémas de gestion/partage de secret s'appelle schéma à seuil. On procède de la façon suivante.

Soit P1,...,Pn les n participants. On se donne un secret s=a1 et un polynome Q=a1 + a2*X + a3*X^2 + ... +ak*X^{k-1} sur un corps fini de cardinal p (avec p premier p>n). On calcule n valeur de Q : Q(1), Q(2), ..., Q(n) et on distribue Q(i) au participant Pi, pour tout i.

Si k participants s'unissent en amenant leur part du secret (k valeurs du polynome), ils peuvent par interpolation (de Lagrange, par exemple) reconstiuter le polynome en entier et donc son premier coefficient a1.

Si seulement k-1 individus font la même chose, il existe, pour toute valeur du premier coefficient et toutes valeurs de Q en k-1 points donnés, un polynome passant par tous ces points. Donc, les k-1 individus n'apprennent rien sur le secret.

Vous devez dans cette partie implémenter plusieurs procédures permettant le partage de secret. Soit:

- une procédure créant, pour un secret a1 à cacher (et une valeur de k et n), un polynome aléatoire sur un corps de cardinal p>n (il faudra choisir un tel p premier et aussi p>a1). En sortie, la procédure donne n valeurs Q(1), ..., Q(n) (sous forme d'une liste ou d'un tableau).

-une procédure qui prend en entrée une liste de n couples [i,Q(i)] et en tire k au hasard (qu'elle redonne sous forme de liste). Ceci pour modéliser n'importe quelle coalition et les valeurs qui en découle.

- une procédure qui prenant des valeurs du polynome en k points, renvoie le premier coefficient (le secret, donc) du polynome de degré k-1 interpolé par ces points.

> genPoly:=proc(a1,n,k)
local p,Q,r, Qval;

r:=rand(n+a1..(n+a1)^2);

p:=nextprime(r());

Q:=Randpoly(k-1,x) mod p;

Q:=Q-eval(Q,x=0)+a1;

Qval:=[seq([i,eval(Q,x=i)mod p],i=1..n)];

return Qval,p;

#return r(),p;

end proc;

genPoly := proc (a1, n, k) local p, Q, r, Qval; r := rand(n+a1 .. (n+a1)^2); p := nextprime(r()); Q := `mod`(Randpoly(k-1, x), p); Q := Q-eval(Q, x = 0)+a1; Qval := [seq([i, `mod`(eval(Q, x = i), p)],...genPoly := proc (a1, n, k) local p, Q, r, Qval; r := rand(n+a1 .. (n+a1)^2); p := nextprime(r()); Q := `mod`(Randpoly(k-1, x), p); Q := Q-eval(Q, x = 0)+a1; Qval := [seq([i, `mod`(eval(Q, x = i), p)],...genPoly := proc (a1, n, k) local p, Q, r, Qval; r := rand(n+a1 .. (n+a1)^2); p := nextprime(r()); Q := `mod`(Randpoly(k-1, x), p); Q := Q-eval(Q, x = 0)+a1; Qval := [seq([i, `mod`(eval(Q, x = i), p)],...genPoly := proc (a1, n, k) local p, Q, r, Qval; r := rand(n+a1 .. (n+a1)^2); p := nextprime(r()); Q := `mod`(Randpoly(k-1, x), p); Q := Q-eval(Q, x = 0)+a1; Qval := [seq([i, `mod`(eval(Q, x = i), p)],...genPoly := proc (a1, n, k) local p, Q, r, Qval; r := rand(n+a1 .. (n+a1)^2); p := nextprime(r()); Q := `mod`(Randpoly(k-1, x), p); Q := Q-eval(Q, x = 0)+a1; Qval := [seq([i, `mod`(eval(Q, x = i), p)],...genPoly := proc (a1, n, k) local p, Q, r, Qval; r := rand(n+a1 .. (n+a1)^2); p := nextprime(r()); Q := `mod`(Randpoly(k-1, x), p); Q := Q-eval(Q, x = 0)+a1; Qval := [seq([i, `mod`(eval(Q, x = i), p)],...genPoly := proc (a1, n, k) local p, Q, r, Qval; r := rand(n+a1 .. (n+a1)^2); p := nextprime(r()); Q := `mod`(Randpoly(k-1, x), p); Q := Q-eval(Q, x = 0)+a1; Qval := [seq([i, `mod`(eval(Q, x = i), p)],...genPoly := proc (a1, n, k) local p, Q, r, Qval; r := rand(n+a1 .. (n+a1)^2); p := nextprime(r()); Q := `mod`(Randpoly(k-1, x), p); Q := Q-eval(Q, x = 0)+a1; Qval := [seq([i, `mod`(eval(Q, x = i), p)],...genPoly := proc (a1, n, k) local p, Q, r, Qval; r := rand(n+a1 .. (n+a1)^2); p := nextprime(r()); Q := `mod`(Randpoly(k-1, x), p); Q := Q-eval(Q, x = 0)+a1; Qval := [seq([i, `mod`(eval(Q, x = i), p)],...

> k:=8;n:=14;secret:=33;
X,p:=genPoly(secret,n,k);

k := 8

n := 14

secret := 33

X, p := [[1, 63], [2, 2], [3, 59], [4, 50], [5, 28], [6, 82], [7, 18], [8, 80], [9, 42], [10, 54], [11, 39], [12, 45], [13, 40], [14, 41]], 89

>
choixParmi:=proc(X,k)

local a;

with(combinat,randcomb):

if k > nops(X) then return printf('erreur'); end if;

randcomb(X, k);

end proc;

>

choixParmi := proc (X, k) local a; with(combinat, combinat:-randcomb); if nops(X) < k then return printf('erreur') end if; combinat:-randcomb(X, k) end proc

> X2:=choixParmi(X,k);

X2 := [[1, 63], [2, 2], [4, 50], [6, 82], [9, 42], [10, 54], [11, 39], [12, 45]]

> calculeSecret:=proc(X,p)
local secret,Absi,Ordo,P;

Ordo:=[seq(X[i][2],i=1..nops(X))];

Absi:=[seq(X[i][1],i=1..nops(X))];

P:=interp(Absi,Ordo,t) mod p;

secret:=coeff(P,t,0);

return Absi,Ordo,P,secret;

end proc;

calculeSecret := proc (X, p) local secret, Absi, Ordo, P; Ordo := [seq(X[i][2], i = (1 .. nops(X)))]; Absi := [seq(X[i][1], i = (1 .. nops(X)))]; P := `mod`(interp(Absi, Ordo, t), p); secret := coeff(...calculeSecret := proc (X, p) local secret, Absi, Ordo, P; Ordo := [seq(X[i][2], i = (1 .. nops(X)))]; Absi := [seq(X[i][1], i = (1 .. nops(X)))]; P := `mod`(interp(Absi, Ordo, t), p); secret := coeff(...calculeSecret := proc (X, p) local secret, Absi, Ordo, P; Ordo := [seq(X[i][2], i = (1 .. nops(X)))]; Absi := [seq(X[i][1], i = (1 .. nops(X)))]; P := `mod`(interp(Absi, Ordo, t), p); secret := coeff(...calculeSecret := proc (X, p) local secret, Absi, Ordo, P; Ordo := [seq(X[i][2], i = (1 .. nops(X)))]; Absi := [seq(X[i][1], i = (1 .. nops(X)))]; P := `mod`(interp(Absi, Ordo, t), p); secret := coeff(...calculeSecret := proc (X, p) local secret, Absi, Ordo, P; Ordo := [seq(X[i][2], i = (1 .. nops(X)))]; Absi := [seq(X[i][1], i = (1 .. nops(X)))]; P := `mod`(interp(Absi, Ordo, t), p); secret := coeff(...calculeSecret := proc (X, p) local secret, Absi, Ordo, P; Ordo := [seq(X[i][2], i = (1 .. nops(X)))]; Absi := [seq(X[i][1], i = (1 .. nops(X)))]; P := `mod`(interp(Absi, Ordo, t), p); secret := coeff(...calculeSecret := proc (X, p) local secret, Absi, Ordo, P; Ordo := [seq(X[i][2], i = (1 .. nops(X)))]; Absi := [seq(X[i][1], i = (1 .. nops(X)))]; P := `mod`(interp(Absi, Ordo, t), p); secret := coeff(...calculeSecret := proc (X, p) local secret, Absi, Ordo, P; Ordo := [seq(X[i][2], i = (1 .. nops(X)))]; Absi := [seq(X[i][1], i = (1 .. nops(X)))]; P := `mod`(interp(Absi, Ordo, t), p); secret := coeff(...

> calculeSecret(X2,p);

[1, 2, 4, 6, 9, 10, 11, 12], [63, 2, 50, 82, 42, 54, 39, 45], 62*t^7+7*t^6+9*t^5+22*t^4+40*t^3+6*t^2+62*t+33, 33

>