Sur le Nombre d'Entiers Réguliers Modulo $n$ et Son Importance pour la Cryptographie

Informations Fondamentales

• ID de l'article: 2304.02471
• Titre: On the Number of Regular Integers Modulo $n$ and Its Significance to Cryptography
• Auteurs: Klaus Dohmen, Mandy Lange-Geisler (Hochschule Mittweida, Allemagne)
• Classification: math.CO (Mathématiques Combinatoires), math.GR (Théorie des Groupes), math.NT (Théorie des Nombres)
• Date de publication: 9 octobre 2025 (version arXiv)
• Lien de l'article: https://arxiv.org/abs/2304.02471v6

Résumé

Cet article fournit quatre preuves combinatoires de la formule de Morgado concernant le nombre d'entiers réguliers modulo $n$, basées sur le principe de bijection et le principe d'inclusion-exclusion. Cette formule correspond à la séquence A055653 de l'OEIS, où un entier $m$ est dit régulier modulo $n$ si et seulement si l'équation de congruence $m^2x \equiv m \pmod{n}$ possède une solution dans l'anneau des entiers $\mathbb{Z}$. Pour souligner l'importance de cette recherche, les auteurs relient cette séquence et la formule de Morgado à une généralisation récemment proposée du système cryptographique RSA pour plusieurs nombres premiers à puissances multiples.

Contexte de Recherche et Motivation

Problème Central

La recherche résout le problème central du calcul du nombre d'entiers réguliers modulo $n$ et explore son importance dans les applications cryptographiques.

Importance du Problème

1. Signification théorique: Le concept d'entiers réguliers a été introduit pour la première fois par Morgado en 1972 et constitue un objet combinatoire important en théorie des nombres. Sa formule de comptage implique les facteurs unitaires et la fonction d'Euler, des concepts fondamentaux de la théorie des nombres.
2. Application pratique: Dans la généralisation du système RSA proposée par les auteurs, les entiers réguliers constituent l'espace des messages pouvant être correctement déchiffrés. Par conséquent, leur nombre est directement lié à la probabilité de correction du système cryptographique.

Limitations des Méthodes Existantes

Les preuves antérieures de la formule de Morgado reposaient principalement sur la propriété multiplicative de la fonction $\varrho(n)$, manquant d'une explication combinatoire intuitive. Cet article fournit une compréhension plus approfondie par des méthodes purement combinatoires.

Motivation de la Recherche

La motivation des auteurs provient des besoins pratiques rencontrés dans leur généralisation RSA multi-premiers à puissances multiples, nécessitant d'estimer la probabilité de déchiffrement correct pour un message arbitraire.

Contributions Principales

1. Quatre preuves combinatoires: Basées sur le principe de bijection et le principe d'inclusion-exclusion, quatre preuves différentes de la formule de Morgado sont fournies sous différents angles
2. Schéma de codage établi: La quatrième preuve fournit un codage explicite des entiers réguliers, potentiellement utile pour des recherches ultérieures sur la séquence A055653
3. Application cryptographique: Relie la théorie des entiers réguliers à la généralisation du système cryptographique RSA, révélant l'importance pratique de ce concept de théorie des nombres
4. Intuition théorique: Les méthodes combinatoires conduisent naturellement à la propriété multiplicative de la fonction $\varrho(n)$

Explication Détaillée de la Méthode

Définition de la Tâche

Entrée: Un entier positif $n$Sortie: Le nombre d'entiers réguliers modulo $n$, noté $\varrho(n)$Contrainte: Un entier $m$ est régulier modulo $n$ si et seulement s'il existe $x \in \mathbb{Z}$ tel que $m^2x \equiv m \pmod{n}$

Fondements Théoriques Principaux

Définition: Un entier $m$ est dit régulier modulo $n$ si l'équation de congruence $m^2x \equiv m \pmod{n}$ possède une solution entière.

Formule de Morgado (Théorème 1): $\varrho(n) = \sum_{d \parallel n} \varphi(d)$ où $d \parallel n$ signifie que $d$ est un facteur unitaire de $n$ (c'est-à-dire $d|n$ et $\gcd(d, n/d) = 1$).

Propriété clé (Proposition 2): Pour tout $n \in \mathbb{N}$ et $m \in \mathbb{Z}$, les conditions suivantes sont équivalentes:

• (a) $m$ est régulier modulo $n$
• (b) $\gcd(m^2, n) = \gcd(m, n)$
• (c) $\gcd(m, n) \parallel n$

Quatre Méthodes de Preuve

Méthode 1: Preuve par Relation d'Équivalence

En définissant une relation d'équivalence sur $\mathbb{Z}^{\text{reg}}_n$ par $m_1 \sim m_2 \Leftrightarrow \gcd(m_1, n) = \gcd(m_2, n)$, on établit une bijection entre les classes d'équivalence et $\mathbb{Z}^*_{n/d}$.

Méthode 2: Preuve Purement Bijective

Construction de l'application $f_n: \mathbb{Z}^{\text{reg}}_n \to \{(d, d') | d \parallel n, d' \in \mathbb{Z}^*_d\}$: $f_n(m) := \left(\frac{n}{\gcd(m,n)}, m \bmod \frac{n}{\gcd(m,n)}\right)$

L'application réciproque est: $f_n^{-1}(d, d') = \frac{n}{d}\left(((n/d \bmod d)^{-1}d') \bmod d\right)$

Méthode 3: Preuve par Fractions Irréductibles

Chaque $m \in \mathbb{Z}^{\text{reg}}_n$ est associé à une fraction irréductible $m/n$. On prouve que les dénominateurs de ces fractions irréductibles sont exactement tous les facteurs unitaires de $n$.

Méthode 4: Preuve par Principe d'Inclusion-Exclusion

Soit $P(n)$ l'ensemble des facteurs premiers de $n$. Pour chaque nombre premier $p \in P(n)$, on définit: $A_p = \{m \in \mathbb{Z}_n | 0 < m_p < n_p\}$ où $m_p$ désigne la multiplicité de $p$ dans la décomposition en facteurs premiers de $m$, puis on applique le principe d'inclusion-exclusion.

Points d'Innovation Technique

1. Perspective combinatoire: Contrairement aux preuves antérieures basées sur la multiplicativité, cet article fournit une explication combinatoire intuitive
2. Construction bijective: La deuxième preuve fournit un codage et un décodage explicites des entiers réguliers
3. Analyse multi-angulaire: Les quatre preuves révèlent la structure essentielle des entiers réguliers sous différents angles
4. Lien cryptographique: Première connexion établie entre la théorie des entiers réguliers et les applications cryptographiques modernes

Configuration Expérimentale

Vérification Numérique

L'article vérifie les résultats théoriques par des exemples concrets:

Exemple: Cas de $n = 20$

• Facteurs unitaires: $1, 4, 5, 20$
• $\varphi(1) = 1, \varphi(4) = 2, \varphi(5) = 4, \varphi(20) = 8$
• Valeur prédite: $\varrho(20) = 1 + 2 + 4 + 8 = 15$
• Entiers réguliers réels: $\{0, 1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19\}$
• Vérification: $|\mathbb{Z}^{\text{reg}}_{20}| = 15$ ✓

Exemple de Mapping

L'article présente en détail toutes les correspondances de l'application $f_{20}$, vérifiant la correction de la bijection.

Résultats Expérimentaux

Vérification Théorique

Les quatre preuves établissent avec succès la correction de la formule de Morgado, chaque méthode fournissant une intuition combinatoire unique.

Résultats d'Application Cryptographique

Dans la généralisation RSA multi-premiers à puissances multiples:

• Probabilité de déchiffrement correct: $\frac{\varrho(n)}{n} = \frac{1}{n}\sum_{d \parallel n} \varphi(d)$
• Estimation inférieure: Pour $n = p_1^{e_1} \cdots p_r^{e_r}$ (où $p_i$ sont des nombres premiers de $k$ bits), on a $\frac{\varrho(n)}{n} \geq 1 - \frac{r}{2^{k-1}}$
• Signification pratique: Lorsque $k = 1024$, presque tous les messages peuvent être correctement déchiffrés

Travaux Connexes

Développement Historique

1. Morgado (1972): Première introduction du concept d'entiers réguliers et formule de comptage
2. Alkam & Osba (2008): Recherche ultérieure sur les propriétés des entiers réguliers
3. Apostol & Petrescu (2013): Étude des propriétés extrêmes des fonctions connexes
4. Tóth (2008): Résultats asymptotiques et analyse des fonctions connexes

Contribution de cet Article

Par rapport aux travaux existants, cet article fournit pour la première fois des méthodes purement combinatoires et établit des connexions importantes avec la cryptographie.

Conclusions et Discussion

Conclusions Principales

1. La formule de Morgado possède des interprétations combinatoires riches; chaque preuve révèle une structure à différents niveaux
2. Les entiers réguliers jouent un rôle clé dans la généralisation du système cryptographique RSA
3. Pour les choix de paramètres pratiques, la probabilité de déchiffrement correct est proche de 1

Limitations

1. L'application cryptographique se limite à une généralisation RSA spécifique
2. L'analyse asymptotique mérite une recherche ultérieure
3. L'analyse de la complexité computationnelle n'est pas suffisamment approfondie

Directions Futures

1. Développer des limites probabilistes plus précises
2. Étudier les propriétés asymptotiques de la séquence A055653
3. Explorer d'autres applications cryptographiques

Évaluation Approfondie

Points Forts

1. Innovation théorique: Les quatre preuves combinatoires sont chacune distinctives et enrichissent la compréhension des entiers réguliers
2. Rigueur méthodologique: Les processus de preuve sont rigoureux et la logique est claire
3. Valeur applicative: La connexion avec la cryptographie renforce l'importance pratique de la recherche théorique
4. Clarté de la Présentation: La structure de l'article est rationnelle et les exemples sont abondants

Insuffisances

1. Limitations d'Application: L'application cryptographique se limite à la généralisation RSA proposée par les auteurs
2. Analyse Computationnelle: Manque d'analyse approfondie de la complexité algorithmique
3. Vérification Expérimentale: Seule une vérification numérique à petite échelle est présente; les expériences de calcul à grande échelle font défaut

Impact

1. Valeur Académique: Fournit de nouvelles perspectives de recherche pour la combinatoire en théorie des nombres
2. Potentiel Pratique: Possède une valeur d'application potentielle en cryptographie
3. Reproductibilité: Les preuves théoriques sont complètes et les résultats sont faciles à vérifier

Scénarios Applicables

1. Recherche théorique en théorie des nombres et mathématiques combinatoires
2. Scénarios cryptographiques impliquant des opérations modulaires
3. Applications nécessitant le calcul de la taille d'ensembles d'entiers spéciaux

Références Bibliographiques

L'article cite 8 références connexes, couvrant l'évolution principale de la théorie des entiers réguliers et les fondements mathématiques connexes, fournissant aux lecteurs une connaissance contextuelle complète.

Évaluation Globale: Ceci est un article mathématique de haute qualité qui approfondit la compréhension d'un problème classique de théorie des nombres par plusieurs méthodes combinatoires et établit avec succès une connexion avec la cryptographie moderne. Les contributions théoriques de l'article sont solides et ses perspectives d'application sont vastes, ce qui en fait un travail de valeur dans le domaine de la combinatoire en théorie des nombres.