🔢 mathematics

Ours go to 211: Euler pseudoprimes to 47 prime bases (from Carmichael numbers)

Cet article présente une classification des nombres de Carmichael et un algorithme rapide pour générer de nouveaux pseudopremiers d'Euler, permettant de découvrir un nombre composé résistant aux tests de primalité pour les 47 premières bases premières, soit jusqu'à 211.

Auteurs originaux : Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange, Benne de Weger

Publié 2026-02-26

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange, Benne de Weger

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🕵️‍♂️ La Chasse aux "Faux-Primes" : Comment tromper les mathématiciens jusqu'à 211

Imaginez que vous êtes un gardien de trésor (un cryptographe). Pour protéger votre coffre-fort, vous avez besoin de clés spéciales appelées nombres premiers. Ces nombres sont comme des blocs de pierre indivisibles : on ne peut pas les casser en deux.

Pour trouver ces blocs, les ordinateurs en testent des milliers au hasard. Mais vérifier si un nombre est vraiment un bloc de pierre (premier) ou juste un tas de cailloux collés ensemble (composé) prend beaucoup de temps. Alors, on utilise des tests rapides, comme des portails de sécurité.

1. Le Problème : Les Caméléons Mathématiques

Certains nombres composés sont de véritables caméléons. Ils ressemblent tellement à des nombres premiers qu'ils réussissent à passer les tests de sécurité. On les appelle des pseudoprimes (faux-primes).

Le test Solovay-Strassen est l'un de ces portails. Il pose une question mathématique au nombre. Si le nombre répond correctement, le portail s'ouvre.
Normalement, un faux-prime se fait attraper très vite. Mais certains sont si forts qu'ils réussissent à répondre correctement à plusieurs questions de suite, en utilisant différentes "clés" (appelées bases).

L'objectif de cette équipe de chercheurs (Alejandra, Jolijn, Tanja et Benne) était de créer le meilleur caméléon de l'histoire. Ils voulaient un nombre qui réussisse à tromper le portail de sécurité non pas une fois, mais 47 fois de suite, en utilisant les 47 premières clés possibles (les nombres premiers de 2 à 211).

2. La Stratégie : Construire un "Monstre" avec des Briques

Pour créer ce monstre mathématique, ils n'ont pas cherché au hasard. Ils ont utilisé une recette secrète basée sur une catégorie spéciale de faux-primes appelés nombres de Carmichael.

Imaginez que les nombres de Carmichael sont des briques de Lego très spéciales.

La classe A (Les briques parfaites) : Les chercheurs ont découvert que certaines de ces briques (la "Classe A") sont plus faciles à assembler pour créer un faux-prime solide. Elles ont une propriété magique : elles répondent toujours "Oui" à la moitié des questions possibles.
L'assemblage : Au lieu de chercher une seule brique géante, ils ont pris plusieurs petites briques (des nombres de Carmichael qu'ils avaient déjà trouvés) et les ont multipliées entre elles.
- Analogie : C'est comme si vous preniez deux caméléons qui savent se cacher dans l'herbe, et que vous les colliez ensemble pour créer un caméléon qui peut se cacher dans l'herbe ET dans les buissons en même temps.

3. L'Algorithme : Le Chef d'Orchestre

Les chercheurs ont écrit un programme (un algorithme) qui agit comme un chef d'orchestre très rigoureux :

Il prend deux nombres qui ont déjà réussi à tromper le portail jusqu'à un certain niveau (par exemple, jusqu'à la clé 37).
Il vérifie s'ils sont compatibles (comme vérifier si deux pièces de puzzle s'emboîtent).
Il les multiplie pour créer un nombre plus grand.
Il teste ce nouveau nombre. S'il réussit encore mieux (par exemple, jusqu'à la clé 41), il le garde pour la prochaine étape.

Ils ont répété ce processus en couches successives :

D'abord, ils ont combiné des briques simples.
Ensuite, ils ont combiné les résultats pour faire des briques plus grosses.
Puis des briques encore plus grosses...

4. Le Résultat : Le Record du Monde

Après des mois de calculs et des milliards de combinaisons testées, ils ont réussi.

Ils ont créé un nombre astronomique (qui fait 1230 chiffres, soit plus long que ce livre entier !). Ce nombre est un pseudoprime d'Euler.

Il a réussi à passer le test de sécurité avec la clé 2.
Puis la clé 3, 5, 7, 11...
Il a continué sans se faire attraper jusqu'à la clé 211.

C'est comme si un imposteur avait réussi à traverser 47 portails de sécurité différents, en utilisant 47 identités différentes, sans jamais être démasqué. C'est le record actuel pour ce type de test.

5. Pourquoi est-ce important ?

Vous pourriez vous demander : "À quoi sert de créer un faux-prime aussi fort ?"

C'est une question de sécurité.

Les systèmes qui protègent vos données bancaires ou vos messages privés (comme le RSA) reposent sur la difficulté de distinguer un vrai nombre premier d'un faux.
En créant le "meilleur" faux-prime possible, les chercheurs prouvent que les tests actuels sont très forts, mais qu'il faut toujours rester vigilant.
C'est un peu comme un test de sécurité informatique : les pirates essaient de trouver des failles. Ici, les chercheurs ont construit le "pirate ultime" pour voir si les gardiens (les algorithmes) tiennent bon. Heureusement, pour la plupart des gens, les tests sont encore suffisants, mais cette découverte aide à améliorer les futurs systèmes de sécurité.

En résumé

Cette équipe a utilisé des mathématiques avancées pour assembler des "briques" spéciales (nombres de Carmichael) et construire un nombre géant capable de se faire passer pour un nombre premier 47 fois de suite. C'est une victoire de l'intelligence mathématique sur la complexité, prouvant que même les meilleurs tests peuvent être trompés si l'on connaît la bonne recette.

Résumé Technique : Pseudopremiers d'Euler jusqu'à 211

1. Problématique et Contexte

Les systèmes cryptographiques à clé publique (comme RSA et Diffie-Hellman) dépendent de la génération de grands nombres premiers. Pour accélérer ce processus, les implémentations utilisent des tests de primalité probabilistes tels que le test de Solovay-Strassen ou celui de Miller-Rabin.

Le problème : Un nombre composé qui passe ces tests est appelé un pseudopremier. Si un attaquant peut fournir des pseudopremiers capables de résister à un grand nombre de bases de test, il peut tromper les systèmes de génération de clés.
Spécificité du papier : L'article se concentre sur le test de Solovay-Strassen, basé sur le critère d'Euler :
$\left(\frac{a}{n}\right) \equiv a^{\frac{n-1}{2}} \pmod n$
Un nombre composé $n$ qui satisfait cette équation pour une base $a$ est un pseudopremier d'Euler (et $a$ est un "menteur d'Euler"). Contrairement aux nombres de Carmichael (qui sont des pseudopremiers de Fermat pour toutes les bases), il n'existe pas de nombre composé qui soit un pseudopremier d'Euler pour toutes les bases. Cependant, l'objectif est de trouver des nombres qui survivent au test pour le plus grand nombre possible de bases consécutives (en commençant par 2).

2. Méthodologie

Les auteurs ont développé une approche systématique basée sur l'analyse théorique des nombres de Carmichael et une stratégie algorithmique de multiplication.

A. Classification des Nombres de Carmichael
Les auteurs ont identifié que les nombres de Carmichael sont les meilleurs candidats pour les pseudopremiers d'Euler, car tout menteur d'Euler est aussi un menteur de Fermat. Ils ont classé les nombres de Carmichael en catégories basées sur l'indice $i(n) = \frac{n-1}{\lambda(n)}$ (où $\lambda$ est la fonction de Carmichael) et la valuation 2-adique des facteurs premiers.

Classe A : $i(n)$ est pair. Ces nombres possèdent $\frac{1}{2}\phi(n)$ menteurs d'Euler (la proportion maximale possible). Pour ces nombres, le terme exponentiel $a^{\frac{n-1}{2}}$ est toujours congru à 1 modulo $n$ .
Classes B1 et B2 : $i(n)$ est impair. La proportion de menteurs est inférieure ou égale à celle de la classe A.
Conclusion clé : Pour maximiser la survie aux tests, il faut privilégier les nombres de la Classe A.

B. Stratégie de Multiplication
Au lieu de chercher des nombres aléatoirement, les auteurs utilisent une approche constructive :

Filtrage initial : Ils partent d'une liste de "nombres de Carmichael atomiques" (non produits d'autres nombres de Carmichael) avec des facteurs premiers supérieurs à 150 (pour éviter les échecs immédiats sur les petites bases).
Multiplication : Ils multiplient des pseudopremiers d'Euler existants pour en créer de plus grands.
- Théorème clé (Lemme 13) : Si l'on multiplie deux nombres de la Classe A ( $n_1, n_2$ ) qui survivent tous deux jusqu'à une base $a$ , leur produit $n = n_1 n_2$ (s'il reste un nombre de Carmichael de Classe A) survivra au moins jusqu'à la base suivante ($NextPrime(a)$).
- Condition de succès : Pour que le produit reste dans la Classe A, il faut que $\min(v_2(n_1-1), v_2(n_2-1)) > \max(v_2(\lambda(n_1)), v_2(\lambda(n_2)))$ .
Algorithme (Algorithm 1) : Un algorithme efficace vérifie ces conditions de valuation 2-adique et de PGCD avant de calculer le produit et de tester la primalité des bases suivantes. Cela permet d'éliminer rapidement les combinaisons non valides.

C. Optimisation par Symétrie
Pour atteindre des nombres très grands, les auteurs privilégient les constructions symétriques (ex: multiplier deux éléments de $epsp_2(a)$ pour obtenir un élément de $epsp_4(a)$ ). Cela réduit l'espace de recherche tout en maintenant un taux de succès élevé.

3. Résultats Principaux

Record de survie : Les auteurs ont trouvé un pseudopremier d'Euler qui survit aux 47 premières bases premières (de 2 à 211).
- Le nombre trouvé est un entier de 1230 bits.
- Il passe le test de Solovay-Strassen pour toutes les bases $a \in \{2, 3, 5, \dots, 211\}$ .
Statistiques de recherche :
- Ils ont généré des millions de candidats en multipliant des nombres atomiques.
- La classe A domine massivement les résultats (plus de 99,97 % des produits valides sont de classe A).
- Une observation importante : les nombres trouvés sont presque toujours congrus à $1 \pmod{120}$ , ce qui correspond à des propriétés de résidus favorisant le symbole de Jacobi égal à 1.
Échec de l'approche par produit massif : En essayant de multiplier des nombres déjà très grands (plus de 16 facteurs atomiques), ils ont constaté un taux d'échec élevé dû à la perte de la propriété "sans carré" (square-free), car les facteurs premiers des nombres de départ partagent trop de diviseurs communs.

4. Contributions Clés

Classification Théorique : Une caractérisation fine des nombres de Carmichael (Classes A, B1, B2) déterminant précisément le nombre de menteurs d'Euler pour chaque classe.
Algorithme de Construction : Une méthode efficace pour générer des pseudopremiers d'Euler de plus en plus grands en multipliant des nombres de la Classe A, garantissant théoriquement la survie à la base suivante.
Nouveau Record : Établissement d'un nouveau record pour les pseudopremiers d'Euler (survie jusqu'à 211), surpassant les précédents records pour le test de Miller-Rabin (12 bases) et Solovay-Strassen.
Nouvelle Classe de Nombres : Introduction des "pseudopremiers de Sophie Germinus" (produits de nombres de la forme $p(2p-1)$ ) comme une alternative potentielle, bien que moins performante que les nombres de Carmichael pour cet objectif spécifique.

5. Signification et Impact

Sécurité Cryptographique : Ce travail démontre que la recherche de nombres premiers pour RSA doit être extrêmement rigoureuse. Un attaquant disposant de ces pseudopremiers pourrait potentiellement contourner les tests de primalité standards si ceux-ci ne sont pas exécutés avec suffisamment de bases aléatoires ou si l'adversaire contrôle la sélection des nombres.
Limites des Tests Probabilistes : Bien que le test de Miller-Rabin soit souvent préféré (avec un taux d'erreur de 1/4 contre 1/2 pour Solovay-Strassen), ce papier montre que des nombres composés peuvent être construits pour résister à un nombre très élevé de bases, rendant le test déterministe ou l'utilisation de bases aléatoires multiples indispensable.
Recherche Future : Les auteurs suggèrent que la construction de nombres de Carmichael via la méthode d'Erdős (où $n \equiv 1 \pmod L$ ) pourrait être une voie alternative pour générer de tels nombres, et posent des conjectures sur la structure des nombres ayant un nombre maximal de menteurs d'Euler.

En résumé, ce papier combine théorie des nombres et algorithmique pour repousser les limites de la compréhension des échecs des tests de primalité, fournissant des contre-exemples extrêmes qui servent de "stress tests" pour la sécurité des infrastructures cryptographiques.