Nombre premier: test de primalité

Comme annoncé dans mon dernier article, concernant l’algorithme de recherche des nombres premiers, nous allons nous pencher sur différents tests de primalité d’un point de vue plus mathématique. Néanmoins, cela devrait rester abordable, nul besoin de la connaissance des espaces vectoriels pour comprendre :D.

Méthode naïve:

Il suffit de diviser le nombre n dont on veut tester la primalité par tous les nombres de 2 à √n, car si n = p * q et dans ce cas, on a: p <= √n et q<= √n. En effet, supposons que        p >= q > √n; p > √n, q > √n; p*q > √n   -> absurde car n = p*q. On peut encore améliorer le test et ne tester que les nombres impairs une fois que la division par 2 a échoué. La complexité de ce test est exp( 1/2 * log n ).

Test de Fermat:

Rappel: Si n est premier et si a < n, alors a^(n-1) ≡ 1 mod n.                                 Conséquences:
Soit a < n,  Si a ^(n-1) ≠ 1 mod n alors n n’est pas premier.                                                 Ce test élimine mais ne confirme pas. Il est possible de déterminer si le nombre n’est pas premier. La réciproque est fausse.

Test de Lucas-Lehmer:

Si p est premier, le nombre de Mersenne Mp d’indice p est défini par: Mp = 2^p  –  1 .       On définit une suite Sn par S2 = 4 et Sn = (S(n-1))² – 2.                                                        Alors, Mp est premier ssi Mp divise Sp, c’est-à-dire: Sp ≡ 0 mod p.

Anonyme

Auteur/autrice : Victor

Ingénieur en informatique de formation et de métier, j’administre ce serveur et son domaine et privilégie l'utilisation de logiciels libres au quotidien. Je construis progressivement mon "cloud" personnel service après service pour conserver un certain contrôle sur mes données numériques.

2 réflexions sur « Nombre premier: test de primalité »

  1. Le test de primalité le plus simple est le suivant:
    Soit un nombre donné N. On ajoute et retranche l’unité à ce nombre: N+1 et N-1.
    Si l’un des deux nombres obtenus est un multiple de 6, ou est divisible par 6, la primalité du nombre donné est confirmée; dans le cas contraire, elle est infirmée.
    C’est aussi simple que cela !

    1. Hum …

      René, pourquoi des Fermat et Lucas-Lehmer se seraient cassé les méninges si c’était aussi simple que d’ajouter 1 et soustraire 1 ?

      Exemple du nombre 91
      91 – 1 = Divisible par 6,
      91 + 1 = Non divisible

      Hors 91 n’est pas un nombre premier !

Répondre à Bruno Adelé Annuler la réponse

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