Tester la primalité d'un grand nombre

Reconnaître qu'un nombre est premier est facile quand il est petit. Pour un nombre de 300 chiffres, la question devient un problème algorithmique — et sa réponse fonde la cryptographie moderne.

Le coût du test naïf

Tester tous les diviseurs jusqu'à √n demande environ √n divisions :

n = 10⁶      ->  1 000 divisions          instantané
n = 10¹⁸     ->  10⁹ divisions            quelques secondes
n = 10⁶⁰⁰    ->  10³⁰⁰ divisions          au-delà de l'âge de l'univers

Or les clés RSA utilisent des premiers de 300 chiffres. Il faut donc un test qui ne cherche aucun diviseur.

Le petit théorème de Fermat

Si p est premier et si a n'est pas divisible par p, alors a^(p-1) ≡ 1 (mod p).

L'idée : cette égalité est facile à vérifier — l'exponentiation modulaire rapide la calcule en quelques centaines d'opérations, même sur 300 chiffres. Si elle échoue, n est certainement composé.

n = 15,  a = 2 :   2¹⁴ mod 15 = 4  ≠ 1     ->  15 est COMPOSÉ, à coup sûr

Remarquable : on a prouvé que 15 est composé sans trouver aucun de ses facteurs. Le test détecte la composition sans la factorisation — exactement ce dont on a besoin.

Le piège des pseudo-premiers

La réciproque est fausse. Certains composés passent le test :

n = 341 = 11 × 31,  a = 2 :   2³⁴⁰ mod 341 = 1        ->  test RÉUSSI
                                                          et pourtant composé

341 est un pseudo-premier de base 2. Il suffit d'essayer une autre base pour le démasquer (3³⁴⁰ mod 341 ≠ 1). Mais il existe pire : les nombres de Carmichael (561, 1105, 1729…) passent le test pour toutes les bases premières avec eux.

Miller-Rabin : le test utilisé en pratique

Il raffine celui de Fermat en exploitant une propriété supplémentaire des racines carrées de 1 modulo un premier, ce qui neutralise les nombres de Carmichael.

Test probabiliste :
   - si n échoue pour une base  ->  n est COMPOSÉ, avec certitude
   - si n réussit pour k bases  ->  n est premier avec une probabilité
                                    d'erreur inférieure à 4^(-k)

k = 20 bases  ->  probabilité d'erreur < 10⁻¹²
k = 40 bases  ->  < 10⁻²⁴, moins probable qu'une erreur matérielle du processeur

C'est ce que fait votre navigateur, en quelques millisecondes, chaque fois qu'il établit une connexion sécurisée. Un test déterministe en temps polynomial existe depuis 2002 — l'algorithme AKS —, mais il reste plus lent en pratique : Miller-Rabin garde la préférence.

L'asymétrie qui protège vos communications

Multiplier deux premiers de 300 chiffres     ->  microsecondes
Tester si un nombre de 300 chiffres est premier -> millisecondes
FACTORISER un produit de 600 chiffres        ->  aucun algorithme connu
                                                 en temps raisonnable

Voilà toute l'idée de RSA : on sait fabriquer et vérifier facilement, mais pas défaire. Le record public de factorisation porte sur 250 chiffres, obtenu en 2020 après environ 2 700 années-cœur de calcul.

Deux réserves honnêtes, cependant :

• rien ne prouve que la factorisation soit intrinsèquement difficile ; un algorithme rapide pourrait être découvert demain ;
• l'algorithme de Shor factorise en temps polynomial sur un ordinateur quantique. Aucune machine de taille suffisante n'existe aujourd'hui, mais c'est ce qui motive le développement de la cryptographie post-quantique.

En résumé

• Le test par divisions jusqu'à √n est inutilisable au-delà de quelques dizaines de chiffres.
• Petit théorème de Fermat : a^(p-1) ≡ 1 (mod p) — vérifiable sans factoriser.
• Sa réciproque est fausse : pseudo-premiers et nombres de Carmichael.
• Miller-Rabin est probabiliste : erreur < 4^(-k), négligeable dès 40 bases.
• Fabriquer et tester est facile, factoriser est hors de portée : c'est le socle de RSA.
• Cette difficulté est conjecturale, et l'algorithme de Shor la lèverait sur machine quantique.