Implémentation en Python

FACTRORISATION

Méthode p − 1 de Pollard

Commençons par exposer une méthode relativement peu efficace dans certains cas : Méthode p − 1 de Pollard Cette méthode est due à J.M Pollard en 1974 et repose sur le petit théoreme de Fermat et la superlissité. Théorème 3.1. (petit théorème de Fermat) Soit p un nombre premier. On a a p ≡ a mod p pour tout entier a, et a p−1 ≡ 1 mod p pour tout entier a premier à p Démostration : Démostratrion par induction sur a. Pour a = 1, le résultat est automatique. Supposons que le théorème est vrai au rang a. Démontrons maintenant qu’il est vrai au rang a + 1. Par le théorème du binôme (a + 1)p = a p + C p 1 a p−1 + C p 2 a p−2 + . . . + C p p−1a + 1 Puisque C p k ≡ 0 mod p pour tout k vérifiant 1 ≤ k < p, on obtient (a + 1)p ≡ a + 1 mod p. Il vient alors le théorème est vrai.  Remarque 3.2. Si k est un multiple de p − 1 on a aussi a k ≡ 1 mod p Définition 3.3. Soit N un entier – Un entier n est dit B-lisse lorsque tous les diviseurs premiers de n sont inférieurs ou égaux a B. C’est a dire si n = Qm i=1 p αi i avec pi nombre premier alors pi ≤ B. – Un entier n est dit B-superlisse lorsque toute puissance d’un nombre premier divisant n est inférieure ou égale a B. C’est a dire si n = Qm i=1 p αi i avec pi nombre premier alors p αi i ≤ B

Fonctionnement de l’algorithme

Soit N l’entier qu’on veut factoriser et p un diviseur premier de N. Si p−1 est B-superlisse pour B de taille raisonnable alors B! est un multiple de p − 1. Si a ∈ [|2, n − 1|] est un entier premier avec N, on aura a B! ≡ 1 mod p donc a B! − 1 est un multiple de p. On cherche ensuite a B! mod n. Et on a forcément a B! mod n − 1 est un multiple de p. En effet a B! mod n = a B!+bn avec b ∈ Z puisque n est un multiple de p on a a B! mod n ≡ 1 mod p ce qui donne notre souhait. On pourra alors calculer P GCD(a B! − 1; n) pour esperer trouver un diviseur non trivial de n. Exemple 3.5. Soit n = 133 un nombre non premier à factoriser. Puisque n est non premier alors il admet au moins un diviseur premier p tel que p ≤ n. Donc p ≤ 11 d’où p−1 ∈ [|2; 10|] et il est 8-superlisse. On peut prendre a = 2. Et donc a 6 −1 = 63 et P GCD(63; 133) = 7 

Implémentation en python

# Implémentation de l’algorithme “p − 1” de Pollard. #Ce programme s’implemente facilement en python : # On définit d’abord le pgcd(a,b): >>> def pgcd(a,b): r=a% b if r == 0 return b else: return pgcd(b,r) 38 # Ensuite la fonction pollard par: >>> def pollard(n,B): a=2 for i in range(2,B+1): a=(a**i)%n d=pgcd(a-1,n) if d in range(2,n): return d # Par exemple on veut factoriser n=391 qui est produit de deux nombres premiers. # Donc l’un des facteurs p<= 11 donc p-1 est 16-superlisse d’où on peut prendre B=16 >>> pollard(391,18) 17 # Et donc 17 est l’un des facteurs de n et l’autre facteur est: >>> 391/17 23 Il vient alors n = 17 × 23 La méthode a été ici un succés car 391 − 1 = 2 × 3 × 5 × 13 a tous ses facteurs p tels que p − 1 n’a que 2 et 3 comme facteurs premiers. Dans le cas général, elle réussit si au moins un facteur p de N est tel que tous les diviseurs de p − 1 soit petit. La méthode p − 1 de Pollard est donc une méthode efficace pour factoriser des entiers N admettant un facteur premier p tel que p − 1 soit B-superlisse pour B pas trops grand. Mais cette méthode a peut de chance de fonctionner car il n’est pas fréquent que p − 1 soit B-superlisse pour B de taille raisonable, d’autant plus que , dans les crystosystèmes comme RSA, on fabrique l’entier N de tel sorte que N ne verifie pas cette condition. Et aussi les grands nombres premiers p tel que p − 1 soit B-superlisse sont assez rares. L’avantage de la méthode de Lenstra, basée sur les courbes elliptiques, est qu’elle ne nécessite pas, que N ait un facteur premier p tel que p − 1 soit B-superlisse.