NOMBRES - Curiosités, théorie et usages

Accueil / Dictionnaire / Rubriques / Index / Atlas / Références /    Nouveautés

ORIENTATION GÉNÉRALE    -   M'écrire   -   Édition du: 26/07/2016

Débutants

Nombres

Premiers

Nombres PREMIERS

Glossaire

Nombres

Premiers

 

Recherche de PRIMALITÉ

 

 

 

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

 


 

 

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.

 

*         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

 

*         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

 

 


 

Suite

*    Test de primalité – Développements

*    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!