NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 30/05/2018

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

Barre de recherche          DicoCulture              Index alphabétique       Brèves de Maths    

 

Nombres PREMIERS

 

Débutants

Nombres

Premiers

Recherche de PRIMALITÉ

 

Glossaire

Nombres

Premiers

 

 

Index des pages

NOMBRES PREMIERS

 

>>> INDEX

 

Crible d'Ératosthène

Presque-premiers

Carmichaël

Divisibilité

Pseudo-premiers

Carmichaël - texte

Primalité

Liste pseudo-P.

 

Sommaire de cette page

>>> Approche

>>> Méthode de recherche des nombres premiers

>>> Principe de la recherche

>>> Test  trouvé en 2002

>>> Recherche simple des premiers avec Fermat

 

 

 

 

Ce nombre est-il PREMIER?

 

Comment s'y prendre?

Quels sont les outils à notre disposition?

 

Le nombre d'opérations pour tester si un nombre est premier croit exponentiellement avec le nombre de chiffres. Il faut beaucoup, beaucoup plus d'opérations pour tester un nombre de 51 chiffres par rapport à un nombre à 50, par exemple. À partir d'une certaine taille de nombre, il faudrait des journées, des années, des milliards d'années … de calculs par ordinateur.

 

 

 

APROCHE – Déterminer si un nombre est premier

 

27 489 ?

 

*    La racine numérique vaut

2 + 7 + 4 + 8 + 9

= 9 + 12 + 9

=>12

=> 3

Ce nombre est divisible par 3

 

*    On peut trouver les facteurs premiers en divisant:

27 489

3

9 163

7

1 309

7

187

11

17

17

1

 

 

427 741 ?

 

*    On tente la division par les premiers successifs.

 

427 741

3

pas divisible

 

5

pas divisible

 

7

61105,8 non

 

11

pas divisible

 

13

32903,1 non

 

17

25161,2 non

 

etc.

 

 

*    On ne trouve pas facilement de diviseurs.

*    Et pourtant, ce nombre est composé.

27 489 = 3 x 7 x 7 x 11 x 17

 

*    Pour de grands nombres, il n'est pas facile de trouver si un nombre est premier.

427 741 = 521 x 821

 

*    Il est encore plus difficile de trouver les facteurs premiers

 

 

Méthode de recherche

des NOMBRES PREMIERS

 

*         On sait que la recherche d'un facteur premier de n s'arrête à n. Au-delà, un des facteurs serait parmi ceux déjà examinés jusqu'à là.

 

*         Même avec cette réserve, en utilisant la méthode systématique du crible, il faudrait 30 ans de calculateur pour tester un nombre de 30 chiffres!

 

Un premier outil bien utile.

Pour s'en faire une petite idée …

 

*         Le (petit) théorème de Fermat réduit les calculs:

 

Si p est premier et que le pgcd (p,a) est égal à 1,

alors ap-1 est congru à 1 modulo p

 

*         Pour effectuer la recherche on calcule an-1 modulo n, si le résultat n'est pas 1, le nombre n'est pas premier.  Voir Exemple de réalisation

 

*         Il existe une méthode simple pour effectuer ce calcul.
Pour un nombre à 100 chiffres, la méthode du crible nécessite 1050 opérations; tandis que cette méthode ne nécessite seulement que 300 opérations.

 

*         Malheureusement, la méthode élimine, mais ne confirme pas. Il existe des nombres non premiers qui satisfont le test de Fermat, ce sont les " pseudo-premiers ".

 

 

Exemple:

2340 = 1 mod 341

Mais 341 n'est pas premier: 341= 11 x 31

Confirmation par 3340 = 56 mod 341

 

*         Il existe d'autres raffinements tenant compte des propriétés des nombres de la forme p-1, comme les nombres de Mersenne:
Mn = 2n – 1.

 

 

 

  

 PRINCIPE DE LA RECHERCHE

 

*         Comment trouver les grands nombres premiers ?

On peut chercher en divisant par les nombres inférieurs.

On y passerait son existence !

 

*         Pour la recherche des grands premiers, on utilise le théorème de Lucas (1870), simplifié par Lehmer.

 

Le théorème de Lucas - Lehmer

 

*         Ce théorème est efficace, mais il faut disposer d'un algorithme de multiplication rapide.

*         En 1968, Strassen découvre une méthode basée sur la FFT (Fast Fourier Transform).

 

*         La méthode améliorée avec Schönhage a été publiée en 1971.

 

*         Le GIMPS utilise une version de cette méthode améliorée par Richard Crandall, un chercheur de longue date sur les nombres de Mersenne.

 

Le test de Lucas - Lehmer

 

*         On utilise le théorème suivant pour rechercher les nombres premiers de Mersenne, et, du même coup, les nombres parfaits pairs :

 

 Pour p impair,

le nombre de Mersenne 2p-1 est premier

si et seulement si

2p – 1 divise S(p-1)

S(n+1) = S(n)2 - 2,

et S(1) = 4.

 

*         Il est aussi possible de démarrer avec S(1) = 10 et d'autres valeurs selon p.

 

En pseudo code ce test devient:

 

Lucas_Lehmer_Test(p):

s := 4;

pour i de 3 à p faire s := s2 - 2 mod 2p - 1;

si s == 0 alors

2p - 1 est premier

sinon

2p - 1 est composé;

 

Voir Exemple de calcul

 

 

 

TEST  TROUVÉ EN 2002 – Test AKS

 

*         Trois mathématiciens indiens trouvent un nouvel algorithme pour tester la primalité d'un entier qui indique si n est premier ou n est composé en un temps qui est un polynôme de la taille de n. C'est le premier du genre

 

*         Trois chercheurs indiens mettent au point un algorithme de test pour les très grands nombres.

*         Pour un même temps de calcul par ordinateur, il permet de tester des nombres beaucoup plus grands en utilisant que les méthodes connues jusqu'alors.

*         L'algorithme est pourtant  relativement simple. Il est performant. Il s'agit d'une habile combinaison de tests déjà connus.

*         La recherche des nombres premiers est un problème polynomial, affirment ces jeunes chercheurs (primes is in P)

 

Voir Voyageur de commerce

 

PRIMES is in P

 

Manindra Agrawal,

Neeraj Kayal and

Nitin Saxena

Department of Computer Science & Engineering

Indian Institute of Technology Kanpur

Kanpur-208016, INDIA

August 6, 2002

 

Abstract

We present a deterministic polynomial-time algorithm that determines whether an input number n is prime or composite.

 

 

Voir Suite sur leur site

Voir Août 2002

 

 

Recherche simple des premiers avec Fermat

Le petit théorème de Fermat énonce:

 

Si p est premier alors:

          2p – 1 – 1 est divisible par p

 

 

Implémentation sur tableur

Il est possible de pratiquer une recherche simple des nombres premiers sur le tableur.

Il s'agit d'un exercice d'entrainement sur cet outil et un exercice de découverte du petit théorème de Fermat. La recherche est, en effet, limitée aux petits nombres (jusqu'à 30).

 

Colonne 1: les nombres de 3 à n;

Colonne 2: le nombre 2 à la puissance n;

Colonne 3: idem moins 1; et

Colonne 4: calcul du reste de la division de ce nombre (en colonne 3) par n via la fonction mod (résultat semblable en faisant simplement la division et en constant qu'elle tombe juste ou pas)

En jaune: reste nul et identification des nombres premiers: 3, 5, 7, 11 …

 

 

Implémentation avec logiciel (Maple)

Aussi rapide qu'avec le tableur à la différence que ces logiciels savent manipuler de très grands nombres.

 

Boucle d'exploration des nombres de 3 à 20 (par exemple);

Calcul de N selon la formule de Fermat;

Recherche conditionnelle: si ce nombre N est divisible par n (via calcul mod), alors imprimer le nombre n. On en profite pour indiquer la valeur du grand nombre N et son quotient par n. Le logiciel authentifie la primalité de n (isprime)

 

Attention

Les spécialistes savent que si p est premier le test est bon; mais, réciproquement, si le test est bon, le nombre n'est pas forcément premier.

 

Le premier cas se présente pour 341

 

Ces nombres comme 341 sont appelés pseudo-premiers.

 

Remède

Introduire un deuxième test (les puissances de 3 par exemple). Ci-contre, le programme élimine bien341, cette fois.

Hélas, il existe de rares nombres qui résistent encore, les pseudo-premiers absolus.

 

 

Voir ProgrammationIndex

 

 

 

Suite

*    Test de primalité – Développements

*    Méthode ou crible de René Nève

*    Primalité et suite de Perrin 

*    Records

*    Nombres premiersIndex

Voir

*    Nombres composés

*    Représentation des nombres

*    Facteurs premiers autour de 1000

*    Programmation du crible d'Ératosthène

*    Grilles 

*    Ératosthène

Site

*    La page des nombres premiers
       de Chris Caldwell

*    Primes is in P - A 2200 year old math problem solved!

Cette page

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