NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 07/02/2017

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Nombres PREMIERS

 

Débutants

Nombres

Premiers

Factorisation

 

Glossaire

Nombres

Premiers

 

 

INDEX

 

Factorisation

 

Nombres premiers

 

Divisibilité

Factorisation

 Fermat

 

Sommaire de cette page

>>> Historique

>>> Approche

>>> Première méthode, la plus commune

>>> Deuxième méthode – Le modulo

>>> Fermat et son petit théorème

>>> Algorithme AKS

>>> Wilson et son théorème

>>> Nombres de Mersenne

>>> Factorisation de Fermat

>>> BILAN

 

 

 

 

 

Primalité & Factorisation

des nombres

 

 Deux problèmes successifs:

*      Déterminer si un nombre est premier: primalité;

*      Trouver ses facteurs premiers: factorisation.

 

Trouver les facteurs d'un nombre est utile en général, mais a regagné de l'intérêt ces dernières décennies du fait que les codes de sécurité des échanges informatiques sont basés sur la grande difficulté (impossibilité) de factoriser de très grands nombres.

 

 

 

 

Gauss (1801)

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic.

C.F. Gauss – 1801 - Disquisitiones Arithmeticae

 

 

 

Historique

 

Avant les machines

 

Au XVIIe siècle: table des facteurs des nombres jusqu'à 24000.

1668:                 tous jusqu'à 100 000.

Au XVIIe siècle: tous jusqu'à 10 000 000 par Johann Dase (1824-1861)

Au XIXe siècle: 100 000 000 par J.P. Kulik (Prague) avec quelques erreurs.

Au-delà, ces tables ne tiennent plus sur du papier.

 

Avec les machines

 

Un des premiers grands nombres factorisés par machine (Lehmer):

293 + 1

= 9 903 520 314 283 042 199 192 993 793 = 0,99… 1028

= 6 442 450 947 x 1 537 228 672 093 301 419

= 6 442 450 947 x 529 510 939 x 2 903 110 321

 

1971: factorisation d'un nombre "difficile" de 40 chiffres.

1982: Supercalculateur (Cray 1) craque les 50 chiffres.

1988: Facteur k trouvé en 1988 par coopération de centaines d'ordinateurs. k = 11104 + 1  / 118 + 1.

La limite des 100 chiffres est atteinte.

Pour se trouver en zone sûre, le codage en cryptographie adopte des nombres à 200 chiffres.

2010: Factorisation du RSA 768 >>>

 

 

D'après: Dites un chiffre de Malcom Lines - Flammarion

 

 

Approche

 

*      Factoriser un nombre consiste à:

*       Identifier que le nombre est composé, et non pas premier, et à

*       Trouver des facteurs premiers dont le produit redonne ce nombre.

*      Le théorème fondamental de l'arithmétique nous indique que cette factorisation est unique.

 

111 n'est pas premier, la somme de ses chiffres est égale à 3 ce qui indique qu'il est divisible par 3 et donc pas premier;

 

Avec une petite division, on trouve l'autre facteur: 111 = 3 x 37.

 

 

Première méthode – la plus commune

 

*      Trouver si le nombre est divisible par un autre:

*       par utilisation de critères de divisibilités, ou






*       par essais par divisions avec des nombres premiers de plus en plus grands.  La recherche s'arrête lorsqu'on atteint un diviseur supérieur à la racine carrée du nombre

 

*      On notera immédiatement qu'il est illusoire d'appliquer cette méthode aux très grands nombres.

La recherche de divisibilité est assez facile pour les nombres 2, 3, 5 et  11 (et leurs multiples).

456 = 2 x 228

453 = 3 x 151

455 = 5 x   91

459 = 9 x   51

450 = 10 x 45

451 = 11 x  41

 

Ayant épuisé ces possibilités, il faut recourir à la division classique:

469

7

04

  49

  00

67

 

 

 

 

 

Deuxième méthode – Modulo

 

*      Le principe est simple: une buche est bien coupée en stère s'il n'y a pas de chute.

*      Les mathématiciens ont créé un nouveau monde, un nouvel espace de travail. Un espace où seul le reste de la division compte. Les calculs dans ce monde seront plus propices à débusquer les nombres composés.

*      Nous utilisons tous les jours cette technique en regardant nos montres. Toutes les 12 heures nous revenons à 0.

*      Les mathématiciens parlent de congruence ou de modulo.

 

*      Cette arithmétique en modulo marche aussi avec les opérations.

 

Un nombre est divisible par n si le reste de sa division par n est nul.

 

Un nombre divisé par 7 donne les restes 0, 1, 2,3 ,4 5 et 6; seul le reste 0 montre que le nombre est divisible par 7.

 

Minuit et midi sont des horaires multiples de 12.

Le calcul de l'horloge fait que 14h devient 2h. On a retiré 12heures.

 

14  2 mod 12

2 est congru à 14 modulo 12

Ce qui veut dire que, dans le monde du 12, 2 et 14 sont équivalents.

 

 9 +  5 = 14   2 mod 12

11 + 12 = 23 11 mod 12

12 + 12 = 24  0 mod 12

13 + 12 = 25  1 mod 12

  9 x  4 = 36   0 mod 12

  9 x  5 = 45   9 mod 12

 

*      Si, d'une manière ou d'une autre, je connais la congruence d'un nombre N modulo M, je sais dire s'il est divisible par M.

*      Bien noter que je ne sais pas conclure si le nombre est premier. Pour cela , il faudrait essayer toutes les valeurs de congruence.

 

109 824  87 mod 89

109 825  88 mod 89

109 826    0 mod 89

Ce dernier nombre est composé:

109 826 = 89 x 1234.

 

 

 

FERMAT et son petit théorème

 

*      Fermat s'intéresse aux modulos selon des nombres premiers p. Il  remarque qu'un nombre a et sa puissance p sont égaux (congruents).


*      Même déguisé en puissance p, le scanner modulo p, déshabillera l'individu pour le mettre à nu: ap  devient a.

 

 

*      En langage mathématique:

 

a puissance p est égal à a modulo p.

 

Exemples

(Le reste de 32 divisé par 5 est 2)

 

Tout nombre a, déguisé en puissance p, se faisant happer par la machine à modulo p, sera haché menu pour recracher tout ce qu'il a.

 

Voir suite et exemples en Modulo / Divisibilité par 11

 

Algorithme AKS

En 2002, Manindra Agrawal (Kapur, Inde), Neeraj Kayal et Nitin Saxena (AKS), annoncent avoir trouvé un test de primalité rapide dérivant du petit théorème de Fermat. Agrawal résume sa découverte par "Les premiers sont en P". Ce qui veut dire que la temps de calcul de la primalité est, en gros, proportionnel à sa quantité de chiffres.

C'est, rapide mais encore assez pour déjouer les systèmes de cryptage.

 

 

 

 

Théorème de Wilson

 

*      Ce théorème se propose de traquer les nombres premiers aux abords des nombres factoriels.

 

(n – 1)! + 1 est divisible par n, seulement si n est premier.

 

Pour n = 5: 4! + 1 = 25, divisible par 5

 

Voir suite et exemples en Théorème de Wilson

 

 

Nombres de Mersenne

 

*      Cette recherche traque les nombres premiers aux abords des puissances de 2.

*      La méthode utilisée permet de reconnaître de très grands nombres premiers, en fait les plus grands connus aujourd'hui.

*      À noter, qu'il s'agit du premier pas (premier ou composé) et non pas de la factorisation.

 

 

24 – 1 = 15 =3 x 5

25 – 1 = 31 premier

26 – 1 = 63 = 3 x 3 x 7

27 – 1 = 127 premier

etc.

 

Voir Primalité des nombres de Mersenne

 

 

 

Factorisation de Fermat

Voir page spéciale >>>

Ce test a été amélioré par Maurice Kraitchik en utilisant les modulos des carrés.

 

 

Autres méthodes

De nombreux algorithmes ont été développés. Cela dépasse le cadre de ce site.

La factorisation est d'autant plus difficile que les facteurs sont de tailles voisines.

Voir factorisation de Lenstra

 

BILAN – Méthodes les plus accessibles

Selon ce que l'on cherche

Premier ou composé?

Facteurs

 

Tout nombre

 

·         Critères de divisibilité

 

·         Congruences (modulos)

*      Théorème de Wilson

*      Petit théorème de Fermat

·         Crible d'Ératosthène

 

·         Méthode de Fermat

Nombres spécifiques

·         Mersenne (2n – 1)

*      Test de Lucas-Lehmer

·         Nombres divisibles d'après un critère de divisibilité.

 

 

 

 

 

 

 

Factorisation

Index

*    Factorisation des factorielles

*    Factorisation des nombres complexes

*    Factorisation des puissances de 21

*    Méthode avec deux carrés

*    Méthode de Fermat

*    Méthode des frères Carissan (crible des résidus quadratiques)

*    Méthode René Nève – Sommes de pairs et des impairs

*    Méthodes générales

*    Méthode ECM de recherche de grands facteurs

Voir

*    Nombres premiersIndex

Aussi

*    Liste de nombres premiers

 

*    Nombres composés

*    Représentation des nombres

*    Facteurs premiers autour de 1000

*    Premiers en tableaux, en spirales …

 

Site

*    Prime Factors Calculator

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Premier/Facto.htm