Cryptographie · Interactif

Petit théorème de Fermat

Exploration numérique : pour p premier et a non multiple de p, on vérifie que a^(p−1) ≡ 1 (mod p).

Premier p Entier a (1 ≤ a < p)

a^p−1 mod p —

Ordre de a —

Divise p−1 ? —

—

Le petit théorème de Fermat affirme que a^p−1 ≡ 1 (mod p) dès que p est premier et que a n'est pas divisible par p. La ligne ci-dessus montre les puissances successives : la dernière case est toujours 1, quelle que soit la valeur de a. L'ordre de a est le plus petit exposant pour lequel on retombe sur 1 ; il divise toujours p−1 (théorème de Lagrange).

Voir dans son contexte RSA : Grand Oral maths expertes