14 — Mathématiques pour l'Informatique : Cours complet

Niveau : Université — Durée : 5h de cours + 4h de TP La cryptographie, les compétitions, le calcul scientifique et bien d'autres domaines reposent sur ces outils mathématiques.

---

Partie I — Arithmétique modulaire

1.1 Propriétés

Soit a ≡ b (mod m) si m | (a − b). Propriétés :

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a − b) mod m = ((a mod m) − (b mod m)) mod m   (ajouter m si négatif)
(a × b) mod m = ((a mod m) × (b mod m)) mod m

La division n'est pas directe : a/b mod m n'existe que si b est inversible mod m.

1.2 Inverse modulaire

x est l'inverse de a mod m si a·x ≡ 1 (mod m).

• Il existe ssi gcd(a, m) = 1.
• Calcul : par Euclide étendu (voir 2.2) ou par Fermat quand m est premier.

1.3 Petit théorème de Fermat

Si p est premier et p ∤ a :

a^(p−1) ≡ 1 (mod p)
→ a^(p−2) ≡ a^(−1) (mod p)     (inverse modulaire)

MOD = 10**9 + 7

def modpow(a, e, m=MOD):
    res = 1
    while e > 0:
        if e & 1:
            res = res * a % m
        a = a * a % m
        e >>= 1
    return res

def inv(a, m=MOD):       # m premier
    return modpow(a, m - 2, m)

---

Partie II — PGCD et Euclide étendu

2.1 Algorithme d'Euclide

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

Complexité : O(log(min(a,b)))

2.2 Euclide étendu — coefficients de Bézout

Il trouve x, y tels que a·x + b·y = gcd(a, b).

def egcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

Application : inverse modulaire quand m non premier :

def mod_inv(a, m):
    g, x, _ = egcd(a, m)
    assert g == 1, "a n'est pas inversible mod m"
    return x % m

2.3 Théorème de Bézout

gcd(a,b) est le plus petit entier positif de la forme a·x + b·y. Deux entiers ont une combinaison linéaire égale à 1 ssi ils sont premiers entre eux.

---

Partie III — Primalité

3.1 Test naïf

import math
def is_prime_naive(n):
    if n < 2: return False
    for d in range(2, int(math.isqrt(n)) + 1):
        if n % d == 0:
            return False
    return True

Complexité : O(√n) — trop lent pour les grands nombres.

3.2 Miller-Rabin (probabiliste)

Basé sur le fait que pour p premier et a non multiple de p :

a^d ≡ 1 (mod p)  ou  a^(d·2^r) ≡ −1 (mod p)  pour un r < s
où n − 1 = d · 2^s

import random

def miller_rabin(n, k=12):
    if n < 2: return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % p == 0:
            return n == p
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2; s += 1
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True

• Probabilité d'erreur : ≤ 4^(−k) par test.
• k=12 → erreur < 10⁻⁷.
• Pour n < 3·10¹⁸, des bases fixes déterministes suffisent.

3.3 AKS (déterministe, polynomial)

L'algorithme AKS (2002) prouve la primalité en polynomial — premier algorithme de ce type. En pratique, son exposant est élevé → rarement utilisé ; Miller-Rabin + preuves PRIME certifiées sont préférés.

---

Partie IV — Cribles

4.1 Crible d'Ératosthène

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

• Complexité : O(n log log n).
• Espace : O(n).
• Optimisation : commencer à i*i (les multiples plus petits sont déjà marqués).

4.2 Crible segmenté

Pour trouver les premiers dans [L, R] avec R très grand (ex. 10¹²) et R−L petit :

1. Cribler les premiers jusqu'à √R (crible d'Ératosthène classique).
2. Marquer les multiples de ces premiers dans le segment [L, R].

def segmented_sieve(L, R):
    limit = int(R**0.5) + 1
    primes = sieve(limit)
    is_prime = [True] * (R - L + 1)
    for p in primes:
        start = max(p * p, (L + p - 1) // p * p)
        for j in range(start, R + 1, p):
            is_prime[j - L] = False
    return [L + i for i in range(R - L + 1) if is_prime[i] and L + i > 1]

---

Partie V — Exponentiation rapide

5.1 Binary exponentiation

def power(a, n, m=None):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a if m is None else res * a % m
        a = a * a if m is None else a * a % m
        n >>= 1
    return res

• O(log n) multiplications.
• Principe : a^n = a^(b0 + 2·b1 + 4·b2 + ...) (décomposition binaire de n).

5.2 Applications

• a^b mod m (cryptographie RSA : c = m^e mod n).
• Inverse modulaire par Fermat.
• Recurrences : voir Partie VII (matrices).

---

Partie VI — Combinatoire

6.1 Formules de base

P(n, k) = n! / (n−k)!                  (arrangements)
C(n, k) = n! / (k!·(n−k)!)             (combinaisons)
C(n, k) = C(n−1, k−1) + C(n−1, k)     (triangle de Pascal)

6.2 C(n,k) mod p (p premier, n ≤ 10⁶)

Pré-calculer les factorielles et leurs inverses :

MOD = 10**9 + 7
MAXN = 10**6 + 1

fact = [1] * MAXN
for i in range(1, MAXN):
    fact[i] = fact[i - 1] * i % MOD

inv_fact = [1] * MAXN
inv_fact[MAXN - 1] = pow(fact[MAXN - 1], MOD - 2, MOD)
for i in range(MAXN - 2, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

def nCr(n, k):
    if k < 0 or k > n: return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

6.3 Théorème de Lucas (n, k très grands, p petit)

nCr(n, k) mod p = produit des nCr(n_i, k_i) mod p
où n_i, k_i sont les chiffres de n, k en base p.

---

Partie VII — Matrices

7.1 Multiplication de matrices

def matmul(A, B, m=None):
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            s = 0
            for k in range(n):
                s += A[i][k] * B[k][j]
            C[i][j] = s % m if m else s
    return C

Naïf : O(n³) ; Strassen : O(n^2.81) (chapitre 12).

7.2 Exponentiation matricielle

def matpow(M, e, m=None):
    n = len(M)
    res = [[int(i == j) for j in range(n)] for i in range(n)]  # identité
    while e > 0:
        if e & 1:
            res = matmul(res, M, m)
        M = matmul(M, M, m)
        e >>= 1
    return res

7.3 Fibonacci en O(log n)

Les suites récurrentes linéaires se représentent par des matrices :

[F(n+1)]   =  [1 1]^n  [F(1)]
[F(n)  ]      [1 0]     [F(0)]

def fib_matrix(n, m=None):
    if n == 0: return 0
    M = [[1, 1], [1, 0]]
    P = matpow(M, n - 1, m)
    return P[0][0] % m if m else P[0][0]

• Application : tous les problèmes de récurrence linéaire (F(n) = a·F(n−1) + b·F(n−2)).

---

Partie VIII — FFT (angle mathématique)

8.1 Multiplication polynomiale

Convoluer deux polynômes de degré n naïvement : O(n²). Via FFT : O(n log n).

1. Évaluer en n racines n-ièmes de l'unité : ω_n = e^(2πi/n).
2. Multiplier point par point.
3. Interpoler (FFT inverse).

8.2 Les racines de l'unité

• ω_n^k pour k = 0..n−1.
• Réduction : ω_n^(2k) = ω_(n/2)^k → récursion de taille n/2 → O(n log n).

8.3 Applications

• Multiplication de polynômes et grands nombres.
• Convolution (filtres, corrélation).
• Résolution d'équations aux différences.

---

Partie IX — Bit manipulation

9.1 Astuces classiques

x & 1          # parité (1 = impair)
x & (x - 1)    # supprime le bit le plus bas à 1 (power of 2 test)
x ^ x          # 0
x | (1 << k)   # set bit k
x & ~(1 << k)  # clear bit k
(x >> k) & 1   # lire bit k
x << k         # multiplie par 2^k
x >> k         # divise par 2^k
~x             # complément (inverse tous les bits)

9.2 Power of two test

def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0

9.3 Énumération de sous-ensembles par bitmask

# Tous les sous-ensembles d'un ensemble de n éléments (0..2^n - 1)
for mask in range(1 << n):
    subset = [i for i in range(n) if mask >> i & 1]
    # traiter subset

Sous-ensembles imbriqués (tous les sous-ensembles de chaque sous-ensemble) :

sub = mask
while sub > 0:
    # traiter sub (sous-ensemble de mask)
    sub = (sub - 1) & mask

Coût total : O(3ⁿ).

9.4 Comptage de bits (popcount)

def popcount(x):
    return bin(x).count("1")     # Python ; en C++: __builtin_popcount

---

Partie X — Applications réelles

---

Récapitulatif des complexités

---

Check-list de maîtrise

• Je sais calculer un inverse modulaire (Fermat + Euclide étendu).
• Je sais implémenter Miller-Rabin et expliquer la probabilité d'erreur.
• Je sais cribler les premiers jusqu'à 10⁸ (et segmenter au-delà).
• Je sais faire l'exponentiation rapide modulo.
• Je sais calculer nCr mod p avec factorielles + inverses.
• Je sais calculer Fibonacci en O(log n) par matrices.
• Je sais utiliser les astuces bitwise et l'énumération de sous-ensembles.