1. Ecuación Lineal de Congruencia ax ≡ b (mod m):
- Existencia de Soluciones:La ecuación tiene solución si y solo si mcd(a, m) divide a b
- Número de Soluciones:Si existen soluciones, hay d = mcd(a, m) soluciones distintas módulo m
- Método de Solución:
- Calcula d = mcd(a, m)
- Verifica si d divide a b; si no, no hay solución
- Divide ambos lados por d: (a/d)x ≡ (b/d) (mod m/d)
- Usa el Algoritmo Extendido de Euclides para encontrar el inverso de a/d módulo m/d
- Calcula x₀ = a' × (b/d) mod (m/d)
- Solución general: x = x₀ + k(m/d), donde k = 0, 1, ..., d-1
2. Ecuación exponencial de congruencia a^x ≡ b (mod m) (Problema del Logaritmo Discreto):
- Descripción del problema:Dados a, b, m, encuentra el menor entero no negativo x tal que a^x ≡ b (mod m)
- Existencia de Soluciones:
- Si mcd(a, m) = 1 y b es un elemento del grupo cíclico generado por a módulo m, entonces existe solución
- Método de verificación: enumerar potencias de a hasta encontrar b o completar un ciclo
- Método de Solución:
- Búsqueda por fuerza bruta en un rango pequeño:Enumera x = 0, 1, 2, ... hasta encontrar una solución o alcanzar el límite
- Algoritmo Baby-step Giant-step:Complejidad O(√m), adecuado para problemas medianos
- Algoritmo rho de Pollard:Aplicable para módulos primos grandes
- Periodicidad:Si x₀ es una solución, entonces x = x₀ + kφ(m) también es solución
3. Escenarios de aplicación:
- Criptografía:RSA, intercambio de claves Diffie-Hellman, cifrado ElGamal
- Investigación en teoría de números:Raíces Primitivas, Residuos Cuadráticos, Teorema Chino del Resto
- Generación de Números Aleatorios:Generador Congruencial Lineal (LCG)
- Funciones Hash:Aplicación de la Aritmética Modular en Tablas Hash
- Programación Competitiva:Exponenciación Rápida, Inverso Modular, Problemas de Teoría de Números
Complejidad del Algoritmo:
- Ecuaciones Lineales de Congruencia:O(log m) (Complejidad del Algoritmo Extendido de Euclides)
- Ecuaciones Exponenciales (Fuerza Bruta):O(n), donde n es el límite de búsqueda
- Ecuaciones Exponenciales (BSGS):O(√m), requiere espacio adicional
Teoremas Importantes:
- Teorema de Bézout:La ecuación ax + my = mcd(a, m) siempre tiene soluciones enteras
- Pequeño Teorema de Fermat:Si p es primo y mcd(a, p) = 1, entonces a^(p-1) ≡ 1 (mod p)
- Teorema de Euler:Si mcd(a, m) = 1, entonces a^φ(m) ≡ 1 (mod m)
- Teorema Chino del Resto:Puede resolver sistemas de congruencias