Licence de Mathématiques L3 Algèbre effective

Description

Niveau: Supérieur, Licence, Bac+3
Licence de Mathématiques 2008--2009 L3 Algèbre effective td 2 : Inversibles modulo m, Calcul rapide de puissances Inversibles modulo m Calcul rapide de puissances Dans la suite on aura besoin de calculer des puissances modxn m avec , ,x n m entiers de grande taille. On a donc besoin d'un algorithme de calcul efficace. Exercice 6 : écrire une fonction qui rende xn en utilisant l'algorithme de calcul rapide de puissances expliqué en cours. Comparer graphiquement la vitesse de l'algorithme naïf par multiplications successives et de celui-ci. Solution > exponaif:=proc(x,n) local i,res; res:=1; for i from 1 to n do res:=res*x od; res end; exponaif := proc( ) end proc,x n local ;,i res ; ; := res 1 for to do end doi n := res ?res x res On initialise res à 1 et non à x pour que cette fonction marche quand n = 0. > exponaif(11,3),exponaif(11,0); ,1331 1 L'algorithme rapide : > exporap:=proc(x,n) if n=0 then 1 elif irem(n,2)=0 then exporap(x*x,iquo(n,2)) else x*exporap(x*x,iquo(n-1,2)) fi end; exporap ,x nproc( ) := =n 0 1if then =( )irem ,n 2

• puissances modulo


• then


• vitesse de l'algorithme naïf par multiplications successives


• vitesse de l'algorithme de l'exercice


• algorithme de calcul rapide de puissances


• exponaif:=proc


• elif irem

Informations

• Publié par: thieg
• Nombre de lectures: 20
• Langue: Français

Extrait

Licence de Mathématiques 2008--2009

L3 Algèbre effective

td 2 : Inversibles modulo m, Calcul rapide de puissances

Inversibles modulo m

Calcul rapide de puissances

Dans la suite on aura besoin de calculer des puissances

mod

x

n

m

avec ,

,

x n m

entiers de grande

taille. On a donc besoin d’un algorithme de calcul efficace.

Exercice 6 : écrire une fonction qui rende

x

n

en utilisant l’algorithme de calcul rapide de

puissances expliqué en cours.

Comparer graphiquement la vitesse de l’algorithme naïf par multiplications successives et de

celui-ci.

Solution

>

exponaif:=proc(x,n)

local i,res;

res:=1;

for i from 1 to n do res:=res*x od;

res

end;

exponaif

:=

proc

(

)

end proc

,

x n

local

;

,

i res

;

;

:=

res

1

for

to

do

end do

i

n

:=

res

*

res x

res

On initialise res à 1 et non à x pour que cette fonction marche quand n = 0.

>

exponaif(11,3),exponaif(11,0);

,

1331 1

L’algorithme rapide :

>

exporap:=proc(x,n)

if n=0 then 1

elif irem(n,2)=0 then exporap(x*x,iquo(n,2)) else

x*exporap(x*x,iquo(n-1,2)) fi

end;

exporap

,

x n

proc

(

)

:=

=

n

0

1

if

then

=

(

)

irem

,

n

2

0

(

)

exporap

,

^

x

2

(

)

iquo

,

n

2

elif

then

*

x

(

)

exporap

,

^

x

2

(

)

iquo

,

-

n

1 2

else

end if

end proc

Les mesures :

>

s1:=NULL: for i to 10 do t:=time(): exponaif(11,3^i):

t:=time()-t: s1:=s1,[i,t] od: s1;

[

]

,

1 0.016

[

]

,

2 0.009

[

]

,

3 0

[

]

,

4 0

[

]

,

5 0.008

[

]

,

6 0.035

[

]

,

7 0.310

[

]

,

8 2.385

,

,

,

,

,

,

,

,

[

]

,

9 21.383

[

]

,

10 191.275

,