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.

Table des matières

I. Préliminaires
1. Notion de divisions
2. Théorème fondamental de l’arithmétique
3. Algorithme d’Euclide
4. Analyse de la complexité de l’algorithme d’Euclide
5. Petit théorème de Fermat
6. Détection d’une puissance d’un nombre premier
7. Estimation de la grandeur des facteurs
8. Friabilité et probabilité de friabilité
8.1. Friabilité
8.2. Probabilité de friabilité
II. La complexité de l’algorithme dépend de la taille de facteurs
1. Méthode d’Eratosthène (Division triviale)
1.1. Efficience de la division triviale
1.2. Division triviale et le pire de cas
2. Méthode (p − 1) de Pollard (1970)
2.1. Factorisation par la méthode (p − 1) de Pollard
2.2. Algorithme de la méthode (p-1) de Pollard
2.3. Analyse de la complexité de la méthode (p − 1) de Pollard
3. Méthode de factorisation par des Courbes Elliptiques de H. Lenstra (1987)
3.1. Courbes elliptiques : définitions et propriétés
3.2. Structure de groupe abélien
3.3. Méthode utilisant les Courbes elliptiques ou ECM(Elliptics Curves Methods)
III. La complexité de l’algorithme ne dépend pas de la taille de facteurs
1. Méthode de Fermat (1643)
2. Méthode de Kra¨ıtchik (1926)
3. Méthode utilisant le Crible Quadratique de C. Pomerance (1981)
3.1. Déroulement de la méthode Crible Quadratique ou QS (Quadratic Sieve)
3.2. Base de factorisation du Crible Quadratique
3.3. Crible Quadratique
3.4. MPQS (Multiple Polynomial Quadratic Sieve) variante de QS par P. Montgomery(1986)
3.5. SIQS(Self Initializing Quadratic Sieve) variante de QS
IV.Algorithme de factorisation de nombres utilisant l’ordinateur quantique
1. Introduction sur l’Information quantique et notion élémentaire au calcul quantique
1.1. Superposition .
1.2. Observation d’un bit quantique
1.3. Transformation quantique de Fourier
2. Algorithme de Peter Shor(1994)
2.1. Détermination des facteurs d’un entier n
2.2. Détermination de la période r de xa (mod n)

Méthode d’EratosthèneTélécharger le document complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *