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