Séance 8 : factorisation d’entiers – crible quadratique

Exercice

Dans cet exercice, on propose d’implémenter (de façon naïve et non-optimisée) l’algorithme de crible quadratique qui trouve un diviseur propre d’un entier \(N\).

Question 1. Écrire une fonction calcule_base_facteurs(N, B) qui calcule une base de facteurs plus petits que B dans le but de factoriser un entier N.

# à compléter

Question 2. Écrire une fonction de quad_sieve(FB, N, A) qui prend en entrée une base de facteurs FB, un entier N à factoriser et une borne A, et qui effectue l’étape d’effritement (crible).

# à compléter

Question 3. Écrire une fonction de build_matrix(FB, sieve) qui prend en entrée une base de facteurs FB et une liste d’entiers effrités sieve, et qui construit la matrice associée.

# à compléter

Question 4. Assembler les fonctions pour obtenir une fonction qui, étant donné un entier N en entrée, retourne un diviseur de N grâce à l’algorithme du crible quadratrique.

# à compléter

Question 5. Testez votre fonction avec \(N =\) par exemple.

# à compléter