Arithmétique des entiers, base64 et algorithme d'Euclide

11 avril 2020 — Introduction, Python

Les entiers naturels, pour compter avec nos doigts

Les entiers naturels $\N$, c’est l’ensemble des nombres suivants : $0, 1, 2, 3, ...$

Ils portent plutôt bien leur nom, car ils sont effectivement très intuitifs et tout le monde comprend leur sens : ce sont ceux que l’on utilise pour compter des objets.

Divisibilité

On dit qu’un entier $a$ est divisible par un entier $b, b \neq 0$ s’il existe un entier $k$ tel que $a = k \times b$.

On peut visualiser ce concept comme la possibilité de regrouper par lots. Par exemple, $6$ est divisible par 2 et par 3 :

$🍋🍋🍋🍋🍋🍋 = 🍋🍋+🍋🍋+🍋🍋 = 🍋🍋🍋+🍋🍋🍋$

Les nombres premiers

Parmi ces nombres, certains ont une propriété particulière.

Un nombre premier est un nombre qui ne se casse pas quand on le laisse tomber par terre. (P. Erdős)

Un entier $n \isin \N$ est dit premier s’il n’admet que deux diviseurs : $1$ et $n$ lui-même ($1$ n’est pas considéré premier).

Par exemple, les nombres $2, 3, 5, 7, 11$ sont premiers : pour vous en convaincre, essayez de ranger cinq 🍋 en lots de $2$, $3$ ou $4$.

La division euclidienne

Si vous prenez un nombre $a$ d’objets, et essayez de les répartir entre $b$ personnes, il n’est pas sûr que vous puissiez y arriver. Par exemple, si ${a = 8}$ et ${b = 3}$, vous allez en donner un au premier, le suivant au second, etc. et il va vous en rester deux dans les mains après avoir partagé les six premiers, car ${8 = 3 \times 2 + 2}$.

La division euclidienne généralise ce procédé.

$a$ et $b$ étant des entiers naturels, avec $b \neq 0$, il existe des entiers naturels $q$ (quotient) et $r$ (reste) uniques vérifiant :
$a = b \times q + r$ et $0 \leq r \lt b$

Je laisse le lecteur vérifier que si une telle décomposition existe, alors elle est unique. Pour montrer son existence, une approche est de décrire un algorithme pour obtenir $q$ et $r$.

💻 L’algorithme Python ci-dessous permet d’obtenir cette décomposition (note: cet algorithme n’est pas optimal).

def euclidean_division(a, b):
    q, r = 0, a
    while r >= b:
        r -= b
        q += 1
    return (q, r)
>>> euclidean_division(8, 3)
(2, 2)      # 8 = 3 * 2 + 2
>>> euclidean_division(2020, 51)
(39, 31)    # 2020 = 51 * 39 + 31

On vérfie que l’égalité $a = b \times q + r$ est un invariant de boucle car à chaque itération $r$ décroit de $b$ et $q$ augmente de $1$.

Ceci permet de prouver que cet algorithme termine après un nombre fini d’itérations et donne un résultat vérifiant les conditions requises. Mathématiquement, c’est une preuve de l’existence pour notre théorème de division euclidienne.

Questions Python :

• Que se passe-t-il si on exécute euclidean_division(42, 0) ?
  Quelle exception Python pourrait-on utiliser pour gérer ce cas ?
• Quels opérateurs natifs de Python peut-on utiliser pour obtenir q et r ?

Les entiers relatifs $\Z$

Comme vous le savez, nous utilisons aussi des nombres négatifs.

💡 D’un point de vue axiomatique, ces nombres peuvent être définis comme des différences : $-3$ est le nombre qui permet de passer de $10$ à $7$, ou de façon équivalente de $25$ à $22$ (en savoir plus).

On note l’ensemble des nombres entiers relatifs (positifs, négatifs ou nuls) $\Z$ :
$\Z = \{..., -3, -2, -1, 0, 1, 2, 3, ...\}$

Les entiers relatifs contiennent les entiers naturels, ce qu’on note : $\N \subset \Z$.

La division euclidienne existe toujours dans $\Z$, mais le quotient peut être négatif.

💻 En exercice, vous pouvez essayer d’adapter la fonction euclidean_division précédente pour qu’elle fonctionne avec $a, b \isin \Z$.

Les bases numériques

Nous avons l’habitude d’écrire les nombres en base 10, avec dix chiffres différents $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$.

Ce choix est pratique, il permet de compter avec ses mains.

Pour des raisons qui relèvent principalement de l’électronique, le choix de la base $2$ (binaire) s’est imposé pour représenter les nombres en informatique (en mémoire, dans les canaux d’échange, etc.).

Ce choix a des conséquences importantes sur lesquelles nous reviendrons.

Le programme ci-dessous permet d’afficher la liste des chiffres d’un entier $n \isin \N$, en base décimale, en commençant par le poids le plus faible. Il n’a évidemment pas d’intérêt autre que didactique, cette fonctionnalité étant native dans tous les langages.

def show_decimals(n):
    while n > 0:
        n, r = euclidean_division(n, 10)
        yield r
>>> print(list(show_decimals(123)))
[3, 2, 1]

Questions :

• Pourquoi ce programme termine bien ?
• Modifier le programme pour obtenir la décomposition d’un nombre en base héxadécimale (base 16 avec les chiffres 0123456789abcdef)

Le cas de la base 64

Pour coder des données binaires dans un document texte (par exemple, des images directement dans le code HTML), le codage base64 est souvent utilisé. Concrètement, cela consiste à utiliser les 64 caractères suivant comme chiffres, chacun pouvant encoder 6 bits d’information ($64 = 2^6$) :

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Le flux de données à encoder étant généralement des octets, l’implémentation présente toutefois quelques subtilités :

• Les octets sont regroupés par blocs de 3, c’est-à-dire 24 bits (car 24 est le plus petit multiple simultané de 8 et 6…)
• Chacun de ces blocs est représenté par 4 caractères base64
• Lorsque les données à encoder ne peuvent pas être regroupées par paquets de 3 octets (ex.: 4 caractères ASCII, sur 4 octets), un symbole = est ajouté à la fin de la chaîne encodée pour chaque octet manquant (pour arriver à un nombre multiple de 3)
• Une conséquence de ce fonctionnement, est que le contenu encodé en base64 prend plus de place en mémoire que le contenu d’origine, d’un facteur moyen $4 / 3$

Par exemple, en utilisant la librairie b64encode :

from base64 import b64encode
>>> b64encode(b"foo")
'Zm9v'
>>> b64encode(b"Je pense donc je suis.")
'SmUgcGVuc2UgZG9uYyBqZSBzdWlzLg=='

Questions :

• Combien de symboles = y aura-t-il en fin de chaîne pour b64encode(b"a") ?

• Même question avec b64encode("à".encode("utf-8")) ?

• L’algorithme Base85 encode les séquence de 32 bits en séquences de $N$ caractères, utilisant un alphabet de $85$ caractères.
  Quelle est la valeur minimale pour $N$ ?

  Une variante de cet algorithme est utilisée par ZeroMQ.

PGCD et identité de Bézout

On appelle PGCD (plus grand commun diviseur) de deux entiers non nuls $a$ et $b$ (noté $\gcd(a,b)$) le plus grand entier qui divise simultanément $a$ et $b$.

Par exemple :

• $\gcd(2, -4) = 2$
• $\gcd(24, 40) = 8$
• $\gcd(2020, 13) = 1$ ($13$ est premier)

Le résultat qui suit est plus compliqué que la division euclidienne. Si vous avez des difficultés à l’appréhender, c’est tout à fait normal. Il est néanmoins à la base d’une bonne partie de l’arithmétique des entiers et sa preuve peut aussi se faire via un algorithme, raison de plus pour en parler ici 😊

Identité de Bézout

Il existe deux nombres ${u, v \isin \Z}$ tels que : ${u \times a + v \times b = \gcd(a, b)}$

Par exemple : ${ -3 \times 24 + 2 \times 40 = 8 = \gcd(24, 40)}$

L’algorithme d’Euclide permet de calculer le PGCD de deux nombres par une méthode itérative, et l’analyse de son fonctionnement met en évidence l’identité de Bézout.

En voici une implémentation en Python :

def gcd(a, b):
    while b != 0:
        q, r = euclidean_division(a, b)
        a, b = b, r
    return a

Analyse de l’algorithme :

• À chaque étape de la boucle, $a$ et $b$ prennent de nouvelles valeurs $a_{n+1}$ et $b_{n+1}$, avec$a_{n+1} = b_n \newline b_{n+1} = a_n - b_n \times q$On en déduit en particulier qu’à chaque iteration :
  • $0 \leq b_{n+1} < b_n$
  • $\gcd(a_{n+1}, b_{n+1}) = \gcd(a_n, b_n)$ — vérifier que tout diviseur commun d’une paire l’est aussi pour l’autre
  • $a_n$ et $b_n$ sont de la forme ${u \times a + v \times b}$ où $u_n$ et $v_n$ sont des entiers
• Ceci nous permet de conclure que l’algorithme termine ($b_{n+1} = 0$ se produit en un nombre fini d’itérations), que la valeur retournée est bien de la forme ${u \times a + v \times b}$.
  Il s’agit bien du PGCD car on a alors $\gcd(a_{n+1}, 0) = \gcd(a, b)$.

Quelques résultats d’arithmétique

Pour finir, nous allons énoncer deux résultats fondamentaux sur la structure des nombres entiers. Un lemme préalable est utile pour les démontrer.

Lemme d’Euclide

Si un nombre premier $p$ divise $a \times b$, alors $p$ divise $a$ ou $p$ divise $b$.

Ce lemme peut se prouver à l’aide de l’identité de Bézout, en supposant que $p$ ne divise pas $a$ (on montre alors qu’il divise forcément $b$). Comme $p$ est premier, on a alors ${gcd(p, a) = 1}$ et on peut construire des entiers ${u, v \isin \Z}$ vérifiant : ${u \times p + v \times a = 1}$

On en déduit $u \times p \times b + v \times a \times b = b$, et donc $p$ divise $b$ car il divise chacun des deux termes de la somme.

Théorème fondamental de l’arithmétique

Tout nombre entier $n \isin \N$ peut s’écrire de façon unique comme produit de nombres premiers.

Par exemple :

• $10 = 2 \times 5$
• $2020 = 2^5 \times 5 \times 101$
• $289674 = 2 \times 3^2 \times 7 \times 11^2 \times 19$

L’algorithme suivant permet d’obtenir cette décomposition (il est cependant assez inefficace) :

def prime_factors(n):
    f = 2
    while n > 1:
        q, r = euclidean_division(n, f)     # n = q * f + r
        if r == 0:
            yield f
            n = q
        else:
            f += 1
>>> print(list(prime_factors(289674)))
[2, 3, 3, 7, 11, 11, 19]

Cet algorithme fonctionne sur le principe suivant :

• La variable $f$ va tester tous les facteurs possibles à partir de 2
• Lorsqu’un facteur $f$ est trouvé, on continue à décomposer le quotient $q$. Le lemme d’Euclide nous autorise en effet à chercher les facteurs premiers de ${n = f \times q}$ parmi les facteurs de $q$.
• À chaque étape, $n$ n’est divisible par aucun nombre premier strictement inférieur à $f$, donc en particulier pas par $f$ si $f$ n’est pas premier. Le résultat est donc le même que si $f$ ne prenait que des nombres premiers comme valeurs.

Question : Montrer que la décomposition obtenue est unique, c’est-à-dire que chaque nombre premier apparaît toujours le même nombre de fois dans la décomposition en produit.

Il existe une infinité de nombres premiers.

Ce résultat peut se prouver en raisonnant par l’absurde.

On suppose qu’il existe seulement un nombre fini $k$ de nombres premiers $p_1, p_2, ... p_k$, et on note ${N = p_1 \times p_2 \times ... \times p_k + 1}$.

$N$ n’est divisible par aucun de ces $k$ nombres (le reste de la division euclidienne est toujours $1$), ce qui est en contradiction avec l’existence d’une décomposition de $N$ en produit de nombres premiers.

💻 On pourra d’ailleurs illustrer cette démonstration en utilisant Python, la décomposition de $N$ avec différentes valeurs pour $p_1, p_2, ... p_k$ pouvant être mise en évidence :

>>> print(list(prime_factors(2*3 + 1)))
[7]
>>> print(list(prime_factors(2*5*13*19 + 1)))
[7, 353]
>>> print(list(prime_factors(3*5*13*19 + 1)))
[2, 17, 109]

Et après ?

Comme vous le savez, les nombres ne s’arrêtent pas aux entiers 😉

Je vous propose de continuer avec cet article sur la construction des nombres réels, toujours illustré avec Python.

Maths et applications, avec les mains et avec du code 💻
Suivre sur Twitter

• De la construction des réels à la norme IEEE 754 →