Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous

Identifiant
Mot de passe

Mot de passe oublié ?

Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

Tutoriel pour comprendre la méthode de factorisation du crible quadratique : une invention de Carl Pomerance,

Par Laurent Ott

Le 23 juillet 2019 à 03:21, par laurent_ott

15 commentaires

5PARTAGES

Voter pour

11

Voter contre

0

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.

Vous avez lu gratuitement 83 articles depuis plus d'un an.
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer à vous proposer des publications.

Une erreur dans cette actualité ? Signalez-nous-la !

Votre nom : Votre e-mail :

Décrivez l'erreur que vous souhaitez porter à notre connaissance :

15 commentaires

Commenter Signaler un problème

Rédacteur

Le 24/07/2019 à 10:31

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.

Voter pour

3

Voter contre

0

Membre actif

Le 23/07/2019 à 8:43

A quoi ça sert concrètement ?

Voter pour

2

Voter contre

1

Membre actif

Le 25/07/2019 à 18:03

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.

Voter pour

1

Voter contre

0

Rédacteur

Le 25/05/2020 à 16:47

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

Voter pour

1

Voter contre

0

Rédacteur

Le 25/05/2020 à 17:16

C'est comme ça que je l'ai compris, et programmé.

Voter pour

1

Voter contre

0

Futur Membre du Club

Le 31/08/2021 à 14:26

Bonjour et merci pour votre article "Comprendre la méthode de factorisation du Crible Quadratique. Il répond d’une façon claire à des questions que je me posais.

Par contre, je me suis surpris à trouver une simplification, étonnamment simple(équation du second degré), à cette méthode : Il suffit de remplacer le calcul des X²- N par la fonction :

F(n) = n²-2(X-1) n+ ((X²-N) -2X+1) avec n entier naturel
On remarque que si on calcule le discriminant (simplifié car b pair)= b'²-ac = ((X-1)²-((X²-N) -2X+1) = N
Normal, sinon on pourrait calculer directement les facteurs premiers.

Exemple pour N = 48206621

X=6944 (racine de N arrondi à l’entier supérieur)

F(n) = n² + 2(6944-1)n+(12515-2*6944+1) = n²+13886n –1372

F(1) = 1+13886-1372= 12515
F(2)=4+2*13886-1372= 26404

Etc....

Cette fonction facilite le calcul du crible quadratique :

Il suffit de calculer la fonction, modulo p (avec p=7,11,19,23,..)- On notera au passage que le test de Legendre sert à éliminer les nombres premiers qui n'admettent pas de racine carrée au discriminant dans p

exemple p= 11 f(n)mod11 = n²+ 4n +3 d'où b'²-ac = 4-3 =1 d'où les deux racines
n1 = -b'+1/a= -2+1= -1= 10 mod11
et n2= -2-1=-3 = 8 mod 11

p= 7 f(n) = n²+ 5n racine n1 = 0 et n= -5 = 2 mod 7

P=19 f(n) = n²+16n+15 d'où b'²-ac = 64-15 = 49 n1= -8-7= -15 = 4 mod 19 et n2= -1 = 18.

Calculer le crible quadratique revient donc à résoudre l'équation du second degré de la f(n) mod(p)=0.

Peut-être que l'utilisation de cette fonction peut permettre un gain de calcul conséquent.

Cordialement

Voter pour

1

Voter contre

0

Rédacteur

Le 09/07/2022 à 13:10

Bonjour.
Je confirme, votre chiffre peut être décomposé avec l'algorithme ECM, en tout cas ça marche chez moi.
Il faut faire plusieurs passages. Difficile à dire combien car à chaque passage les variables de départ sont aléatoires. Donc non reproductible.
D'après mes rapides essais, une cinquantaine de passages.
Mais c'est parfois moins, parfois plus.
Il faudrait peut être programmer votre recherche en lui indiquant le temps que vous souhaitez consacrer à l'algorithme, et donc le laisser tourner autant de fois que ce délai n'est pas dépassé. Ou comme j'ai fait, lui indiquer un nombre maximum de passages avant de laisser tomber.
Ce qui revient au même.
Bonne programmation.
Laurent OTT.

Voter pour

1

Voter contre

0

Candidat au Club

Le 25/05/2020 à 16:23

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

Voter pour

0

Voter contre

0

Candidat au Club

Le 25/05/2020 à 17:11

Ah d'accord, on détermine les facteurs à l'aide de la friabilité et de Legendre, puis on arrête de chercher des équations une fois qu'on en a obtenu autant que l'on a de facteurs ?

Voter pour

0

Voter contre

0

Futur Membre du Club

Le 01/09/2021 à 9:20

P.S. Lire F(n) = n²+2(X-1) n+ ((X²-N) -2X+1) au lieu de F(n) = n²-2(X-1) n+ ((X²-N) -2X+1)

Voter pour

0

Voter contre

0

Commenter Signaler un problème