Méthode d’Eratosthène (Division triviale)

LA COMPLEXITE DE L’ALGORITHME DEPEND DE LA TAILLE DE FACTEURS

Méthode d’Eratosthène (Division triviale)

Efficience de la division triviale

Nous pouvons remarquer que le petit Théorème de Fermat peut tester seulement si n est composé, mais il ne donne pas les différent facteurs de n. Supposons que n est un grand entier composé `a factoriser. On peut écrire n = n1n2 alors n1 ≤ √n ou n2 ≤ √n , si le plus petit facteur de n est supérieur `a √n alors n est premier ; visiblement la méthode qui semble la plus naturelle pour trouver le plus petit facteur premier de n, c’est de diviser n par les nombres entre 1 et √n, on a donc besoin de √n d’opérations dans le pire de cas, cette méthode est appelée la méthode d’Eratosthène , elle est déterministe et qui marche avec beaucoup d’entiers car 88% d’entiers ont un facteurs < 100 et prèsque 92% ont un facteur < 1000 [Len00, p.107]. En effet , comme π (100) = 25 o`u π (x) désigne le nombre des premiers inferieurs `a x, nous allons noter p1 = 2, p2 = 3, ··· , p25 = 97 ces 25 nombres premiers inferieurs `a 100. Soit p premier : Si x ≡ 0 (mod p) alors p | x Si x ≡ 1 (mod p) alors p  x Si x ≡ 2 (mod p) alors p  x … Si x ≡ (p − 1) (mod p) alors p  x Dans cette présentation, il y a 1 p de chance pour que x soit divisible par p. Désignons par T1,j la proportion des nombres qui ont un facteur premier dans {p1, p2,…,pj} :

1. La complexité de l’algorithme dépend de la taille de facteurs En remplaçant p1 = 2, p2 = 3, ··· , p25 = 97 dans cette suite d’opérations, on trouve T1,25 ≈ 88% , de la meme manière pour trouver T1,168 ≈ 92% o`u 168 = π (1000).

Division triviale et le pire de cas

Seulement, il y a des cas que cette méthode d’Eratosthène qui consiste `a diviser n par tous les nombres premiers inférieur `a √n , n’est pas pratique :

– Soit n un entier de 60 chiffres a factoriser, nous devons diviser n par des nombres inférieur ou égal `a 1030, supposons qu’il n’y a que 0, 1% seulement parmis eux sont des nombres premiers, on a encore besoin de 1027 divisions a faire , admettons que l’ordinateur peut faire 1015 divisions par seconde, alors la factorisation se fait en 1012 secondes soit plus de 31000 années.

– d’après Tchebycheff , si π (x) désigne le nombre premier inférieur `a x, on a π (x) >x ln x · ln2 Pour factoriser un nombre de 100 chiffres, produit de deux nombres de 50 chiffres, nécessiterait plus de 1050 · 0, 921 ln  1050−1 = 8 · 1047 opérations Et supposons que l’ordinateur(un super ordinateur) pourrait faire 1000 divisions par nanoseconde (10−9s), alors le temps qu’il faudrait pour factoriser n est 8·1047·10−9 secondes ≈ 2 · 1028 années, ce qui est bien plus que l’ˆage de l’univers !

Méthode (p − 1) de Pollard (1970)

 Factorisation par la méthode (p − 1) de Pollard

soit n un entier que l’on souhaite factoriser, supposons que p est un facteur premier de n. Soit a ∈ {2,…,n − 1} tel que pgcd(a, n) = 1 et soit K un entier tel que p − 1 | K (c’est-`a-dire K = (p − 1) · m). Comme pgcd(a, n) = 1 et que p | n, on a pgcd(a, p) = 1. Et d’après le petit théorème de Fermat (voir théorème 5.1), on a : aK = (ap−1)m ≡ 1 (mod p), d’o`u p | aK − 1. Or p | n, puis p | pgcd(aK − 1, n), ainsi pgcd(aK − 1, n) > 1. Si l’on a de plus aK − 1 = 0 (mod n), alors pgcd(aK − 1, n) est un facteur propre de n. L’algorithme (p-1)de Pollard utilise une borne de friabilité B qui est choisie en début de calcul en posant :K =p : premier ≤ B s ∈ N ps (2.1) Si tous les facteurs de p − 1 sont inférieurs `a B, alors on a plus de chance que p − 1 divise K ainsi choisi.

La complexité de l’algorithme dépend de la taille de facteurs 9

Algorithme de la méthode (p-1) de Pollard

Soit n ≥ 2 un entier `a factoriser :

(i) Choisir une borne B pour que si p est le facteur que l’on cherche, avec un peu de chance, tous les facteurs de p − 1 soient plus petit que B. (ii) Choisir un entier a tel que 1 <a<n et que pgcd(a, n) = 1. (iii Calculer l’entier K donné dans l’équation (2.1). (iv) Calculer pgcd(aK − 1, n). Si 1 < pgcd(aK − 1, n) < n alors pgcd(aK − 1, n) est un facteur non trivial de n. Sinon choisir une autre borne B plus grande.

Remarque 2.1. Comme K est B-friable, alors pour que (p−1) ait plus de chance `a diviser K, (p − 1) devrait ˆetre aussi B-friable. Et comme la probabilité de la friabilité de (p − 1) depend de la taille de p alors la rapidité de l’algorithme de (p − 1) de Pollard depend principalement de la taille du facteur p de n (voir Proposition 8.2).

Remarque 2.2. L’algorithme de (p − 1) de Pollard pourrait se terminer éventuellement parce que quand B sera égal `a 1 2 (p − 1) pour un p qui divise n, alors (p − 1) divise K. Cependant si n est un très grand entier , il pourrait ˆetre très difficile de trouver K dans le cas pratique. De plus, cet algorithme a peu de chances de fonctionner, car il n’est pas fréquent que (p − 1) soit puissance de petits nombres premiers, d’autant que, dans les cryptosystèmes comme RSA, on fabrique l’entier n, et on peut s’arranger pour que n ne vérifie pas cette condition.

2.3. Analyse de la complexité de la méthode (p − 1) de Pollard

Soit n le nombre que l’on souhaite factoriser. Proposition 2.3. Pour calculer, pgcd(aK − 1, n), on a besoin de 2 log2 2Kn opérations. Lemme 2.4. Il est possible de calculer aK (mod n) en faisant au plus 2 log2 K opérations o`u chaque opération comprend une multiplication et une congruence modulo n.Preuve. Ecrivons K en base 2, on a K = k0 + k121 + k222 + ··· + kr2r o`u ki = 0 ou ki = 1.