Discussion :

[laurent_ott]

Chers membres du club,

J'ai le plaisir de vous présenter ce tutoriel :

Comprendre la méthode de factorisation du Crible Quadratique
Une invention de Carl Pomerance

Cet article vous permet de comprendre la méthode de factorisation du crible quadratique. Vous trouverez dans le fichier joint les codes source en VBA du crible quadratique ainsi que d'autres fonctions utilisées pour la factorisation : le test de primalité Miller-Rabin, le crible d'Ératosthène, la factorisation RhoPollard, l'algorithme Tonelli-Shanks, mais aussi les algorithmes pour les opérations sur les grands nombres (additions, soustractions, multiplications, puissances, divisions, modulos, racines carrées…).

Bonne lecture

Retrouvez les meilleurs cours et tutoriels pour apprendre l'algorithmique.

[valentin03]

A quoi ça sert concrètement ?

[laurent_ott]

Bonjour.
Si la question est à quoi sert le crible quadratique, la réponse est : à factoriser "rapidement" des grands nombres.
Si la question est à quoi sert cette documentation, la réponse est : à expliquer "simplement" cette méthode de factorisation qui est une référence dans ce domaine.
Si la question est à quoi ça sert de savoir comment marche le crible quadratique, alors on s'éloigne peut-être de l'algorithmique et l'on s'approche de la philosophie.

Plus sérieusement, la question mérite en effet d'être posée. J'avoue ne pas avoir la réponse.
Et pour celles et ceux qui (se) demanderont à Qui ça sert, je peux répondre tout de suite : "je ne sais pas, en tout cas pas à moi."
Bonne lecture pour les plus curieux d'entre vous.

[valentin03]

Qui factorise et pourquoi ?
Tu dis ne pas avoir la réponse mais peut-être que quelqu'un ici l'a. Je suis curieux pathologique.

[aghrsa]

Bonjour,

Je n'ai pas compris dans l'exemple du début vous vous arrêtiez une fois arrivé à 51, ou dans le deuxième exemple, pourquoi à 60261, pourriez-vous clarifier ce détail ?

Merci beaucoup

[laurent_ott]

Le premier exemple est très simpliste et ne tient pas compte des améliorations possibles. La règle du pivot de Gauss dit que si l'on a au moins autant de lignes que de colonne une solution peut être trouvée.
60261 est la 7eme ligne sur 7 colonnes (-1 est exclu car non utilisé ici) donc on cherche une solution. Si pas trouvée on ajoutera une ligne. Ainsi de suite.
La recherche étant chronophage, c'est inutile de la lancer avant d'avoir le minimum de lignes requises, sauf à avoir de la chance.
Cordialement