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
1 |
0 |