Utilisateur:Némo Sv/Brouillon

En théorie calculatoire des nombres, l'algorithme p + 1 de Williams est un algorithme de décomposition en facteurs premiers, appartenant à la famille des algorithmes de factorisation se basant sur les groupes algébriques. Il a été créé par Hugh C. Williams (en) en 1982.

http://colin.barker.pagesperso-orange.fr/lpa/big_pp1.htm https://programmingpraxis.com/2010/06/04/williams-p1-factorization-algorithm/

Il fonctionne bien si l'entier N à factoriser possède au moins un facteur premier p tel que p + 1 est friable, c'est-à-dire si p + 1 ne possède que des petits facteurs. Il fait appel aux suites de Lucas to perform exponentiation dans un corps quadratique.

Il est analogue à l'algorithme p − 1 de Pollard.

Algorithme

On choisit un entier A supérieur à 2 caractérisant la suite de Lucas définie par

V_{0}=2,V_{1}=A,V_{j}=AV_{j-1}-V_{j-2}

,

où toutes les opérations se font modulo N.

Alors tout nombre premier impair p divise $\operatorname {pgcd} (N,V_{M}-2)$ quand M est un multiple de $p-\left({\frac {D}{p}}\right)$ , où $D=A^{2}-4$ et $\left({\frac {D}{p}}\right)$ représente le symbole de Jacobi.

Il est nécessaire que $\left({\frac {D}{p}}\right)=-1$ , c'est-à-dire que D doit être un non-résidu quadratique modulo p. Cependant, p étant inconnu avant l'exécution de l'algorithme, plusieurs valeurs de A peuvent être nécessaires avant de trouver une solution. Si $\left({\frac {D}{p}}\right)=+1$ , cet algorithme dégénère en une version lente de l'algorithme p − 1 de Pollard.

Ainsi, pour différentes valeurs de M, on calcule $\operatorname {pgcd} (N,V_{M}-2)$ , et si le résultat est différent de 1 et de N, on a trouvé un facteur non-trivial de N.

Les valeurs de M employées sont les factorielles successives, et on tire parti du fait que $V_{k!}$ est le k-ème terme de la suite caractérisée par $V_{k!-1}$ .

Pour trouver le M-ème élément V de la suite de Lucas caractérisée par B, on emploie les relations suivantes : $V_{2j}=V_{j}^{2}-2$ et $V_{2j+1}=V_{j+1}V_{j}-B$ .

On procède d'une manière similaire à l'algorithme d'exponentiation modulaire, mais en partant du premier bit à droite du bit de poids fort jusqu'au bit de poids faible :

x := B       
y := (B ^ 2 − 2) mod N     
pour chaque bit de M à partir du premier bit à droite du bit de poids fort faire
    si le bit est égal à 1 alors
        x := (x × y − B) mod N 
        y := (y ^ 2 − 2) mod N 
    sinon
        y := (x × y − B) mod N 
        x := (x ^ 2 − 2) mod N 
V := x

Exemples

Avec N = 112729 et A = 5, et en notant V[B] la suite de Lucas de premiers termes $V_{0}=2$ et $V_{1}=B$ , les termes successifs $V_{M}$ sont :

V[5]_1!= V[5]₁ = 5

V[5]_2!= V[5]₂ = 23

V[5]_3! = V[23]₃ = 12098

V[5]_4! = V[12098]₄ = 87680

V[5]_5! = V[87680]₅ = 53242

V[5]_6! = V[53242]₆ = 27666

V[5]_7! = V[27666]₇ = 110229.

À cette étape, on remarque que pgcd(110229 - 2, 112729) = 139, donc 139 est un facteur non-trivial de 112 729. On peut noter que p + 1 = 140 = 2² × 5 × 7. Le nombre 7! est la plus petite factorielle multiple de 140, c'est pourquoi le facteur 139 est trouvé à cette étape.

En employant une autre valeur initiale, par exemple A = 9, on obtient :

V[9]_1! = V[9]₁ = 9

V[9]_2! = V[9]₂ = 79

V[9]_3! = V[79]₃ = 41886

V[9]_4! = V[41886]₄ = 79378

V[9]_5! = V[79378]₅ = 1934

V[9]_6! = V[1934]₆ = 10582

V[9]_7! = V[10582]₇ = 84241

V[9]_8! = V[84241]₈ = 93973

V[9]_9! = V[93973]₉ = 91645.

À cette étape, on remarque que pgcd(91645 - 2, 112729) = 811, donc 811 est un facteur non-trivial de 112 729. On peut noter que p − 1 = 810 = 2 × 5 × 3⁴. Le nombre 9! est la plus petite factorielle qui est multiple de 810, c'est pourquoi le facteur 811 est trouvé à cette étape. Le facteur 139 n'est pas trouvé car p − 1 = 138 = 2 × 3 × 23 n'est pas un diviseur de 9!.

Comme on peut le remarquer à travers ces exemples, on ne peut savoir à l'avance lequel des deux entiers p - 1 ou p + 1 sera friable, p étant le facteur premier trouvé par l'algorithme.

Généralisation

En se basant sur l'algorithme p − 1 de Pollard et l'algorithme p+1 de Williams, Eric Bach et Jeffrey Shallit ont développé des méthodes pour factoriser n efficacement sachant qu'il possède un facteur premier p tel que le k^ème polynôme cyclotomique Φ_k(p) est friable.^[1] Les premiers polynômes cyclotomiques sont les suivants : Φ₁(p) = p−1, Φ₂(p) = p+1, Φ₃(p) = p²+p+1 et Φ₄(p) = p²+1.

Références

↑ Eric Bach et Jeffrey Shallit, « Factoring with Cyclotomic Polynomials », Mathematics of Computation, American Mathematical Society, vol. 52, n^o 185,‎ 1989, p. 201–219 (DOI 10.1090/S0025-5718-1989-0947467-1, JSTOR 2008664, lire en ligne)

« {{{1}}} »
https://www.jstor.org/stable/2007633?origin=crossref&seq=1

Liens externes

Modèle:Number theoretic algorithms

Category:Integer factorization algorithms

[1] Eric Bach et Jeffrey Shallit, « Factoring with Cyclotomic Polynomials », Mathematics of Computation, American Mathematical Society, vol. 52, n^o 185,‎ 1989, p. 201–219 (DOI 10.1090/S0025-5718-1989-0947467-1, JSTOR 2008664, lire en ligne)

[1]