#mathematiques

Le petit théorème de Fermat stipule que

• pour un nombre premier p
• pour un nombre entier a, tel que a % p != 0 (p n’est pas un multiple de a)

Alors a^(p-1) % p = 1

Ce théorème peut être utilisé pour créer un algorithme probabiliste de recherche de nombre premier.

Soit un nombre q, pour lequel on souhaite déterminer si il est premier ou non.

• Si on trouve un nombre a tel que a^(q-1) % q != 1, alors q n’est pas premier (Fermat Witness)
• Attention: La contraposée n’est pas vraie : il est possible que a^(q-1) % q = 1, sans que q soit premier (Fermat Liar). Pour un nombre a < p, cela n’arrive qu’avec un probabilité de ¹⁄₂. Donc il suffit d’essayer aléatoirement d’autres valeurs de a pour augmenter les chances que q soit effectives premier.