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.

Victor

Auteur : Victor

Libriste convaincu, 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.

Une réflexion 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 !

Laisser un commentaire

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