Binaire et
arithmétique.

• Convertir entre décimal, binaire et hexadécimal, à la main et en Python.
• Manipuler des bits avec & | ^ ~ << >> : masques, drapeaux, registres.
• Expliquer pourquoi 30 000 + 30 000 est négatif sur Arduino.
• Calculer avec des restes et comprendre le principe du chiffrement RSA.

Couleurs (#FF8800), adresses mémoire, adresses I2C des capteurs (0x68 pour un gyroscope MPU6050), codes d’erreur, registres des microcontrôleurs. Un octet va de 0x00 à 0xFF (0 à 255). Apprenez à lire les hexas à deux chiffres comme vous lisez les nombres à deux chiffres.

Avec k bits, on représente 2ᵏ valeurs. Pour représenter n valeurs, il faut ⌈log₂(n)⌉ bits. Un convertisseur analogique-numérique « 10 bits » découpe la tension en 1024 niveaux : c’est sa résolution. Une image 8 bits par couleur a 256 niveaux de rouge, vert et bleu, soit 16,7 millions de couleurs. Un entier Python n’a pas de limite, mais un int Arduino a 16 bits, un long 32 : il faut choisir le type selon la plage nécessaire.

Ce sont les opérations natives du processeur : une porte ET par bit, en un cycle. Sur un microcontrôleur, allumer une LED consiste à mettre un bit à 1 dans un registre de 8 bits, sans toucher aux 7 autres : impossible sans | et &. Le décalage remplace une multiplication par 2ᵏ, précieux sur un processeur sans multiplieur matériel.

Un masque est un nombre avec des 1 aux positions qui nous intéressent. 1 << i est le masque du seul bit i. r | m force à 1, r & ~m force à 0, r ^ m inverse, r & m teste. C’est exactement ce que fait digitalWrite sur Arduino, et vous l’écrirez vous-même en séance 22 avec PORTB |= (1 << 5). Les protocoles de communication (I2C, CAN, Bluetooth) empaquettent plusieurs valeurs dans un octet : il faut savoir les extraire.

Sur 8 bits, on décide que les valeurs de 128 à 255 représentent −128 à −1 : on soustrait 256. Avantage : l’addition marche sans rien changer (255 + 1 = 256 ≡ 0, et −1 + 1 = 0). Le bit de poids fort indique le signe. 32767 + 1 donne −32768 : c’est le débordement (overflow), silencieux en C. Ariane 5 a explosé en 1996 en convertissant un flottant 64 bits vers un entier 16 bits. Sur Arduino, int = 16 bits : pour compter des millisecondes, utilisez unsigned long (32 bits), sinon votre chronomètre repasse à zéro après 32 secondes.

Un float est un nombre binaire à virgule flottante sur 64 bits (norme IEEE 754) : 1 bit de signe, 11 d’exposant, 52 de mantisse. 0.1 n’a pas d’écriture binaire finie (comme 1/3 en décimal). Conséquences : jamais de == entre flottants calculés, préférer les entiers quand c’est possible (compter en millimètres plutôt qu’en mètres flottants), et savoir que 16 chiffres significatifs est le maximum. Sur Arduino, float ne fait que 32 bits : 7 chiffres significatifs, et les calculs sont 10 à 50 fois plus lents que sur entiers.

Si a = q₁n + r₁ et b = q₂n + r₂, alors ab = (q₁q₂n + q₁r₂ + q₂r₁)n + r₁r₂ : le reste de ab ne dépend que de r₁r₂. Cela permet de calculer avec des nombres énormes en gardant des restes petits. C’est la base de toute la cryptographie moderne, et une question de concours classique (« montrer que 10ⁿ ≡ 1 mod 9 »).

L’algorithme d’Euclide est le plus vieil algorithme encore utilisé. Sa complexité est O(log(min(a, b))) : le pire cas est deux nombres de Fibonacci consécutifs (théorème de Lamé, 1844 — le premier résultat de complexité de l’histoire). L’inverse modulaire permet de « diviser » modulo n : c’est la clé de déchiffrement de RSA. Prouver que bezout est correct par récurrence est un excellent exercice.

Le théorème d’Euler dit que m^φ(n) ≡ 1 (mod n) quand pgcd(m, n) = 1. Comme ed ≡ 1 (mod φ), (mᵉ)ᵈ = m^(1+kφ) ≡ m. Pour casser RSA, il faut d, donc φ, donc p et q : factoriser n. Multiplier deux nombres de 300 chiffres est instantané ; retrouver les facteurs prendrait des milliards d’années avec les algorithmes connus. Toute la sécurité repose sur cette asymétrie. RSA (1977) protège vos connexions HTTPS, vos cartes bancaires, vos mises à jour logicielles. Un ordinateur quantique assez grand le casserait (algorithme de Shor) : la cryptographie post-quantique est un sujet de recherche actuel.

def vers_binaire(n):
    if n == 0:
        return "0"
    bits = ""
    while n > 0:
        bits = str(n % 2) + bits
        n //= 2
    return bits

def depuis_binaire(s):
    n = 0
    for c in s:
        n = n * 2 + int(c)         # schéma de Horner
    return n

assert all(depuis_binaire(vers_binaire(n)) == n for n in range(1001))

for n in range(16):
    g = n ^ (n >> 1)
    print(f"{n:2} {n:04b} {n:X}   gray {g:04b}")

Colonne de droite : 0101… ; suivante : 00110011… ; chaque colonne a une période double de la précédente. Le code de Gray sert dans les encodeurs de position des moteurs : quand le capteur passe d’une position à la suivante, un seul bit change, donc aucune lecture intermédiaire fausse. Vous le retrouverez en séance 27.

def encoder(vitesse, direction, alerte, batterie):
    assert 0 <= vitesse < 16 and 0 <= direction < 8 and 0 <= batterie < 256
    return vitesse | (direction << 4) | (int(alerte) << 7) | (batterie << 8)

def decoder(paquet):
    return {
        "vitesse":   paquet & 0xF,
        "direction": (paquet >> 4) & 0x7,
        "alerte":    bool((paquet >> 7) & 1),
        "batterie":  (paquet >> 8) & 0xFF,
    }

def parite(x):
    return bin(x).count("1") % 2      # 0 si nombre pair de 1

import random
for _ in range(1000):
    v, d, a, b = random.randrange(16), random.randrange(8), random.random() < .5, random.randrange(256)
    assert decoder(encoder(v, d, a, b)) == {"vitesse": v, "direction": d, "alerte": a, "batterie": b}
print("OK")

Le bit de parité (un 17ᵉ bit valant la parité des 16 autres) détecte toute corruption d’un nombre impair de bits, mais pas de deux. Pour corriger, il faut plus de redondance : codes de Hamming, CRC — c’est ce que font l’USB, le WiFi et les disques durs. Ce défi est exactement ce que vous ferez en séance 26 entre PC et carte.

def est_premier_mr(n, k=20):
    if n < 2: return False
    for p in (2, 3, 5, 7, 11, 13):
        if n % p == 0: return n == p
    s, d = 0, n - 1
    while d % 2 == 0:
        s += 1; d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x in (1, n - 1):
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False           # aucun break : a est un témoin de non-primalité
    return True

def premier_aleatoire(bits):
    while True:
        c = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if est_premier_mr(c):
            return c

p, q = premier_aleatoire(64), premier_aleatoire(64)
n, phi, e = p * q, (p - 1) * (q - 1), 65537
d = pow(e, -1, phi)
m = 123456789
print(pow(pow(m, e, n), d, n) == m)

Le for … else : le else s’exécute si la boucle s’est terminée sans break. Miller-Rabin est probabiliste : un nombre composé peut passer un témoin avec probabilité ≤ 1/4, donc 20 témoins → erreur ≤ 10⁻¹². C’est ainsi que sont générées toutes les clés RSA du monde. Le fondement est le petit théorème de Fermat (aⁿ⁻¹ ≡ 1 mod n si n premier) affiné par la structure des racines carrées de 1. Ouverture : cherchez « nombres de Carmichael » — ils trompent Fermat mais pas Miller-Rabin.