Séance 7 : factorisation d’entiers – méthodes exponentielles

Séance 7 : factorisation d’entiers – méthodes exponentielles#

Tout entier naturel \(n \ge 2\) peut se décomposer comme un produit de facteurs premiers élevés à une certaine puissance. Cette décomposition est uneique à l’ordre des facteurs près :

\[ n = \prod_{i=1}^k p_i^{e_i} \]

où les \(p_i\) sont premiers et les \(e_i\) sont des entiers strictement positifs.

En informatique, on peut donc représenter une factorisation de \(n\) comme un ditionnaire, où l’on associe à chaque \(p_i\) sa valuation \(e_i\).

Par exemple, l’entier \(n = 600 = 2^3 \cdot 3 \cdot 5^2\) peut être représenté par le dictionnaire

{ 2: 3, 3: 1, 5: 1}

{2: 3, 3: 1, 5: 1}

Exercice 1 : divisions successives#

Dans cet exercice, on utilise un algorithme « naïf » de factorisation, à l’aide de divisions successives.

Question 1. Écrire une fonction factorise_divisions(n), qui prend en entrée un entier \(n \ge 2\), et qui retourne sa décomposition en facteurs premuiers sous la forme d’un dictionnaire, comme présenté ci-dessus.

# à compléter

Question 2. Jusqu’à quelle valeur de \(n\) (en orde de grandeur) l’algorithme prend-il moins d’une seconde ?

# à compléter

Exercice 2 : algorithme de Fermat#

Dans cet exercice, on utilise la méthode de Fermat pour factoriser un entier. L’algorithme est le suivant :

Entrée : \(n \ge 3\) impair

Sortie : deux diviseurs \(a\) et \(b\) de \(n\)

  1. Calculer \(t = \lceil \sqrt{n} \rceil\) et \(c = t^2-n\).

  2. Tant que \(c\) n’est pas un carré :

    • \(c \leftarrow c + 2t + 1\)

    • \(t \leftarrow t+1\)

  3. Calculer \(s\) la racine carrée de \(c\).

  4. Retourner \((t+s, t-s)\)

Ci-dessous vous est fournie une fonction de calcul de racine carrée entière avec reste, qui pour un entier \(N\) en entrée, retourne un couple d’entier naturels \((X, R)\) tels que \(N = X^2 + R\) et \(0 \le R < 2X+1\). Si \(R = 0\), l’entier \(N\) en entrée est donc un carré.

def decomposition_base_4(N):
    n = N
    res = []
    while n > 0:
        res.append(n % 4)
        n //= 4
    return res

def racine_carree_entiere(N):
    decomp = decomposition_base_4(N)
    d = len(decomp)
    R = 0
    X = 0
    for j in range(d-1, -1, -1):
        T = 4*R + decomp[j]
        if T > 4*X:
            R = T - 4*X - 1
            X = 2*X+1
        else:
            R = T
            X = 2*X
    return X, R

Vous pouvez également utiliser la fonction isqrt du module math de python.

Question 1. Écrire une fonction etape_fermat(n), qui prend en entrée un entier \(n \ge 3\) impair, et retourne deux diviseurs \(a\) et \(b\) de \(n\) grâce à la méthode de Fermat.

# à compléter

Question 2 (facultative). Écrire une fonction factorise_fermat(n), qui prend en entrée un entier \(n \ge 1\) quelconque, et retourne sa facorisation complète en utilisant la méthode de Fermat.

# à compléter

Exercice 3 : méthode \(\rho\) de Pollard#

Dans cet exercice, on utilise la méthode du \(\rho\) de Pollard pour factoriser un entier. Voir slides de cours pour les détails.

Question 1. Écrire une fonction etape_pollard_rho(n), qui prend en entrée un entier \(n\) qui n’est pas la puissance d’un nombre premier, et qui retourne deux diviseurs \(a\) et \(b\) de \(n\) grâce à la méthode de Fermat. La fonction implémentera l’algorithme de Floyd pour la recherche du cycle.

# à compléter

Question 2 (facultative). Écrire une fonction factorise_pollard_rho(n), qui prend en entrée un entier \(n \ge 1\) quelconque, et retourne sa facorisation complète en utilisant la méthode de Fermat.

# à compléter
Contenu