Logarithme base 2 en informatique

Le logarithme en base 2, noté log₂, répond à la question « à quelle puissance faut-il élever 2 pour obtenir x ? » : log₂ 8 = 3, car 2³ = 8. En informatique, il donne le nombre de bits qu'il faut pour coder n valeurs, le nombre d'étapes d'une recherche dichotomique, l'ordre de grandeur des algorithmes rapides et l'entropie d'un mot de passe. Il se calcule avec ln : log₂ x = ln x / ln 2.

Logarithme de base a et exponentielle de base a

Le logarithme népérien est le logarithme de base e : ln x est la puissance à laquelle il faut élever e pour obtenir x. On définit de la même façon un logarithme pour toute base a > 0 différente de 1.

Deux bases servent tous les jours :

la base 10, le logarithme décimal, noté log ou log₁₀ : log 1 000 = 3, log 0,001 = −3. Il compte les chiffres d'un nombre et mesure les décibels ;
la base 2, le logarithme binaire, noté log₂ ou lb : log₂ 1 024 = 10, log₂ 0,25 = −2. Il compte les bits.

Dans l'autre sens, l'exponentielle de base a s'écrit avec e : aˣ = e^(x ln a), puisque ln(aˣ) = x ln a. Ainsi 2ˣ = e^(x ln 2) ≈ e^(0,693x). Sa dérivée vaut ln a × aˣ.

Où le calculer	Logarithme en base 2	Logarithme décimal
À la main	ln x / ln 2	ln x / ln 10, ou la touche log
TI-83 Premium CE Edition Python	touche `math`, ligne A : baseLOG( (logBASE( en anglais)	touche `log`
Casio Graph 90+E	menu Exe-Mat, `F4` (MATH) puis `F2` (logab)	touche `log`
Python	`math.log2(x)`	`math.log10(x)`

Un repère à connaître : 2¹⁰ = 1 024 ≈ 10³. Donc log₂ 1 000 ≈ 10, log₂(10⁶) ≈ 20, log₂(10⁹) ≈ 30. Les valeurs exactes sont 9,97, 19,93 et 29,90.

Combien de bits pour coder n valeurs ?

Avec k bits, on écrit 2ᵏ valeurs différentes (cours d'arithmétique). Pour coder n valeurs distinctes, il faut le plus petit k tel que 2ᵏ ≥ n, c'est-à-dire k ≥ log₂ n.

Besoin	Calcul	Bits
Une lettre parmi 26	log₂ 26 ≈ 4,70	5
Un identifiant parmi 1 000	log₂ 1 000 ≈ 9,97	10
Un identifiant parmi 5 000 salariés	log₂ 5 000 ≈ 12,29	13
Un numéro de VLAN (4 096 valeurs, de 0 à 4 095)	log₂ 4 096 = 12	12, la taille du champ VLAN ID de la norme 802.1Q
Écrire 1 000 en binaire	⌊9,97⌋ + 1	10 bits : 1111101000
Écrire 1 024 en binaire	⌊10⌋ + 1	11 bits : 10000000000

En réseau, la même question se pose pour un sous-réseau : pour 500 hôtes, il faut k bits d'hôte avec 2ᵏ − 2 ≥ 500 (on retire l'adresse du réseau et celle de diffusion). 2⁸ − 2 = 254 ne suffit pas, 2⁹ − 2 = 510 suffit : 9 bits d'hôte, donc un masque en /23 (32 − 9).

En Python, n.bit_length() donne directement le nombre de bits d'un entier : (1000).bit_length() renvoie 10.

La recherche dichotomique

La recherche dichotomique cherche une valeur dans un tableau trié en comparant à l'élément du milieu, puis en jetant la moitié qui ne peut pas la contenir (cours d'algorithmique). À chaque comparaison, la zone de recherche est divisée par 2 : il reste n/2, puis n/4, puis n/2ᵏ éléments après k comparaisons. La recherche s'arrête quand il ne reste plus rien, c'est-à-dire après environ log₂ n étapes.

Taille du tableau	Recherche séquentielle (pire cas)	Recherche dichotomique (pire cas)
8	8	4
1 000	1 000	10
10 000	10 000	14
1 000 000	1 000 000	20
2 000 000	2 000 000	21

Les index des bases de données reposent sur la même idée, avec une base plus grande. MySQL range ses index dans des arbres B+ où chaque page contient des centaines de clés (index SQL). Avec environ 500 clés par page, le nombre de niveaux à lire pour 3 millions de lignes est de l'ordre de log₅₀₀(3 000 000) = ln(3 000 000) / ln 500 ≈ 2,4 : trois lectures de pages suffisent.

La complexité des algorithmes

La complexité d'un algorithme dit comment son nombre d'opérations grandit avec la taille n des données (la notation O). Le logarithme y occupe une place à part : il grandit, mais si lentement qu'un algorithme en O(log n) reste quasi instantané quelle que soit la taille.

n	log₂ n	n	n log₂ n	n²
1 000	≈ 10	1 000	≈ 10 000	1 000 000
1 000 000	≈ 20	1 000 000	≈ 20 000 000	10¹²

Plus la courbe monte vite, plus l'algorithme devient lent quand les données grossissent

Le chapitre 7 donne la version mathématique de ce classement : à l'infini, toute puissance de n l'emporte sur le logarithme, et l'exponentielle l'emporte sur toute puissance.

L'entropie d'un mot de passe

La robustesse d'un mot de passe tiré au hasard se mesure par son entropie, en bits : si chacun de ses L caractères est choisi au hasard parmi N symboles, il y a N^L mots de passe possibles, et l'entropie vaut :

text

H = log₂(N^L) = L × log₂ N    bits

Chaque bit d'entropie double le nombre d'essais nécessaires à une attaque par force brute ; dix bits de plus le multiplient par 2¹⁰ ≈ 1 000.

12 caractères parmi 62 (minuscules, majuscules, chiffres) : H = 12 × log₂ 62 ≈ 12 × 5,954 ≈ 71,5 bits.
Combien de caractères parmi 62 pour atteindre 80 bits ? L × 5,954 ≥ 80, soit L ≥ 13,44 : 14 caractères.
Une phrase de passe dont chaque mot est tiré au hasard dans une liste de 7 776 mots : chaque mot apporte log₂ 7 776 ≈ 12,92 bits.

Les recommandations de la CNIL fixent des seuils d'entropie selon les protections en place ; elles sont détaillées dans le cours de cybersécurité. Le même logarithme règle le facteur de coût de bcrypt : un coût c correspond à 2ᶜ itérations, donc passer d'un coût 10 à un coût 12 multiplie le temps de calcul d'une empreinte par 2² = 4 (politique de mots de passe).

Les décibels et le dBm du Wi-Fi

Le logarithme décimal mesure les rapports de puissance en décibels (dB). Une puissance P exprimée en dBm se compare à 1 milliwatt :

text

P en dBm = 10 × log₁₀(P / 1 mW)        et, dans l'autre sens,        P = 10^(dBm / 10) mW

1 mW = 0 dBm, 100 mW = 20 dBm, 0,001 mW = −30 dBm.
Un signal Wi-Fi de −67 dBm, la valeur souvent visée pour la voix et la visioconférence (le Wi-Fi d'entreprise), vaut 10^(−6,7) mW ≈ 2 × 10⁻⁷ mW : deux dixièmes de nanowatt.
+3 dB ≈ puissance × 2 (car 10 log₁₀ 2 ≈ 3,01) et +10 dB = puissance × 10.
Un signal à −79 dBm est 12 dB sous −67 dBm : il est 10^1,2 ≈ 16 fois plus faible.

Grâce au logarithme, une échelle qui va du milliwatt (0 dBm) au picowatt (−90 dBm, soit 10⁻⁹ mW) tient entre 0 et −90 : c'est pour ça que les outils d'étude de site Wi-Fi l'utilisent.