ÁLGEBRA

ARITMÉTICA MODULAR

 logaritmo discreto de y en base g, donde g e y son elementos de un grupo cíclico finito G, a la solución x de la ecuación g^x = y. Esto, se puede denotar matemáticamente como:

${\displaystyle x=\log _{g}(y)\Longleftrightarrow g^{x}=y}$

Los logaritmos discretos son análogos en teoría de grupos a los logaritmos ordinarios en análisis. Mientras que el cálculo de su inversa — la exponenciación discreta — es una tarea muy sencilla en términos computacionales, el cálculo del logaritmo discreto no es sencillo en muchos grupos. El hecho de que el problema sea «irresoluble» en un tiempo razonable si se utiliza aritmética modular hace que esto se use en criptografía, en el método de intercambio de claves de Diffie-Hellman o en el sistema de ElGamal.

Ejemplo[editar]

Los Logaritmos discretos son quizás más sencillos de entender en el grupo (Z_p)^×, o sea el grupo multiplicativo módulo un primo p.

La k-ésima potencia de uno de los números en este grupo puede ser calculada encontrando la potencia k-ésima como un entero y luego obteniendo el resto después de su división por p. Este proceso es llamado Exponenciación modular. Por ejemplo, considerando (Z₁₇)^×, para considerar 3⁴ en este grupo, primero se calcula 3⁴ = 81 y después se divide 81 entre 17 obteniendo de resto 13. Esto es 3⁴ = 13 en el grupo (Z₁₇)^×. En la práctica se utiliza el método de la exponenciación binaria, reduciendo en cada paso.

El logaritmo discreto es la operación inversa. Por ejemplo, considerando la ecuación 3^k ≡ 13 (mod 17) para k. Del ejemplo de arriba, una solución es k = 4, pero esta no es la única solución. Puesto que 3¹⁶ ≡ 1 (mod 17) — como indica el Pequeño teorema de Fermat — , se deduce que, si n es un entero, entonces 3⁴⁺¹⁶ⁿ ≡ 3⁴ × (3¹⁶)ⁿ ≡ 13 × 1ⁿ ≡ 13 (mod 17). Por lo tanto la ecuación tiene infinitas soluciones de la forma 4 + 16n. Por otra parte, como 16 es el menor número entero positivo m que cumple 3^m ≡ 1 (mod 17) (en otras palabras, 16 es el orden de 3 en (Z₁₇)^×), estas son las únicas soluciones. Equivalentemente, el conjunto de todas las posibles soluciones puede ser expresado por la restricción k ≡ 4 (mod 16).

Definición[editar]

Sea (G,·) un grupo cíclico finito de orden n — con n elementos —, es decir, G={e,g,g²,...,g^n-1} para cierto elemento g de G. Dado h perteneciente a G existe un k perteneciente a Z tal que h = g^k. Este valor de k es el logaritmo discreto de a en base g.

Más formalmente, se define:

${\displaystyle \log _{g}:G\rightarrow \mathbb {Z} /n\mathbb {Z} }$

como la función que asigna valores de la siguiente manera:

${\displaystyle \log _{g}(x)=k}$ tal que ${\displaystyle x\equiv g^{k}}$.

Propiedades[editar]

Algunas de las propiedades de esta función son:

• ${\displaystyle \log _{g}(x\cdot y)=\log _{g}(x)+\log _{g}(y)}$

• ${\displaystyle \forall \ t\in \mathbb {N} ,\log _{g}(c^{t})=t\,\log _{g}(c)}$

• ${\displaystyle \log _{g}(1)=0}$

• ${\displaystyle \log _{g}(g)=1}$

Aquí sigue vigente la fórmula del cambio de base de los logaritmos continuos siempre que c sea otro generador:

• ${\displaystyle \log _{c}(x)=\log _{c}(g)\cdot \log _{g}(x)}$

Cálculo[editar]

No se conocen algoritmos clásicos para la computación de un logaritmo discreto log_b g. Un algoritmo es elevar ba sucesivas potencias k hasta encontrar la deseada g. Este algoritmo requiere una complejidad temporal lineal respecto del tamaño del grupo G y, por lo tanto, exponencial respecto del número de dígitos en el tamaño del grupo. Existe un algoritmo cuántico eficiente debido a Peter Shor.¹​

Existen algoritmos más sofisticados, normalmente inspirados por algoritmos similares para la factorización de enteros. Estos algoritmos funcionan más rápido que el algoritmo anterior. Algunos de ellos en un tiempo lineal respecto de la raíz cuadrada del tamaño del grupo y, por lo tanto, exponencial respecto de la mitad del número de dígitos del tamaño del grupo. Sin embargo, ninguno corre en un Tiempo polinómico (en el número de dígitos del tamaño del grupo). Algunos de los algoritmos funcionan para cualquier grupo, mientras otros sólo pueden ser utilizados para ciertos grupos concretos.²​

• Baby-step giant-step (también conocido como algoritmo de Shanks)
• Algoritmo rho de Pollard para logaritmo discreto
• Algoritmo del canguro de Pollard (también conocido como algoritmo lambda)
• Algoritmo Pohlig–Hellman
• Algoritmo de cálculo de índices

Comparación con la factorización de enteros[editar]

Si bien los problema del cálculo de logaritmos discretos y el de factorización de enteros son distintos, comparten algunas propiedades:

• ambos problemas son difíciles
• para ambos se conocen algoritmos eficientes en ordenadores cuánticos,
• algoritmos para un problema a menudo se adaptan al otro, y
• la dificultad de ambos problemas se ha utilizado para construir varios sistemas criptográficos.

Criptografía[editar]

Existen grupos para los que calcular logaritmos discretos es aparentemente difícil. En algunos casos no hay ningún algoritmo eficaz conocido para resolver el problema en general y la complejidad en el caso promedio resulta tan difícil como en el peor de los casos.

Al mismo tiempo, el problema inverso, la exponenciación discreta, no es difícil (puede ser computada eficientemente usando Exponenciación binaria). Esta asimetría es análoga a la que ocurre entre la factorización de enteros y la multiplicación de enteros. Ambas asimetrías han sido explotadas en la construcción de sistemas criptográficos.

Opciones populares para el grupo G en la criptografía usando logaritmos discretos son aquellos para los que no existen buenos algoritmos, entre los que se encuentran los grupos cíclicos (Z_p)^× (e.g. Cifrado ElGamal, Diffie-Hellman y el algoritmo de firma digital) y subgrupos cíclicos de curvas elípticas sobre cuerpos finitos (verCriptografía de curva elíptica).

módulo es una de las estructuras algebraicas fundamentales usadas en álgebra abstracta. Un módulo sobre un anillo es una generalización de la noción de espacio vectorial sobre un cuerpo, donde los correspondientes escalares son los elementos un anillo (con identidad) arbitrario y donde está definida una multiplicación (a la izquierda y/o a la derecha) entre elementos del anillo y elementos del módulo.

Los módulos están estrechamente relacionados con la teoría de representación de grupos. Son una de las nociones centrales del álgebra conmutativa y del álgebra homológica y se usan en la geometría algebraica y la topología algebraica.

Definición[editar]

Sea ${\displaystyle R}$ un anillo con identidad y sea ${\displaystyle 1_{R}}$ su identidad multiplicativa. Un ${\displaystyle R}$-módulo izquierdo de ${\displaystyle M}$ es un grupo abeliano ${\displaystyle (M,+)}$ y una operación ${\displaystyle \cdot :R\times M\to M}$ tal que para cualesquiera ${\displaystyle r,s\in R}$, ${\displaystyle x,y\in M}$, se tiene

1. ${\displaystyle (rs)x=r(sx)}$
2. ${\displaystyle (r+s)x=rx+sx}$
3. ${\displaystyle r(x+y)=rx+ry}$
4. ${\displaystyle 1x=x}$

Generalmente, se escribe simplemente "un ${\displaystyle R}$-módulo izquierdo ${\displaystyle M}$" o ${\displaystyle R_{M}}$.

Algunos autores^{[cita requerida]} omiten la condición 4 en la definición general de módulos izquierdos, y llaman a las estructuras definidas antes "módulos izquierdos unitales". En este artículo sin embargo, todos los módulos (y todos los anillos) se presuponen unitales. Por lo general, para módulos, en la mayoría de los textos se considera la condición 4, mientras que para anillos no se supone que exista elemento unidad, excepto que se diga lo contrario.

Un ${\displaystyle R}$-módulo derecho de ${\displaystyle M}$ o ${\displaystyle M_{R}}$ se define de forma semejante, sólo que el anillo actúa por la derecha, es decir se tiene una multiplicación escalar de la forma ${\displaystyle M\times R\to M}$, y los tres axiomas antedichos se escriben con los escalares ${\displaystyle r}$ y ${\displaystyle s}$ a la derecha de ${\displaystyle x}$ e ${\displaystyle y}$.

Si R es conmutativo, entonces los R-módulos a la izquierda son lo mismo que R-módulos a la derecha y se llaman simplemente R-módulos.

Ejemplos[editar]

• Si K es un cuerpo, entonces los conceptos "K-espacio vectorial" y K-módulo son idénticos.

• Cada grupo abeliano M es un módulo sobre el anillo de los números enteros Z si se define nx = x + x +... + x(n sumandos) para n > 0, 0 x = 0, y (- n) x = - (nx) para n < 0.

• Si R es cualquier anillo y n un número natural, entonces el producto cartesiano Rⁿ es un módulo izquierdo y derecho sobre R si se utilizan las operaciones componente a componente. El caso n = 0 da el trivial R-módulo {0} que consiste solamente en el elemento identidad (aditiva).

• Si X es una variedad diferenciable, entonces las funciones diferenciables de X a los números reales forman un anillo R. El conjunto de todos los campos vectoriales diferenciables definidos en X forman un módulo sobre R, y lo mismo con los campos tensoriales y las formas diferenciales en X.

• Las matrices cuadradas n-por-n con entradas reales forman un anillo R, y el espacio euclidiano R ⁿ es un módulo izquierdo sobre este anillo si se define la operación de módulo vía la multiplicación de matrices.

• Si R es cualquier anillo e I es cualquier ideal izquierdo en R, entonces I es un módulo izquierdo sobre R. Análogamente, por supuesto, los ideales derechos son módulos derechos.

Submódulos y homomorfismos[editar]

Suponga que M es un R-módulo izquierdo y N es un subgrupo de M. Entonces N es un submódulo (o R-submódulo, para ser más explícito) si, para cualquier n en N y cualquier r en R, el producto rn está en N (o el nrpara un módulo derecho). Si M y N son R - módulos, entonces una función f: M → N es un homomorfismo de R- módulos si, para cualquier m, n en M y r, s en R,

f (rm + sn) = rf(m) + sf(n).

Esto, como cualquier homomorfismo de objetos matemáticos, es precisamente una función que preserva la estructura de los objetos. Un homomorfismo biyectivo de módulos es un isomorfismo de módulos, y los dos módulos se llaman isomorfos. Dos módulos isomorfos son idénticos para todos los propósitos prácticos, diferenciándose solamente en la notación para sus elementos.

El núcleo de un homomorfismo de módulos f: M → N es el submódulo de M que consiste en todos los elementos que son enviados a cero por f. Los teoremas de isomorfía familiares de grupos abelianos y de espacios vectoriales son también válidos para R-módulos.

Los R-módulos izquierdos, junto con sus homomorfismos de módulo, forman una categoría, escrita como _RMod. Esta es una categoría abeliana.

Tipos de módulos[editar]

Finitamente generado. Un módulo M es finitamente generado si existe un número finito de elementos x₁..., x_nen M tales que cada elemento de M es una combinación lineal de esos elementos con coeficientes del anillo escalar R.

Libre. Un módulo libre es un módulo que tiene una base libre, o equivalentemente, uno que es isomorfo a una suma directa de copias del anillo escalar R. Estos son los módulos que se comportan parecido a los espacios vectoriales.

Proyectivo. Los módulos proyectivos son sumandos directos de módulos libres y comparten muchas de sus propiedades deseables.

Inyectivo. Los módulos inyectivos se definen dualmente a los módulos proyectivos.

Simple. Un módulo simple S es un módulo que no es {0} cuyos únicos submódulos son {0} y S. Los módulos simples a veces se llaman irreducibles.

Indescomponible. Un módulo indescomponible es un módulo diferente a cero que no se puede escribir como una suma directa de dos submódulos diferentes a cero. Cada módulo simple es indescomponible.

Fiel. Un módulo fiel M es uno donde la acción de cada r (distinto de cero) en R es no trivial (es decir, existe algún m en M tal que rm ≠ 0). Equivalente, el anulador de M es el ideal cero.

Noetheriano. Un módulo noetheriano es un módulo tal que cada submódulo es finitamente generado. Equivalente, cada cadena creciente de submódulos llega a ser estacionaria en finitos pasos.

Artiniano. Un módulo artiniano es un módulo en el cual cada cadena decreciente de submódulos llega a ser estacionaria en finitos pasos.

Definición alternativa como representaciones[editar]

Si M es un R-módulo izquierdo, entonces la acción de un elemento r en R se define como la función M → M que envía cada x al rx (o al xr en el caso de un módulo derecho), y es necesariamente un endomorfismo de grupo del grupo abeliano (M, +). El conjunto de todos los endomorfismos de grupo de M es denotado End_Z(M) y forma un anillo bajo la adición y composición, y enviando un elemento r del anillo R a su acción define realmente un homomorfismo de anillo de R a End_Z(M).

Tal del homorfismo R del anillo → End_Z(M) se llama una representación de R en el grupo abeliano M; una manera alternativa y equivalente de definir R-módulos izquierdos es decir que un R-módulo izquierdo es un grupo abeliano M junto con una representación de R en él.

Una representación se llama fiel si y solamente si la función R → End_Z(M) es inyectiva. En términos de módulos, esto significa que si r es un elemento de R tal que rx = 0 para todo x en M, entonces r = 0. Cada grupo abeliano es un módulo fiel sobre los números enteros o sobre una cierta aritmética modular Z/n Z.

Generalizaciones[editar]

Cualquier anillo R se puede ver como categoría preaditiva con un solo objeto. Con esta comprensión, un R-módulo izquierdo es un funtor aditivo (covariante) de R a la categoría Ab grupos abelianos. Los R-módulosderechos son funtores aditivos contravariantes. Esto sugiere que, si C es cualquier categoría preaditiva, un funtor aditivo covariante de C a Ab sea considerado un módulo izquierdo generalizado sobre C; estos funtores forman una categoría de funtores C-Mod que es la generalización natural de la categoría de módulos R-Mod.

Los módulos sobre anillos conmutativos se pueden generalizar en una dirección distinta: tome un espacio anillado (X, O_X) y considere los haces de O_X-módulos. Estos forman una categoría O_X-Mod. Si X tiene solamente un punto, entonces esto es una categoría de módulo en el viejo sentido sobre el anillo conmutativo O_X(X).