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.
ordinateur aussi petit qu’une carte de crédit.