Nombres premiers

Cette fiche présente les méthodes de test des nombres premiers utilisées par Up ! Mathematical :

Test de Fermat.
Test de Miller et Rabin.
Test de Solovay et Strassen.

Test de Fermat

Soit N le nombre dont cherche s'il est premier ou non.

Pour tout nombre entier A tel que 1 < A < N-1, si A^(N-1) % N est différent de 1, alors N n'est pas premier.

Le test précédent est répété NbIterations fois pour avoir une probabilité assez fiable de l'affirmation.

Test de Miller et Rabin

Soit N le nombre dont cherche s'il est premier ou non.

On calcule d'abord les nombres D et S tels que 2^S*D=N-1.

Pour tout nombre entier A tel que 1 < A < N-1, si A^D % N est différent de 1 et si, pour tout R tel que 0 < R < S-1, A^(2^R*D) % N est différent de N-1, alors N n'est pas premier.

Le test précédent est répété NbIterations fois pour avoir une probabilité assez fiable de l'affirmation.

Test de Solovay et Strassen

Soit N le nombre dont cherche s'il est premier ou non.

Pour tout nombre entier A tel que 1 < A < N-1 :

On calcule le nombre X tel que X=A % N.
Si X est égal à 0 ou si A^((N-1)/2) est différent de X alors N n'est pas premier.

Le test précédent est répété NbIterations fois pour avoir une probabilité assez fiable de l'affirmation.