Nombre premier et tests probabilistes.

Rappelons tout d'abord le petit théorème de Fermat :
Si p est un nombre premier, et si a est un entier naturel qui n'est pas multiple de p, c'est à dire p ne divise pas a, alors:

On peut appliquer ce théorème à la recherche de primalité d'un nombre. En effet si un nombre n est premier alors tous les nombres a strictement inférieurs à n sont premiers avec n et si n n'est pas premier, les nombres entiers a qui vérifient a^n-1  ≣ 1 (n) sont infiniment peu nombreux. Ils existent cependant, faites une recherche sur les nombres de Carmichael.

Il est prouvé que la probabilité que la réponse à ce test soit juste est de 1/2.
On en déduit qu'un nombre n qui vérifie a^n-1  ≣ 1 (n) pour 20 tirages au hasard de a est donc un nombre très certainement premier (pseudo-premier en fait) et ceci avec une erreur de l'ordre de (1/2)²⁰ .
On ne peut certes rien conclure de "sûr" car la réciproque du théorème de Fermat est évidemment fausse : on peut juste dire qu'il y a seulement une très forte probabilité pour que ce nombre n soit premier. On parle parfois de réciproque probabiliste du théorème de Fermat. Voilà donc en tout cas pourquoi on appelle ces tests des tests probabilistes ;-)

Il existe une variante de ce test un peu plus complexe arithmétiquement parlant, qui est le test de Rabin et qui augmente sensiblement la probabilité d'obtenir une réponse correcte pour des nombres vraiment très grands. Peut être l'objet d'un prochain article...

Revenons maintenant à notre algorithme de primalité avec Fermat qui est assez simple. On effectue donc nos 20 itérations (vous pouvez tester d'autres valeurs) :

Tant que ( J = 1 et I < 21 )
{   
On choisit un nombre A au hasard tel que 1 < A < N-1   
On affecte A Puissance N-1 Modulo N à J   
On incrémente I d'une unité
}
Si ( J = 1)  Alors ( N est probablement premier) Sinon ( N est non premier)

Voici le programme associé qui utilise la fonction POWMOD d'exponentiation modulaire de la HP-50G. Quand au nombre A pris au hasard il est construit en utilisant la fonction RAND qui ne prends aucun argument et renvoie un réel r tel que 0 ≤ r < 1. On effectue un décalage affine pour prendre A strictement plus grand que 1 et strictement plus petit que N-1.

<< 1 0 ⟶ N I H
  <<
    1 SF 0 RDZ N MODSTO
    WHILE 1 FS? I 21 < AND
    REPEAT
      RAND N 2 - * FLOOR 2 + 'H' STO
      IF H N 1 - POWMOD 1 == NOT
      THEN 1 CF
      ELSE 1 'I' STO+
      END
    END 1 FS?
  >> CASCFG
>>

L'instruction CASCFG remets le modulo par défaut du CAS à 13. Enregistrez et utilisez ce programme comme de coutume, le nombre à tester doit être sur le niveau 1 du stack. Le programme renvoie 1 si le nombre est très probablement premier, 0 sinon.

Voici quelques nombres à tester: 412343 est premier, 785523 est non premier, 1138117 est premier, 1999601 est non premier et 1999993 est premier.
Pour exercice vous pouvez comparer les temps d'exécutions de ce programme avec le test probabiliste de Fermat et de celui du précédent article avec la méthode simpliste (naive).

Certes cet article manque de rigueur mathématique mais il s'adresse à des élèves de lycée et tout ceci pourrait être un bon exercice autour du théorème de Fermat pour l'épreuve de Spé Maths de ce lundi au bac ;-)

Liens intéressants:
Test de Fermat.

A bientôt !