Algorithmes pour nombres premiers

Un article de Haypo.

Retour aux articles de mathématiques

Sommaire

[modifier] Test par divisions successives

La méthode la plus simple pour tester la primauté d'un nombre N est de tester sa divisibilité par tous les nombres compris entre 2 et la racine carrée de N.

EstPremier(x) =
{
  // Inférieur à 2 : pas premier
  Si (x<2) Retourne(FAUX);

  // Egal 2 : premier
  Si (x == 2) Retourne(VRAI);

  // Nombre pair autre que 2 : n'est pas premier
  Si ((x % 2) == 0) Retourne(FAUX);

  // Teste tous les diviseur inférieur au nombre (de 2 à x-1)
  i = 3;
  TantQue(i*i <= x)
  {
    // Si on peut diviser ce nombre : il n'est pas premier
    Si ((x % i) == 0) Retourne(FAUX);

    // Passe au prochain diviseur
    i += 2;
  };

  // Aucun nombre compris entre 2 et Racine(x)
  // ne le divise : il est premier
  Retourne(VRAI);
};

Le problème avec cet algorithme est qu'il est très long car il doit faire énormément de divisions ... Pensons à un nombre ayant une centaines de chiffres. On utilise plutôt cet algorithme pour vérifier rapidement qu'est nombre est composé en testant sa divisibilité par les nombres compris entre 1 et 1000 par exemple (très rapide).

[modifier] Crible d'Eratostène

Pour obtenir facilement une liste des nombres premiers de 1 à N, on place les N entiers naturels (nombres de 1 à N) dans un tableau (carré de côté la racine de N par exemple). Puis on suit cette recette :

Eratostene(n) =
{
  // Crée le tableau : le nombre i est premier si lst[i]=Vrai
  lst = NouvListe(n+1, Vrai);

  // Les nombres 0 et 1 ne sont pas premier
  lst[0] = Faux;
  lst[1] = Faux;

  // "Efface" les nombres composés
  i = 2;
  TantQue (i <= n)
  {
    j = i*2;
    TantQue(j <= n)
    {
      lst[j] = Faux;
      j += i;
    };
    i++;
    TantQue ((i <= n) et (lst[i] == Faux)) i++;
  };

  // Exemple d'utilisation du tableau :
  // Affiche les nombres premiers
  AfficheN ("Nombre premiers compris entre 1 à ".n." (inclu) :");
  k = 0; // compteur de nombres premiers
  Pour (i=0, i <= n, i++)
  {
    // Si le nombre i est premier ...
    Si (lst[i] == Vrai)
    {
      Si (k <> 0) Affiche (", ");
      Affiche (i);
      k++;
    };
  };

  Affiche ("\n\n");

  // Affiche le nombre de nombres premiers inférieur ou égaux à n
  AfficheN ("Total = ".k." nombre(s) premier(s)");
};
  • On barre 1 (n'est pas premier).
  • On barre ensuite tous les multiples de 2 : 4, 6, 8, 10, ...
  • Le nombre qui suit, 3, est donc premier. On barre tous ses multiples : 6, 9, 12, ...
  • Le nombre qui suit, 5 (car 4 a été barré car il est mutliple de 2), est donc premier. On barre tous ses multiples : 10, 15, 20, 25, ...
  • On continue ansi jusqu'à la fin du tableau.

Pour finir, on obtient uniquement des nombres premiers.

[modifier] Algorithme de Rabin-Miller (1975)

On passe maintenant aux tests "probabilistes". Le test permet de dire avec certitude qu'est est composé, par contre il peut qu'un nombre est premier avec un risque (très faible) qu'il soit premier. Pour diminuer l'erreur, on fait plusieurs tests en modifiant les paramètres (ici les valeurs de a).

Rabin(n) =
{
  // Le seul nombre premier inférieur à 3 est 2
  Si (n<3) Retourne (n==2); 

  // Le seul nombre premier pair est 2
  Si ((n % 2)==0) Retourne (FAUX);

  // Calcule q et r tels que n-1=2^q*r
  q = n-1;
  r = 0;
  TantQue ((q % 2)==0)
  {
    q /= 2;
    r++;
  };

  / / Liste des nombres 'a' à tester
  Si (n<25326001) {
    lsta = {2};
  } sinon {
    // Vérifie que le nombre ne soit pas trop grand
    // (après je ne connais pas la liste des a :-( ...)
    Si (341 550 071 728 321 <= n) Erreur ("Nombre trop grand ...");
    lsta = {2,3,5,7,11,13,17}
  };

  savr = r;
  Pour (ia = 0, ia<Dim(lsta), ia++)
  {
    a = lsta[ia];
    m = a^q % n;
    r = savr;

    TantQue ((m<>1) et (r<>0))
    {
      savm = m;
      m ^= 2;
      m %= n;
      Si ((m == 1) et (savm<>n-1)) Retourne (FAUX);
      r--;
    };

    Si (m<>1) Retourne (FAUX);
  };

  Retourne(VRAI);
};

L'algorithme que je vous présente est « sûr » à 100%. Ceci est possible grâce à de nombreux tests qui ont cherchés les nombres délicats (nombres dits premiers avec une certaines valeur de a alors qu'ils sont composés). Ce n'est pas moi qui ait fait les tests, je les ai trouvés dans le livre [1].

[modifier] Algorithme de Miller-Bach (1985)

Autre algorithme probabiliste. Il est également sûr, mais beaucoup plus long car il va tester toutes les valeurs de a (de 2 à Ln(n)^2 ...).

Miller(n) =
{
  // Le seul nombre premier inférieur à 3 est 2
  Si (n<3) Retourne (n==2);

  // Le seul nombre premier pair est 2
  Si ((n % 2) == 0) Retourne (FAUX);

  // Calcule q tel que n-1=2^r*q
  q = n-1;
  r = 0;
  TantQue ((q % 2)==0)
  {
    q /= 2;
    r++;
  };

  a = 2;
  amax = PartieEntiere(Approx(2*(Ln(n))^2));
  Si (n <= amax) amax = n-1;
  TantQue (a <= amax)
  {
    m = a^q % n;
    Si (m<>1)
    {
      Si (r<>1)
      {
        ir=1;
        TantQue (m <> n-1)
        {
          m ^= 2;
          m %= n;
          ir++;
          Si (r < ir) Retourne (Faux);
        };
      } sinon {
        Si (m <> n-1) Retourne (FAUX);
      };
    };
    a++;
  };

  Retourne (VRAI);
};

Note: Ln(x) est le logarithme népérien de x.

[modifier] Algorithme de Lucas-Lehmer

Il permet de tester si nombre 2n - 1 est premier ou non.

Soit la suite U(k) définie par :

  • U0 = 4
  • Uk+1 ≡ (Uk² - 2) (modulo 2n - 1)

Alors 2n - 1 est premier si Un-1=0.

Lucas(n) =
{
  // 2^0-1=0 et 2^1-1=1 ne sont pas premier
  Si(n <= 1) Retourne(FAUX);

  // 2^2-1=3 est premier
  Si(n == 2) Retourne(VRAI);

  // Calcule 2^n-1
  nbr = 2^n-1;

  // Calcule la suite U(k)
  m = 4;
  Pour (i=2, i<n, i++)
  {
    m ^= 2;
    m -= 2;
    m %= nbr;
  };

  // 2^n-1 est premier si m=0
  Retourne(m == 0);
}

Valeurs de n telles que le nombre 2n - 1 soit premier : 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, ...

[modifier] Voir aussi

[modifier] Articles connexes

[modifier] Liens externes

Fonctions de HaypoCALC dans le manuel d'utilisation :

[modifier] Bibliographie

  • [1] « Merveilleux nombres premiers » de Jean-Pierre DELAHAYE aux éditions Pour la science (ISBN : 2-84245-017-5). C'est un très bon livre de vulgarisation.