Les entiers et l’ordinateur

La représentation des nombres

L’écriture des nombres

On utilise un système de représentation dit de position (Gerbert

d’Aurillac (940-1003), pape Sylvestre II)

On choisit une base b ∈ N \ {0, 1}.

Alors ∀n ∈ N, ∃!(nk , ..., n0 ) ∈ {0, 1, 2, ...b − 1}k+1 tels que

k
X
n = nk . . . n3 n2 n1 n0 [b] = ni b i
i=0
Exemple de base

I Base dix et {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} :

9281 = 9 × 103 + 2 × 102 + 8 × 10 + 1

I Base deux et {0, 1} : 10010001 = 1 × 27 + 1 × 24 + 1

I Base hexadécimale (16) et

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C , D, E , F } :
D3C 2 = 13 × 163 + 3 × 162 + 12 × 16 + 2
Les entiers de l’ordinateur

Au sein de la machine, les nombres sont représentés en base 2, un

chiffre est appelé "bit" (binary digit, Claude Shannon, 1940) .
Un entier est codé sur un nombre fini k de bits (k = 8 à 64)
De ce fait, seuls les nombres strictement inférieurs à 2k sont
représentables.
Soit n = 39011 = 215 + 212 + 211 + 26 + 25 + 21 + 20 sur 16 bits,
se code en
1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

L’arithmétique est donc modulaire, modulo 2k .

Passage de la base 10 à la base b

On utilise la division euclidienne :

∀(a, b) ∈ N∗ 2 , ∃!(q, r ) ∈ N2 tels que a = bq + r avec 0 6 r < b

On note q = a/b et r = a%b

Algorithme :
i ←0
Tant que n > 0 faire
ni ← n%b
n ← n/b
i ←i +1
i ←0
Tant que n > 0 faire
ni ← n%b
n ← n/b
i ←i +1
Exemple : 1766 en base 7
Cas particulier de la base 2
On pourrra avoir intérêt à commencer par les puissances élevées :
2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Exemple : 2321
Cas particulier de la base 2 vers la base 16 et réciproquement

De la base 2 vers la base 16 : on groupe les bits par 4

101100110101100010010010100 [2] =
101 1001 1010 1100 0100 1001 0100 [2] = 59AC 494 [16]

De la base 16 vers la base 2, on développe chaque chiffre

hexadécimal.
7A5B1F 0F [16] = 0111 1010 0101 1011 0001 1111 0000 1111 [2]
Fin
Les entiers non-signés en C
En C, les entiers int et long int sont signés par défaut
On déclare un entier non-signé comme unsigned int
Un entier C non-signé codé sur k bits
I peut représenter les valeurs entre 0 et 2k − 1,
I respecte une arithmétique modulaire mod 2k
Sauf qu’on ne connaît pas k pour unsigned int.
Alors:
I mettre #include <stdint.h> et
I utiliser uint8_t, uint16_t, uint32_t ou uint64_t
Attention: les constantes entières sont signées par défaut !
⇒ Utiliser 2019u.
Effets de bord
Soit le programme C

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

void main()
{
uint16_t n=1;
int i;
for(i=1; i<10; i++)
{
n *= 10;
printf("i = %2d, n = %10d \n",i,n);
}
}
Effets de bord

i = 1, n = 10
i = 2, n = 100
i = 3, n = 1000
i = 4, n = 10000
i = 5, n = 34464
i = 6, n = 16960
i = 7, n = 38528
i = 8, n = 57600
i = 9, n = 51712

car 216 = 65536

Effets de bord

De même, avec uint32_t:

230 → 1073741824
231 → 2147483648
232 → 0
233 → 0

car 231 × 2 = 0 !!
Les entiers non-signés en C

Dans la machine, les entiers sont représentés en binaire c-à-d pour

42, on a bien l’octet 00101010 quelque part.

Mais: on programme en C, donc on a le droit d’écrire 42 en

décimal et c’est le compilateur qui se charge de la conversion.

Pour accéder au codage binaire, il faut utiliser les opérations de

masque et décalage.
Les masques
En C, pour deux valeurs uint32_t a, b
I a & b est le ET logique de tous les bits de a et de b
a = 42 = 00101010
b = 22 = 00010110
a & b = 2 = 00000010

I a | b est le OU logique de tous les bits de a et de b

a = 42 = 00101010
b = 22 = 00010110
a | b = 62 = 00111110

I Avec un tel masque & on peut donc accéder aux différents bits
d’un entier en C:
I a & 1u est non-nul ssi a a son bit à droite à 1
I a & 2u est non-nul ssi a a son bit de poids 1 à 1
I a & 4u est non-nul ssi a a son bit de poids 2 à 1
I ...
Les décalages

En C, pour une valeur uint32_t a et un entier b

I a « b a les mêmes bits que a décalés de b bits à gauche
a = 42 = 00101010
a « 2 = 168 = 10101000

I a » b a les mêmes bits que a décalés de b bits à droite

a = 68 = 01000100
a » 2 = 17 = 00010001

I Les bits en trop à gauche ou à droite disparaissent.

I 1u « k a un seul bit à 1 à la k-ième position

⇒ a & (1u « k) est non-nul ssi a a son bit de poids k à 1.
Les décalages et les masques

I De la même façon qu’on peut abréger a = a + b en a += b,

on peut abréger a = a & b en a &= b,
a = a | b en a |= b,
a = a » b en a »= b et
a = a « b en a «= b.
Fin
Les entiers signés en C
Pour représenter des entiers signés (i.e. les entiers relatif de Z, on
utilise le complément à deux.
Plus précisement, sur k bits
1 - si n ∈ 0; 2k−1 − 1 , n est codé tel quel sur k − 1 bits,
 

2 - n ∈ −2k−1 ; −1 ,on code 2k + n ∈ 2k−1 ; 2k − 1 donc le bit

   

de gauche vaut 1.

I Accès au signe facile: prendre le bit à gauche

I Une représentation unique
I Rien n’est à changer dans les algorithmes pour +, −, <.
C’est la représentation utilisée dans les processeurs actuels.
Pour passer du codage de n > 0 au codage de −n (et inversement)
sur k bits, on va au premier bit non nul par la droite. On ne touche
pas à ce bit puis on inverse tous les autres bits sur la gauche..
Soit n = 0ak−2 ...ak0 10...0 [2].
Quelques exemples d’opérations.
On travaille sur 8 bit.
Soit a = 57 = 0011 1001 [2] et b = 44 = 0010 1100 [2]
28 − a = 199 = 1100 0111 [2] et 28 − b = 212 = 1101 0100 [2]

57 = 0011 1001 28 − 57 = 199 = 1100 0111

44 = 0010 1100 28 − 44 = 212 = 1101 0100
101 = 0110 0101 28 − 101 = 155 = 1001 1011

57 = 0011 1001 28 − 57 = 199 = 1100 0111

8
2 − 44 = 212 = 1101 0100 44 = 0010 1100
13 = 00001101 28 − 13 = 243 = 1111 0011
Les entiers signés de l’ordinateur
Pour passer à la ligne suivante, on ajoute 1 sur le premier bit et on
propage la rétenue.
écritures binaire valeurs absolues valeurs signées
0000000000000000 0 0
0000000000000001 1 1
0000000000000010 2 2
0000000000000011 3 3
... ... ...
0111111111111110 215 − 2 215 − 2
0111111111111111 215 − 1 215 − 1
1000000000000000 2 = 216 − 215
15 −215
1000000000000001 215 + 1 −(215 − 1)
... ... ...
1111111111111110 216 − 2 −2
1111111111111111 216 − 1 −1
Les entiers signés en C

En C, les entiers int et long int sont signés par défaut

Un entier C signé
I peut représenter les valeurs entre −2k−1 et 2k−1 − 1,
I respecte une arithmétique modulaire mod 2k
Pour autant, il est préférable d’éviter d’utiliser int et long int
pour garantir une portabilité optimale du code.
Alors:
I mettre #include <stdint.h> et
I utiliser int8_t, int16_t, int32_t ou int64_t
Rappel: les constantes entières sont signées par défaut.
Second effet de bord
Soit le programme C

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

void main()
{
int16_t n=1;
int i;
for(i=1; i<10; i++)
{
n *= 10;
printf("i = %2d, n = %10d \n",i,n);
}
}
Second effet de bord

i = 1, n = 10
i = 2, n = 100
i = 3, n = 1000
i = 4, n = 10000
i = 5, n = -31072
i = 6, n = 16960
i = 7, n = -27008
i = 8, n = -7936
i = 9, n = -13824

car 216 = 65536

Fin
L’algorithme d’Euclide et le théorème chinois des restes
Rappels de maths et PGCD
Rappels de math
Division Euclidienne :
∀(a, b) ∈ Z × N∗ , ∃!(q, r ) ∈ Z × N tels que a = bq + r avec 0 ≤ r < b
Z est un anneau principal : les seuls idéaux de Z sont les
nZ = {nq, q ∈ Z}
On dit que a est congru à c modulo b et on écrit

a≡c (mod b) ⇔ (a − c) ∈ bZ

la relation ≡ est stable par addition et multiplication

a1 ≡ c1 (mod b) et a2 ≡ c2 (mod b) ⇒ a1 + a2 ≡ c1 + c2 (mod b)
a1 ≡ c1 (mod b) et a2 ≡ c2 (mod b) ⇒ a1 × a2 ≡ c1 × c2 (mod b)

la relation ≡ est une relation d’équivalence

Z/nZ est un anneau commutatif
Rappels de math

On dit que b divise a ssi a ∈ bZ

Le plus grand commun diviseur d de a et b, noté pgcd(a, b), est
défini par
aZ + bZ = dZ

donc si d = pgcd(a, b) alors (identité de Bézout)

∃(u, v ) ∈ Z2 tels que au + bv = d

a et b sont dit premier entre eux ssi pgcd(a, b) = 1.

Z/nZ est un corps ssi n est premier.
Calcul du PGCD à base de soustraction
L’algorithme est basé sur la remarque suivante :
si a > b alors pgcd(a, b) = pgcd(a − b, b)
Entrées A et B
Sortie U le pgcd de A et de B
Corps
U←A
V ←B
Tant que V > 0 faire
Si V > U alors
T ← V , V ← U, U ← T
U ←U −V
Invariant de boucle : U ≥ V et pgcd(U, V ) = pgcd(U − V , V )
Terminaison : si V = 0 alors U = pgcd(U, V )
Exemple
U V U-V
1479 699 780
780 699 81
699 81 618
618 81 537
... ... ...
213 81 132
132 81 51
81 51 30
51 30 21
30 21 9
21 9 12
12 9 3
9 3 6
6 3 3
3 3 0
3 0
Calcul du PGCD à base de division

Entrées A et B
Sortie U le pgcd de A et de B
Corps
U←A
V ←B
Tant que V > 0 faire
T ← U%V
U←V
V ←T
Le PGCD
Algoritme à base de division : exemple

U V U%V
1479 699 81
699 81 51
81 51 30
51 30 21
30 21 9
21 9 3
9 3 0
3 0
Fin
l’algorithme d’Euclide étendu
Rappels de math

Identité de Bézout : Soient a et b deux entiers, il existe deux

entiers u et v tels que : a × u + b × v = pgcd(a, b)
Remarque 1 : a et b premiers entre eux ⇔ a × u + b × v = 1
Remarque 2 : a × u + b × v = 1
⇒ a−1 ≡ u (mod b) et b −1 ≡ v (mod a)
L’algorithme d’Euclide étendu

Le but est de calculer les coefficients de Bézout :

u1 × a + u2 × b = u3 = pgcd(a, b)

Entrées : a et b
Sortie : u1 × a + u2 × b = u3 = pgcd(a, b)
(u1 , u2 , u3 ) ← (1, 0, a)
Initialisation :
(v1 , v2 , v3 ) ← (0, 1, b)
Itération : tant que v3 6= 0
q = u3 /v3
(t1 , t2 , t3 ) ← (u1 , u2 , u3 ) − q × (v1 , v2 , v3 )
(u1 , u2 , u3 ) ← (v1 , v2 , v3 )
(v1 , v2 , v3 ) ← (t1 , t2 , t3 )
Exemple

On veut calculer le pgcd et les coefficients de Bézout pour a = 391

et b = 276.

u1 u2 u3 v1 v2 v3 q t1 t2 t3
1 0 391 0 1 276 1 1 −1 115
Exemple

On veut calculer le pgcd et les coefficients de Bézout pour a = 391

et b = 276.

u1 u2 u3 v1 v2 v3 q t1 t2 t3
1 0 391 0 1 276 1 1 −1 115
0 1 276 1 −1 115 2 −2 3 46
Exemple

On veut calculer le pgcd et les coefficients de Bézout pour a = 391

et b = 276.

u1 u2 u3 v1 v2 v3 q t1 t2 t3
1 0 391 0 1 276 1 1 −1 115
0 1 276 1 −1 115 2 −2 3 46
1 −1 115 −2 3 46 2 5 −7 23
Exemple

On veut calculer le pgcd et les coefficients de Bézout pour a = 391

et b = 276.

u1 u2 u3 v1 v2 v3 q t1 t2 t3
1 0 391 0 1 276 1 1 −1 115
0 1 276 1 −1 115 2 −2 3 46
1 −1 115 −2 3 46 2 5 −7 23
−2 3 46 5 −7 23 2 −12 17 0
Exemple

On veut calculer le pgcd et les coefficients de Bézout pour a = 391

et b = 276.

u1 u2 u3 v1 v2 v3 q t1 t2 t3
1 0 391 0 1 276 1 1 −1 115
0 1 276 1 −1 115 2 −2 3 46
1 −1 115 −2 3 46 2 5 −7 23
−2 3 46 5 −7 23 2 −12 17 0
5 −7 23 −12 17 0

donc l’identité de Bézout s’écrit

5 ∗ 391 − 7 ∗ 276 = 23 et pgcd(391, 276) = 23.

Fin
 Le théorème chinois des reste

Il apparaitrait pour la première fois dans le livre de Sun Zi, le Sunzi

suanjing, datant du IIIe siècle
Théorème chinois des restes

Étant donné des entiers (moduli) m1 , . . . , mn premiers entre eux

deux à deux et des restes associés a1 , . . . , an , on cherche à résoudre
le système de congruences


 x ≡ a1 mod m1
 x ≡ a2

mod m2
..


 .
x ≡ an mod mn


où x est l’inconnue.
Les outils mathématiques :
Si a et premier avec b et premier avec c alors a est premier avec bc.
Les outils mathématiques :
Si a est premier avec b et premier avec c alors a est premier avec
bc.
Si m est premier, ∀a, ∃b tel que ab ≡ 1 (mod m)
Les outils mathématiques :
Si a est premier avec b et premier avec c alors a est premier avec
bc.
Si m est premier, ∀a, ∃b tel que ab ≡ 1 (mod m)
Si m1 et m2 sont premiers entre eux et que a est un multiple de m1
et de m2 alors a est un multiple de m1 × m2 .
Étude Théorique



 x ≡ a1 mod m1
 x ≡ a2

mod m2
..


 .
x ≡ an mod mn


Qn
Théoreme : Soit M = i=1 mi et Mi = M
mi , soit yi = Mi−1
(mod mi ) alors
n
X
y= ai × yi × Mi
i=1

est une solution du système modulaire et l’ensemble des solutions

est S = {y + k × M, k ∈ Z}
Démonstration

Vérifions que ∀1 ≤ i ≤ n, y ≡ ai (mod mi )

Qn
D’abord, si i 6= j, Mj ≡ 0 (mod mi ) car Mj = k=1,k6=j mk est un
multiple de mi .

Donc, soit 1 ≤ i0 ≤ n,
n
X
ak × yk × Mk ≡ ai0 × yi0 × Mi0 (mod mi0 )
k=1

Par définition,
yi0 × Mi0 ≡ 1 (mod mi0 )
donc
y ≡ ai0 (mod mi0 )
Démonstration suite

Supposons que y et z soient deux solutions du systèmes

modulaires. On a

y ≡ a1 mod m1 z ≡ a1 mod m1
y ≡ a2 mod m2 z ≡ a2 mod m2
.. et .
. ..
y ≡ an mod mn z ≡ an mod mn

y −z ≡ 0 mod m1
y −z ≡ 0 mod m2
Et donc ..
.
y −z ≡ 0 mod mn
Donc y − z est un multiple de mi , ∀i
donc y − z est un multiple de M.
Algorithme
On résout le système de proche en proche.

Entrées m1 , . . . , mn des moduli premiers entre eux

a1 , . . . , an des entiers restes
Sortie x resolvant le système de congruences
Corps
M ← m1
x ← a1
Pour i = 2, . . . , n faire
Euclide étendu: calculer (u, v ) tq.
u mi + v M = 1
x ← u mi x + v M ai
M ← mi M
x ← x mod M
Application

Une jeune fille portait un panier rempli d’œufs. Un chevalier passa avec son
cheval et toucha le panier, qui tomba par terre et tous les œufs se cassèrent. Il
voulut dédommager la fille et il lui demanda combien d’œufs elle avait eu.
Elle ne sut plus dire leur nombre mais elle se rappela que quand elle les avait
comptés par paires, un œuf était resté seul, que quand elle avait compté par
triplets, deux étaient restés et quand elle les avait arrangés par groupes de cinq,
quatre étaient restés. Finalement, quand elle les avait comptés par groupes de
sept, aucun œuf n’était resté à côté.
Alors le chevalier répondit: maintenant je sais combien d’œufs il y avait.
Brahmagupta, VIIe siècle

x ≡ 1 mod 2
x ≡ 2 mod 3
x ≡ 4 mod 5
x ≡ 0 mod 7
 x ≡ 1 mod 2
x ≡ 2 mod 3
x ← u mi x + v M ai
x ≡ 4 mod 5
x ≡ 0 mod 7
On organise les calculs dans un tableau comme suit:
i mi ai M u v x x mod M
1 2 1 2 1 1
2
3
4
x ≡ 1 mod 2
x ≡ 2 mod 3
x ← u mi x + v M ai
x ≡ 4 mod 5
x ≡ 0 mod 7

i mi ai M u v x x mod M
1 2 1 2 1 1
2 3 2 6 1 −1 −1 −1
3
4
x ≡ 1 mod 2
x ≡ 2 mod 3
x ← u mi x + v M ai
x ≡ 4 mod 5
x ≡ 0 mod 7

i mi ai M u v x x mod M
1 2 1 2 1 1
2 3 2 6 1 −1 −1 −1
3 5 4 30 −1 1 29 −1
4
x ≡ 1 mod 2
x ≡ 2 mod 3
x ← u mi x + v M ai
x ≡ 4 mod 5
x ≡ 0 mod 7

i mi ai M u v x x mod M
1 2 1 2 1 1
2 3 2 6 1 −1 −1 −1
3 5 4 30 −1 1 29 −1
4 7 0 210 −17 4 119
Fin