Télécharger cette partie

pages

Français

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-urra-2012

Nombre de lectures

Langue

Français

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

Voir

Publié par

profil-urra-2012

Nombre de lectures

Langue

Français

Arithm´etiqueAlogirhtimuqe

Arithme´tique

Algorithmique

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

Arithme´tique

Algorithmique

Partie

Algorithmes

classiques

Arithm´etiqu

elAogirhtimuqe

Couˆtdelamultiplicationetdeladivision

Exponentiation rapide

Algorithme d’Euclide

Algorithmed’Euclidee´tendu

Reconstruction d’un nombre rationnel

Carre´sdansFp de Legendre-Jacobi: symbole

Carre´sdansFp: calcul des racin ´ es carrees

L’algorithme LLL

Quelques applications de LLL

Entiersdetailled´ecroissante.Soienta1, . . . aketb1, . . . , bkdes entiers (disons positifs) tels quea1, . . . , ak≤NetQibi≤N. Alors le cout ˆ pour faire toutes les multiplications desaipar lesbi, ou toutes les divisions desaiavec lesbipour quotients, est O(loga1logb1) +∙ ∙ ∙+O(logaklogbk)⊂O((logN)(logb1+∙ ∙ ∙logbk)) =O((logN)(logb1∙ ∙ ∙bk))⊂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´thqitelAeuirogimhtnoisividumtledalˆotuuqCedelaonetcatiipli

rAithmxEe´ptoqinueetniAaltgioornitrhampiqiduee

Exponentiation rapide

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

Remarques.nedohte´Mneedona¨ıvO(nsdsnaitnoe´ar)opG. Quittea`remplacergparg−1, on peut supposern≥0. Ecriture binaire.O´tnicren=Pii2iaveci= 0 ou 1, on a alors ´ gn=Yg2i. i=1 Au plusO(logn) multiplications dansGetg2i+1g2i2. =