Fermat Little Theorem

Petit théorème de Fermat : si p est premier et gcd(a,p)=1, alors a^(p-1)≡1 (mod p) ; il fonde les tests de primalité et les inverses modulaires.

Objectif

Fournir une simplification rapide des exponentiations modulaires et la base théorique des tests de primalité.

Mécanisme

a^(p-1)≡1 (mod p) implique a^(-1)≡a^(p-2) (mod p) (inverse modulaire). Test de primalité de Fermat : choisir un a aléatoire et vérifier a^(n-1)≡1 (mod n) ; un échec prouve que n est composé. Cependant, les nombres de Carmichael passent tous les tests de Fermat.

Cas d’usage

Tests de primalité
Calcul d'inverses modulaires
Fondements cryptographiques

Outils associés

Vérificateur de nombres premiers

Prime Checker — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur.

Exponentiation modulaire

Modular Exponentiation — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur.

Test de primalité de Lucas

Lucas Primality Test — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur. Avertissement : l'implémentation actuelle utilise une simple division d'essai (équivalente à prime-checker), pas le vrai test de primalité de Lucas avec suites de Lucas.

References