Sobre el Número de Enteros Regulares Módulo $n$ y Su Significancia para la Criptografía

Información Básica

• ID del Artículo: 2304.02471
• Título: On the Number of Regular Integers Modulo $n$ and Its Significance to Cryptography
• Autores: Klaus Dohmen, Mandy Lange-Geisler (Hochschule Mittweida, Alemania)
• Clasificación: math.CO (Matemática Combinatoria), math.GR (Teoría de Grupos), math.NT (Teoría de Números)
• Fecha de Publicación: 9 de octubre de 2025 (versión arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2304.02471v6

Resumen

Este artículo proporciona cuatro pruebas combinatorias de la fórmula de Morgado sobre el número de enteros regulares módulo $n$, basándose en el principio de biyección y el principio de inclusión-exclusión. La fórmula corresponde a la secuencia A055653 en OEIS, donde un entero $m$ se denomina regular módulo $n$ si y solo si la ecuación de congruencia $m^2x \equiv m \pmod{n}$ tiene solución en el anillo de enteros $\mathbb{Z}$. Para enfatizar la importancia de esta investigación, los autores vinculan esta secuencia y la fórmula de Morgado con una generalización recientemente propuesta del sistema criptográfico RSA con múltiples primos y potencias múltiples.

Antecedentes de Investigación y Motivación

Problema Central

La investigación aborda el problema central de calcular el número de enteros regulares módulo $n$ y explorar su significancia en aplicaciones criptográficas.

Importancia del Problema

1. Significancia Teórica: El concepto de enteros regulares fue introducido por primera vez por Morgado en 1972 y constituye un objeto combinatorio importante en la teoría de números. Su fórmula de conteo involucra factores unitarios y la función de Euler, conceptos fundamentales de la teoría de números.
2. Aplicación Práctica: En la generalización del sistema criptográfico RSA propuesta por los autores, los enteros regulares constituyen el espacio de mensajes que se descifran correctamente, por lo que su número se relaciona directamente con la probabilidad de corrección del sistema criptográfico.

Limitaciones de Métodos Existentes

Las pruebas anteriores de la fórmula de Morgado se basaban principalmente en la propiedad multiplicativa de la función $\varrho(n)$, careciendo de una explicación combinatoria intuitiva. Este artículo proporciona una comprensión más profunda mediante métodos puramente combinatorios.

Motivación de la Investigación

La motivación de los autores surge de necesidades prácticas encontradas en su generalización de RSA con múltiples primos y potencias múltiples, requiriendo estimar la probabilidad de descifrado correcto para mensajes arbitrarios.

Contribuciones Principales

1. Cuatro Pruebas Combinatorias: Basándose en el principio de biyección y el principio de inclusión-exclusión, se proporcionan cuatro pruebas combinatorias diferentes de la fórmula de Morgado desde distintos ángulos.
2. Esquema de Codificación Establecido: La cuarta prueba proporciona una codificación explícita de enteros regulares, que puede ser valiosa para investigaciones futuras de la secuencia A055653.
3. Aplicaciones Criptográficas: Se vincula la teoría de enteros regulares con la generalización del sistema criptográfico RSA, revelando la significancia práctica de este concepto de teoría de números.
4. Perspectivas Teóricas: Los métodos combinatorios conducen naturalmente a la propiedad multiplicativa de la función $\varrho(n)$.

Explicación Detallada de Métodos

Definición de Tareas

Entrada: Entero positivo $n$Salida: Número de enteros regulares módulo $n$, $\varrho(n)$Restricciones: Un entero $m$ es regular módulo $n$ si y solo si existe $x \in \mathbb{Z}$ tal que $m^2x \equiv m \pmod{n}$

Fundamentos Teóricos Principales

Definición: Un entero $m$ se denomina regular módulo $n$ si la ecuación de congruencia $m^2x \equiv m \pmod{n}$ tiene solución entera.

Fórmula de Morgado (Teorema 1): $\varrho(n) = \sum_{d \parallel n} \varphi(d)$ donde $d \parallel n$ denota que $d$ es un factor unitario de $n$ (es decir, $d|n$ y $\gcd(d, n/d) = 1$).

Propiedades Clave (Proposición 2): Para cualquier $n \in \mathbb{N}$ y $m \in \mathbb{Z}$, las siguientes condiciones son equivalentes:

• (a) $m$ es regular módulo $n$
• (b) $\gcd(m^2, n) = \gcd(m, n)$
• (c) $\gcd(m, n) \parallel n$

Cuatro Métodos de Prueba

Método 1: Prueba por Relación de Equivalencia

Se define una relación de equivalencia en $\mathbb{Z}^{\text{reg}}_n$ como $m_1 \sim m_2 \Leftrightarrow \gcd(m_1, n) = \gcd(m_2, n)$, estableciendo una biyección entre las clases de equivalencia y $\mathbb{Z}^*_{n/d}$.

Método 2: Prueba Puramente Biyectiva

Se construye la aplicación $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)$

La aplicación inversa es: $f_n^{-1}(d, d') = \frac{n}{d}\left(((n/d \bmod d)^{-1}d') \bmod d\right)$

Método 3: Prueba de Fracciones Irreducibles

Se corresponde cada $m \in \mathbb{Z}^{\text{reg}}_n$ con la fracción irreducible $m/n$, probando que los denominadores de estas fracciones irreducibles son precisamente todos los factores unitarios de $n$.

Método 4: Prueba por Principio de Inclusión-Exclusión

Sea $P(n)$ el conjunto de factores primos de $n$. Para cada primo $p \in P(n)$ se define: $A_p = \{m \in \mathbb{Z}_n | 0 < m_p < n_p\}$ donde $m_p$ denota la multiplicidad de $p$ en la factorización prima de $m$, aplicándose luego el principio de inclusión-exclusión.

Puntos de Innovación Técnica

1. Perspectiva Combinatoria: A diferencia de las pruebas anteriores basadas en multiplicatividad, este artículo proporciona una explicación combinatoria intuitiva.
2. Construcción Biyectiva: La segunda prueba proporciona un algoritmo explícito de codificación y decodificación de enteros regulares.
3. Análisis Multiangular: Las cuatro pruebas revelan la estructura esencial de los enteros regulares desde diferentes ángulos.
4. Conexión Criptográfica: Se vincula por primera vez la teoría de enteros regulares con aplicaciones criptográficas modernas.

Configuración Experimental

Verificación Numérica

El artículo verifica los resultados teóricos mediante ejemplos concretos:

Ejemplo: Caso $n = 20$

• Factores unitarios: $1, 4, 5, 20$
• $\varphi(1) = 1, \varphi(4) = 2, \varphi(5) = 4, \varphi(20) = 8$
• Valor predicho: $\varrho(20) = 1 + 2 + 4 + 8 = 15$
• Enteros regulares reales: $\{0, 1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19\}$
• Verificación: $|\mathbb{Z}^{\text{reg}}_{20}| = 15$ ✓

Ejemplo de Aplicación

El artículo presenta en detalle todas las correspondencias de la aplicación $f_{20}$, verificando la corrección de la biyección.

Resultados Experimentales

Verificación Teórica

Las cuatro pruebas establecen exitosamente la corrección de la fórmula de Morgado, proporcionando cada método perspectivas combinatorias únicas.

Resultados de Aplicación Criptográfica

En la generalización de RSA con múltiples primos y potencias múltiples:

• Probabilidad de descifrado correcto: $\frac{\varrho(n)}{n} = \frac{1}{n}\sum_{d \parallel n} \varphi(d)$
• Estimación de cota inferior: Para $n = p_1^{e_1} \cdots p_r^{e_r}$ (donde $p_i$ son primos de $k$ bits), se tiene $\frac{\varrho(n)}{n} \geq 1 - \frac{r}{2^{k-1}}$
• Significancia Práctica: Cuando $k = 1024$, casi todos los mensajes se descifran correctamente.

Trabajos Relacionados

Desarrollo Histórico

1. Morgado (1972): Introduce por primera vez el concepto de enteros regulares y proporciona la fórmula de conteo.
2. Alkam & Osba (2008): Investigan más a fondo las propiedades de los enteros regulares.
3. Apostol & Petrescu (2013): Estudian propiedades extremales de funciones relacionadas.
4. Tóth (2008): Proporcionan resultados asintóticos y análisis de funciones relacionadas.

Contribución de Este Artículo

En comparación con trabajos existentes, este artículo proporciona por primera vez métodos de prueba puramente combinatorios y establece conexiones importantes con la criptografía.

Conclusiones y Discusión

Conclusiones Principales

1. La fórmula de Morgado tiene interpretaciones combinatorias ricas; cada prueba revela estructuras en diferentes niveles.
2. Los enteros regulares juegan un papel clave en la generalización del sistema criptográfico RSA.
3. Para parámetros prácticos, la probabilidad de descifrado correcto se aproxima a 1.

Limitaciones

1. Las aplicaciones criptográficas se limitan a la generalización específica de RSA propuesta.
2. El análisis asintótico requiere investigación adicional.
3. El análisis de complejidad computacional no es suficientemente profundo.

Direcciones Futuras

1. Desarrollar límites de probabilidad más precisos.
2. Investigar propiedades asintóticas de la secuencia A055653.
3. Explorar otras aplicaciones criptográficas.

Evaluación Profunda

Fortalezas

1. Innovación Teórica: Las cuatro pruebas combinatorias tienen características distintivas, enriqueciendo la comprensión de los enteros regulares.
2. Rigor Metodológico: El proceso de prueba es riguroso y la lógica es clara.
3. Valor Aplicado: La conexión con la criptografía aumenta la significancia práctica de la investigación teórica.
4. Claridad de Expresión: La estructura del artículo es razonable y los ejemplos son abundantes.

Deficiencias

1. Limitaciones de Aplicación: Las aplicaciones criptográficas se limitan a la generalización de RSA propuesta por los autores.
2. Análisis Computacional: Falta análisis profundo de la complejidad algorítmica.
3. Verificación Experimental: Solo hay verificación numérica a pequeña escala; faltan experimentos computacionales a gran escala.

Impacto

1. Valor Académico: Proporciona nuevas perspectivas de investigación para la matemática combinatoria de la teoría de números.
2. Potencial Práctico: Tiene valor de aplicación potencial en criptografía.
3. Reproducibilidad: Las pruebas teóricas son completas y los resultados son fáciles de verificar.

Escenarios Aplicables

1. Investigación teórica en teoría de números y matemática combinatoria.
2. Escenarios en criptografía que involucren operaciones modulares.
3. Aplicaciones que requieran calcular el tamaño de conjuntos especiales de enteros.

Referencias Bibliográficas

El artículo cita 8 referencias relacionadas, cubriendo el desarrollo principal de la teoría de enteros regulares y los fundamentos matemáticos relacionados, proporcionando a los lectores conocimientos de antecedentes completos.

Evaluación General: Este es un artículo matemático de alta calidad que profundiza la comprensión de un problema clásico de teoría de números mediante múltiples métodos combinatorios, estableciendo exitosamente conexiones con la criptografía moderna. Las contribuciones teóricas del artículo son sólidas y sus perspectivas de aplicación son amplias, constituyendo un trabajo valioso en el campo de la matemática combinatoria de la teoría de números.