Télécharger cette partie

Description

Arithmetique Algorithmique Arithmetique Algorithmique

• symbole de legendre-jacobi


• ecriture binaire


• bi pour quotients


• calcul des racines carrees


• cout de la multiplication et de la division


• entiers de taille decroissante

Informations

• Publié par: profil-urra-2012
• Nombre de lectures: 27
• Langue: Français

Extrait

Arithm´etiqueAlogirhtimuqe

Arithme´tique

Algorithmique

http://www.math.univ-lyon1.fr/~roblot/ens.html

Arithme´tique

Algorithmique

Partie

Algorithmes

I

I

I

classiques

Arithm´etiqu

1

2

3

4

5

6

7

8

9

elAogirhtimuqe

Couˆtdelamultiplicationetdeladivision

Exponentiation rapide

Algorithme d’Euclide

Algorithmed’Euclidee´tendu

Reconstruction d’un nombre rationnel

Carre´sdansF p  de Legendre-Jacobi: symbole

Carre´sdansF p : calcul des racin ´ es carrees

L’algorithme LLL

Quelques applications de LLL

Entiersdetailled´ecroissante.Soienta 1 , . . . a k etb 1 , . . . , b k des entiers (disons positifs) tels quea 1 , . . . , a k ≤Net Q i b i ≤N. Alors le cout ˆ pour faire toutes les multiplications desa i par lesb i , ou toutes les divisions desa i avec lesb i pour quotients, est O(loga 1 logb 1 ) +∙ ∙ ∙+O(loga k logb k )⊂O((logN)(logb 1 +∙ ∙ ∙logb k )) =O((logN)(logb 1 ∙ ∙ ∙b k ))⊂O((logN) 2 ).

O(logalogb)⊂O((logN) 2 )

op´erationsbinairesavec|a|,|b| ≤N.

Couˆtdelamultiplicationetdeladivision

Convention.iluteshms´eisttecrapeere`snadlgsaitoreqtileueOnconsid pour la division et la multiplication sont les algorithmes classiques et donc la multiplication entre deux entiersaetbou la division deaavecb commequotientcoˆute

riAm´thqitelAeuirogimht noisividumtledalˆotu uq C e delaonetcatiipli

rAithm xE e´ p t o qi n u e e tni A a l t g i o o r n it r h a m pi qi d u e e

Exponentiation rapide

Probl`me.PourGgroupe,g∈Getn∈Z, on veut calculerg n . e

Remarques.nedohte´Mneedona¨ıvO(nsdsnaitnoe´ar)opG. Quittea`remplacergparg −1 , on peut supposern≥0. Ecriture binaire.O´tnicren= P i  i 2 i avec i = 0 ou 1, on a alors ´ g n = Y g 2 i .  i =1 Au plusO(logn) multiplications dansGetg 2 i+1  g 2 i  2 . =

Algorithme. (1)Poserh←1 G ,t←g (2)Sin= 0 alors retournerh (3)Sinest impair alors poserh←h∙t (4)Fairen← bn/2c,t←t 2 et retourner en (2)