Introduction a la Cryptologie Chapitre Arithmetique des nombres entiers

Michael Eisermann

Description

Niveau: Supérieur, Master
Introduction a la Cryptologie Chapitre 2 : Arithmetique des nombres entiers Michael Eisermann (Institut Fourier, UJF Grenoble) Annee 2008-2009 IF / IMAG, Master 1, S1-S2 document mis a jour le 7 juillet 2009FOURIERINSTITUTfi www-fourier.ujf-grenoble.fr/~eiserm/cours _ crypto 1/41

• numeration romaine


• arithmetiques


• fourierinstitutfi www-fourier


• division euclidienne des entiers


• cout en temps et en memoire


• etablir des algorithmes pour les operations arithmetiques

Sujets

• Numération romaine

Informations

• Publié par: profil-infoe-2012
• Nombre de lectures: 12
• Langue: Français

Extrait

Introduction ` alaCryptologie Chapitre2:Arithm ´ etiquedesnombresentiers

Michael Eisermann (Institut Fourier, UJF Grenoble)

Anne´ e  2008-2009 IF / IMAG, Master 1, S1-S2

document mis a` jour le 7 juillet 2009

www-fourier.ujf-grenoble.fr/~eiserm/cours # crypto

/114

Objectifs

Questions de base : 1 Qu’est-ce que les nombres entiers ? 2 Comment les implementer sur ordinateur ? ´

D ´ eveloppementmathe ´ matique: Retracer le fondement axiomatique. De ´ finirlesop ´ erationsarithme ´ tiquesete ´ tablirleurspropri ´ ete ´ s. Introduire notamment la division euclidienne des entiers.

De´ veloppement  algorithmique : Lanume ´ rationpositionnelleestunerepr ´ esentationefficace. ´ Etablirdesalgorithmespourlesope ´ rationsarithm ´ etiques. Estimerleurcomplexite ´ :coˆutentempsetenm ´ emoire.

2/41

Sommaire

1

2

3

4

5

6

Remarques historiques

Langage mathematique ´

Les nombres naturelsN

Imple´ mentation  artisanale

Les nombres entiersZ

Impl ´ ementationsprofessionnelles

/314

Qu’est-ce que les nombres naturels ?

Nume´ ration romaine utilise´  e  jusqu’au moyen aˆ  ge :

I, II, III, IV, V, V I, V II, V III, IX, X, . . .

Num ´ erationindo-arabeutilis ´ eedenosjours:

0,1,2,3,4,5,6,7,8,9,10, . . .

Quatreop ´ erationsarithm ´ etiques:

DXXXVII537 +LXXIX+79 DMXVI616

XLIII43 ×LXXIX×79 MMMXXXIIIX3397

MMVIII2008 −LXXIX−79 MCMXXIX1929

MMMXXXIIIX3397 ÷LXXIX÷79 XLIII43

Ceci n’est pas unefinitd ´ eoin: il ne s’agit qued’exemples.

/414