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.

import math

def factorise_divisions(n):
    x = n
    s = math.sqrt(n)
    p = 2
    facto = dict()
    while x >= s:
        while x % p == 0:
            if p in facto:
                facto[p] += 1
            else:
                facto[p] = 1
            x //= p
        p += 1
    if x != 1:
        if x in facto:
            facto[x] += 1
        else:
            facto[x] = 1
    return facto
    
for n in [8, 21, 101, 600]:
    print(n, ":", factorise_divisions(n))

8 : {2: 3}
21 : {3: 1, 7: 1}
101 : {101: 1}
600 : {2: 3, 3: 1, 5: 2}

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

import time, random

t = 0.0
e = 3
while t < 0.1:   # 0.1 sec. pour moi
    n = random.randint(10**e, 10**(e+1))
    t = time.time()
    x = factorise_divisions(n)
    t = time.time() - t
    print(n, ":", x)
    e += 1

7354 : {2: 1, 3677: 1}
69009 : {3: 1, 23003: 1}
383986 : {2: 1, 37: 1, 5189: 1}
4124407 : {7: 1, 53: 1, 11117: 1}
13016122 : {2: 1, 7: 1, 107: 1, 8689: 1}

254097532 : {2: 2, 13: 1, 4886491: 1}

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.

def etape_fermat(n):
    t, r = racine_carree_entiere(n)
    if r != 0:
        t += 1
    c = t**2 - n
    s, r = racine_carree_entiere(c)
    while r != 0:
        c += 2*t +1
        t += 1
        s, r = racine_carree_entiere(c)
    return [t+s, t-s]

Puis, on peut tester que la méthode fonctionne bien avec des entiers \(n\) constitués de deux diviseurs \(a\) et \(b\) proches de \(\sqrt{n}\) :

for e in range(3, 8):
    a = random.randint(10**e, 10**(e+1))
    p = a - random.randint(0, 10**(e//2))
    if p % 2 == 0:
        p -= 1
    q = a + random.randint(0, 10**(e//2))
    if q % 2 == 0:
        q += 1
    n = p*q
    print(n, etape_fermat(n))

23425551 [4847, 4833]
171007353 [13101, 13053]
27214106733 [165033, 164901]
16102018090599 [4012847, 4012617]
729453184079405 [27008965, 27007817]

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.

def fermat_aux(n, fact):
    while n % 2 == 0:
        if not(2 in fact):
            fact[2] = 0
        fact[2] += 1
        n //= 2
    f, g = etape_fermat(n)
    if (f == 1 or f == n):
        if not(n in fact):
            fact[n] = 0
        fact[n] += 1
        return
    fermat_aux(f, fact)
    fermat_aux(g, fact)

def factorise_fermat(n):
    fact = dict()
    fermat_aux(n, fact)
    return fact
    
for n in [8, 21, 101, 600]:
    print(n, ":", factorise_fermat(n))

8 : {2: 3, 1: 1}
21 : {7: 1, 3: 1}
101 : {101: 1}
600 : {2: 3, 5: 2, 3: 1}

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.

def function_f(z):
    return z**2 + 1

def etape_pollard_rho(n, func):
    x = random.randint(0, n-1)
    y = x
    d = 1
    while (d == 1):
        x = func(x) % n
        y = func(func(y)) % n
        d = math.gcd(x-y, n)
    if d == n:
        return etape_pollard_rho(n, func)
    return d, n//d

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.

# à terminer
Contenu