Algorithmes d'arithmétique en Python

Ce chapitre programme en Python les méthodes du cours : conversions entre bases, division euclidienne, algorithme d'Euclide, test de primalité, crible d'Ératosthène, décomposition en facteurs premiers, calculs modulo n et inverse modulaire. Le programme de l'E3 demande de savoir mettre en œuvre un algorithme de recherche de nombres premiers et de décomposition en facteurs premiers, et l'écrit ponctuel de 2 heures comporte toujours un exercice qui évalue la capacité à programmer (compléter, lire ou écrire un algorithme) ; en CCF, l'algorithmique a sa propre situation d'évaluation, sur machine. Chaque fonction est donnée en Python, avec sa version en pseudo-code quand les sujets l'écrivent ainsi.

Pseudo-code et Python

Les sujets écrivent les algorithmes en pseudo-code (langage naturel structuré) ou en Python ; aucun langage n'est imposé, Python est recommandé. Les deux se traduisent ligne à ligne :

Le cours d'algorithmique détaille la syntaxe de Python, les boucles et les fonctions ; son chapitre algorithmes des maths du BTS SIO présente aussi des algorithmes de logique, d'ensembles et de graphes.

Du décimal vers une base quelconque

Les divisions successives se programment avec une boucle : tant que le nombre n'est pas nul, on calcule le reste (le chiffre suivant) et on remplace le nombre par le quotient.

CHIFFRES = "0123456789ABCDEF"

def vers_base(n, b):
    """Écriture de l'entier naturel n en base b (2 <= b <= 16)."""
    if n == 0:
        return "0"
    resultat = ""
    while n > 0:
        reste = n % b
        resultat = CHIFFRES[reste] + resultat   # le nouveau chiffre va à gauche
        n = n // b
    return resultat

print(vers_base(156, 2))     # 10011100
print(vers_base(2026, 16))   # 7EA

La ligne resultat = CHIFFRES[reste] + resultat ajoute chaque chiffre à gauche : c'est la lecture « de bas en haut » des restes, faite automatiquement. La chaîne CHIFFRES donne le caractère de chaque reste : CHIFFRES[10] vaut "A".

Trace de vers_base(45, 2) :

La boucle s'arrête quand n vaut 0 : 45 = (101101)₂.

D'une base quelconque vers le décimal

La méthode de Horner du chapitre 2 lit les chiffres de gauche à droite : à chaque chiffre, on multiplie la valeur par la base et on ajoute le chiffre.

def vers_decimal(ecriture, b):
    """Valeur de l'écriture (une chaîne) en base b, par la méthode de Horner."""
    valeur = 0
    for chiffre in ecriture:
        valeur = valeur * b + CHIFFRES.index(chiffre)
    return valeur

print(vers_decimal("7EA", 16))       # 2026
print(vers_decimal("11111111", 2))   # 255

CHIFFRES.index("E") renvoie 14, la position du caractère dans la chaîne, donc sa valeur.

Python fait déjà ces conversions avec bin, hex, format et int(chaine, base) (chapitre 2) ; un sujet peut pourtant te demander de les écrire toi-même, ou de compléter une fonction comme celles-ci.

La partie fractionnaire en binaire

Les multiplications successives du chapitre 3 : on multiplie par 2, la partie entière donne le bit, on garde la partie fractionnaire. On limite le nombre de bits, car l'écriture peut être infinie.

def fraction_binaire(x, nb_bits):
    """Les nb_bits premiers bits après la virgule de x (0 <= x < 1)."""
    bits = ""
    for i in range(nb_bits):
        x = x * 2
        if x >= 1:
            bits = bits + "1"
            x = x - 1
        else:
            bits = bits + "0"
    return bits

print(fraction_binaire(0.8125, 4))   # 1101
print(fraction_binaire(0.1, 12))     # 000110011001

Pour 0,1, on retrouve le motif 0011 qui se répète.

La division euclidienne

Python la fait avec // et %. Sans ces opérateurs, on retire b tant que c'est possible : le nombre de soustractions est le quotient, ce qui reste est le reste.

Fonction division(a, b)
    q ← 0
    r ← a
    Tant que r ≥ b faire
        r ← r − b
        q ← q + 1
    Fin Tant que
    Renvoyer q, r

def division_euclidienne(a, b):
    q = 0
    r = a
    while r >= b:
        r = r - b
        q = q + 1
    return q, r

print(division_euclidienne(2026, 7))   # (289, 3)

La boucle s'arrête dès que r < b : c'est exactement la condition 0 ≤ r < b de la définition. Cet algorithme est lent pour de grands quotients (289 tours de boucle ici), mais il montre pourquoi le couple (q, r) existe.

L'algorithme d'Euclide

On remplace (a, b) par (b, reste de a par b) tant que b n'est pas nul ; le PGCD est la dernière valeur de a.

Fonction pgcd(a, b)
    Tant que b ≠ 0 faire
        r ← reste(a, b)
        a ← b
        b ← r
    Fin Tant que
    Renvoyer a

def pgcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

print(pgcd(4410, 1188))   # 18

Trace de pgcd(4410, 1188), une ligne par passage dans la boucle :

Après le dernier tour, a = 18 et b = 0 : la fonction renvoie 18.

En Python, math.gcd(4410, 1188) donne aussi 18.

Nombres premiers, test, crible et décomposition

Tester si n est premier : on cherche un diviseur d de 2 à √n. La condition d * d <= n évite de calculer une racine carrée.

def est_premier(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d = d + 1
    return True

print(est_premier(223), est_premier(221))   # True False

return False arrête la fonction dès qu'un diviseur est trouvé ; on n'atteint return True qu'après avoir tout testé sans succès. Le test n < 2 écarte 0 et 1, qui ne sont pas premiers.

Le crible d'Ératosthène : un tableau de booléens, où l'on barre (met à False) les multiples de chaque nombre premier.

def crible(n):
    """Liste des nombres premiers inférieurs ou égaux à n."""
    premier = [True] * (n + 1)   # premier[k] vaut True tant que k n'est pas barré
    premier[0] = False
    premier[1] = False
    p = 2
    while p * p <= n:
        if premier[p]:
            for multiple in range(p * p, n + 1, p):
                premier[multiple] = False
        p = p + 1
    return [k for k in range(n + 1) if premier[k]]

print(crible(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

range(p * p, n + 1, p) parcourt p², p² + p, p² + 2p… : les multiples de p à partir de p², comme dans la méthode à la main.

La décomposition en facteurs premiers : on divise par d tant que c'est possible, puis on passe à d + 1. Les diviseurs non premiers (4, 6…) ne divisent jamais : leurs facteurs ont déjà été retirés.

def decomposition(n):
    """Liste des facteurs premiers de n (n >= 2), répétés selon leur exposant."""
    facteurs = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            facteurs.append(d)
            n = n // d
        d = d + 1
    if n > 1:              # ce qui reste est un nombre premier
        facteurs.append(n)
    return facteurs

print(decomposition(360))    # [2, 2, 2, 3, 3, 5]
print(decomposition(2026))   # [2, 1013]

Le dernier test traite le cas d'un grand facteur premier : pour 2 026, après la division par 2, il reste 1 013, et aucun d de 3 à 31 ne le divise ; la boucle s'arrête et 1 013 est ajouté.

Les diviseurs d'un entier, par simple test :

def diviseurs(n):
    liste = []
    for d in range(1, n + 1):
        if n % d == 0:
            liste.append(d)
    return liste

print(diviseurs(72))   # [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]

Congruences et inverse modulaire

Une puissance modulo n, en réduisant à chaque multiplication pour ne jamais manipuler de grands nombres :

def puissance_modulaire(a, k, n):
    resultat = 1
    for i in range(k):
        resultat = (resultat * a) % n
    return resultat

print(puissance_modulaire(3, 2026, 7))   # 4
print(pow(3, 2026, 7))                   # 4 : la fonction intégrée, bien plus rapide

L'inverse modulo n, par essais successifs, en vérifiant d'abord qu'il existe :

def inverse(a, n):
    """Inverse de a modulo n, ou -1 s'il n'existe pas."""
    if pgcd(a, n) != 1:
        return -1
    c = 1
    while (a * c) % n != 1:
        c = c + 1
    return c

print(inverse(7, 26), inverse(9, 26), inverse(6, 26))   # 15 3 -1

Depuis Python 3.8, pow(7, -1, 26) renvoie aussi 15 ; il utilise l'algorithme d'Euclide étendu.

Compter les clés d'un chiffrement affine (la fonction du sujet E3 2026, en Python) :

def nb_cles():
    nb = 0
    for a in range(1, 26):
        if pgcd(a, 26) == 1:
            nb = nb + 1
    return nb * 26

print(nb_cles())   # 312

Parcourir une liste circulaire par sauts

On part de la position 0 et on avance de saut positions, modulo n, jusqu'à revenir à 0 :

def positions_visitees(saut, n):
    positions = [0]
    p = saut % n
    while p != 0:
        positions.append(p)
        p = (p + saut) % n
    return positions

print(positions_visitees(8, 12))        # [0, 8, 4]
print(len(positions_visitees(5, 12)))   # 12 : tout est visité

La longueur de la liste vaut toujours n ÷ PGCD(saut, n) : tu peux le vérifier sur plusieurs exemples, c'est la propriété du chapitre 9.

Tester ses fonctions

Une fonction n'est pas finie tant qu'elle n'est pas testée sur des cas choisis, y compris les cas limites. Avec assert, Python s'arrête avec une erreur si un test échoue :

assert vers_base(0, 2) == "0"         # cas limite : zéro
assert vers_base(255, 16) == "FF"
assert vers_decimal("FF", 16) == 255
assert pgcd(17, 5) == 1               # premiers entre eux
assert pgcd(12, 4) == 4               # l'un divise l'autre
assert est_premier(2)                 # le seul premier pair
assert not est_premier(1)             # 1 n'est pas premier
assert not est_premier(91)            # 7 × 13 : piège classique
assert inverse(13, 26) == -1          # pas d'inverse

Choisir et justifier ses jeux d'essai fait partie des critères d'évaluation de la situation d'algorithmique de l'E3 (l'épreuve d'algorithmique).

Exercices

def mystere(n):
    s = 0
    while n > 0:
        s = s + n % 10
        n = n // 10
    return s

def est_premier(n):
    for d in range(2, n):
        if n % d == 0:
            return False
        else:
            return True

def nb_bits(n):
    k = 0
    while ........:
        n = ........
        k = k + 1
    return k

def nb_bits(n):
    k = 0
    while n > 0:
        n = n // 2
        k = k + 1
    return k

def premiers_avec(n):
    liste = []
    for a in range(1, n):
        if pgcd(a, n) == 1:
            liste.append(a)
    return liste