Aritmética modular

Tiempo de mantenimiento en este reloj utiliza modulo aritmético 12. Añadiendo 4 horas a 9 en punto da 1 en punto, ya que 13 es congruente con 1 modulo 12.

En matemáticas, la aritmética modular es un sistema de aritmética para números enteros, donde los números "envuelven" al alcanzar un determinado valor, llamado módulo. El enfoque moderno de la aritmética modular fue desarrollado por Carl Friedrich Gauss en su libro Disquisitiones Arithmeticae, publicado en 1801.

Un uso familiar de la aritmética modular es el reloj de 12 horas, en el que el día se divide en dos períodos de 12 horas. Si ahora son las 7:00, 8 horas después serán las 3:00. La suma simple daría como resultado 7 + 8 = 15, pero los relojes "envuelven" cada 12 horas. Debido a que el número de hora comienza de nuevo en cero cuando llega a 12, esto es aritmética módulo 12. En términos de la definición siguiente, 15 es congruente con 3 módulo 12, entonces & #34;15:00" en un reloj de 24 horas se muestra "3:00" en un reloj de 12 horas.

Congruencia

Dado un número entero n > 1, llamado módulo, dos números enteros a y b se dice que son congruentes módulo n, si n es un divisor de su diferencia (es decir, si hay un número entero k tal que a − b = kn).

Congruence modulo n es una relación de congruencia, lo que significa que es una relación de equivalencia que es compatible con las operaciones de suma, resta y multiplicación. El módulo de congruencia n se denota:

a↑ ↑ b()modn).{displaystyle aequiv b{pmod {n}}

Los paréntesis significan que (modelo) n) se aplica a toda la ecuación, no sólo al lado derecho (aquí, b). Esta notación no debe confundirse con la notación b mod n (sin paréntesis), que se refiere a la operación modulo. De hecho, b mod n denota el entero único a tales que 0 ≤ a. n y a↑ ↑ b()modn){displaystyle aequiv b;({text{mod};n) } (es decir, el resto de b{displaystyle b} cuando se divide n{displaystyle n}).

La relación de congruencia se puede reescribir como

a=kn+b,{displaystyle a=kn+b,}

mostrando explícitamente su relación con la división euclidiana. Sin embargo, el b aquí no necesita ser el resto de la división de a por n. En cambio, lo que la declaración a ≡ b (mod n) afirma que a y b tiene el mismo resto cuando se divide por n. Es decir,

a=pn+r,{displaystyle a=pn+r,}

b=qn+r,{displaystyle b=qn+r,}

donde 0 ≤ r < n es el resto común. Restando estas dos expresiones, recuperamos la relación anterior:

a− − b=kn,{displaystyle a-b=kn,}

estableciendo k = p − q.

Ejemplos

En el módulo 12, se puede afirmar que:

38↑ ↑ 14()mod12){displaystyle 38equiv 14{pmod {12}}

porque 38 − 14 = 24, que es un múltiplo de 12. Otra forma de expresar esto es decir que tanto 38 como 14 tienen el mismo resto 2, cuando se dividen por 12

La definición de congruencia también se aplica a valores negativos. Por ejemplo:

2↑ ↑ − − 3()mod5)− − 8↑ ↑ 7()mod5)− − 3↑ ↑ − − 8()mod5).{fnMicrosoft -3{pmod {5}\\fnMicrosoft Sans Serif}\cH3}\pmod {5}}\\cH0}}\cH2} {pmod {pmod {5}}}}}}}}}}}}}}}}}

Propiedades

La relación de congruencia satisface todas las condiciones de una relación de equivalencia:

• Reflexividad: a ↑ a (modelo) n)
• Simetría: a ↑ b (modelo) n) si b ↑ a (modelo) n) para todos a, b, y n.
• Transitividad: Si a ↑ b (modelo) n) y b ↑ c (modelo) n), entonces a ↑ c (modelo) n)

Si a₁ ≡ b₁ (modificación n) y a₂ ≡ b₂ (mod n), o si a ≡ b (mod n), luego:

• a + k ↑ b + k (modelo) n) para cualquier entero k (compatibilidad con traducción)
• k a ↑ kb (modelo) n) para cualquier entero k (compatibilidad con escalado)
• k a ↑ kb (modelo) kn) para cualquier entero k
• a₁ + a₂ ↑ b₁ + b₂ (modelo) n) (compatibilidad con adición)
• a₁ – a₂ ↑ b₁ – b₂ (modelo) n) (compatibilidad con resta)
• a₁ a₂ ↑ b₁ b₂ (modelo) n) (compatibilidad con multiplicación)
• a^k ↑ b^k (modelo) n) para cualquier entero no negativo k (compatibilidad con exponentiación)
• p()a) p()b(modelo) n), para cualquier polinomio p()x) con coeficientes enteros (compatibilidad con evaluación polinómica)

Si a ≡ b (mod n), generalmente es falso que k^a ≡ k^b (mod n). Sin embargo, lo siguiente es cierto:

• Si c ↑ d (modelo) φ()n)), Donde φ es la función totiente de Euler, entonces a^c ↑ a^d (modelo) n)—siempre que a es coprime con n.

Para la cancelación de términos comunes, tenemos las siguientes reglas:

• Si a + k ↑ b + k (modelo) n), donde k es cualquier entero, entonces a ↑ b (modelo) n)
• Si k a ↑ kb (modelo) n) y k es coprime con n, entonces a ↑ b (modelo) n)
• Si k a ↑ kb (modelo) kn) y k ه 0, entonces a ↑ b (modelo) n)

El inverso multiplicativo modular se define mediante las siguientes reglas:

• Existencia: existe un entero denotado a^–1 tales que aa^–1 (modelo) n) si a es coprime con n. Este entero a^–1 se llama multiplicador modular inverso de a modulo n.
• Si a ↑ b (modelo) n) y a^–1 existe, entonces a^–1 ↑ b^–1 (modelo) n) (compatibilidad con inverso multiplicador, y, si a = b, modulo de singularidad n)
• Si a x ↑ b (modelo) n) y a es coprime n, entonces la solución a esta congruencia lineal es dada por x ↑ a^–1b (modelo) n)

El inverso multiplicador x ↑ a^–1 (modelo) n) puede ser computado eficientemente por resolver la ecuación de Bézout ax+nSí.=1{displaystyle ax+ny=1} para x,Sí.{displaystyle x,y}—usando el algoritmo de Euclidean extendido.

En particular, si p es un número primo, entonces a es coprimo con p para cada a tal que 0 < a < p; por lo tanto, existe un inverso multiplicativo para todo a que no es congruente con módulo cero p .

Algunas de las propiedades más avanzadas de las relaciones de congruencia son las siguientes:

• El pequeño teorema de Fermat: Si p es primo y no divide a, entonces a ^{p – 1} (modelo) p).
• El teorema de Euler: Si a y n son coprime, entonces a ^φ()n) (modelo) n), donde φ es la función totiente de Euler
• Una simple consecuencia del pequeño teorema de Fermat es que si p es primo, entonces a⁻¹ ↑ a ^{p − 2} (modelo) p) es el inverso multiplicativo de 0 a. p. Más generalmente, del teorema de Euler, si a y n son coprime, entonces a⁻¹ ↑ a ^{φ()n− 1} (modelo) n).
• Otra consecuencia simple es que si a ↑ b (modelo) φ()n)), Donde φ es la función totiente de Euler, entonces k^a ↑ k^b (modelo) n) proporcionadas k es coprime con n.
• El teorema de Wilson: p es primo si y sólo si ()p - 1). (modelo) p).
• Teorema de restos chinos: Para cualquier a, b y coprime m, n, existe un único x (modelo) mn) tales que x ↑ a (modelo) m) y x ↑ b (modelo) n). De hecho, x ↑ b_n^–1 m + a n_m^–1 n (modelo) mn) Donde m_n⁻¹ es el inverso de m modulo n y n_m⁻¹ es el inverso de n modulo m.
• Teorema de Lagrange: La congruencia f ()x) ↑ 0 (modelo) p), donde p es primo, y f ()x) a₀ xⁿ +... + a_n es un polinomio con coeficientes enteros tales que a₀ ل 0 (mod p), tiene al máximo n raíces.
• Primitive root modulo n: Número g es un modulo de raíz primitivo n si, por cada entero a coprime n, hay un entero k tales que g^k ↑ a (modelo) n). Un modulo de raíz primitivo n existe si n es igual a 2, 4, p^k o 2p^k, donde p es un número primo extraño y k es un entero positivo. Si un modulo de raíz primitivo n existe, entonces hay exactamente φ()φ()n) tales raíces primitivas, donde φ es la función totiente de Euler.
• Residuo cuadrático: Un entero a es un modulo de residuos cuadráticos n, si existe un entero x tales que x² ↑ a (modelo) n). El criterio de Euler afirma que, si p es una prima extraña, y a no es un múltiple p, entonces a es un modulo de residuos cuadráticos p si

a()p− − 1)/2↑ ↑ 1()modp).{displaystyle a^{(p-1)/2}equiv 1{pmod {p}}

Clases de congruencia

Como cualquier relación de congruencia, módulo de congruencia n es una relación de equivalencia, y la clase de equivalencia del entero a, indicado por a_n, es el conjunto {... a − 2n, a − n, a, a + n, un + 2n,...}. Este conjunto, que consta de todos los números enteros congruentes con a módulo n, se denomina clase de congruencia, clase de residuo, o simplemente residuo del entero a módulo n. Cuando el módulo n se conoce por el contexto, ese residuo también se puede denotar [a].

Sistemas de residuos

Cada clase de residuo módulo n puede representarse por cualquiera de sus miembros, aunque generalmente representamos cada clase de residuo por el entero no negativo más pequeño que pertenece a esa clase (ya que este es el resto propio que resulta de la división). Dos miembros cualesquiera de diferentes clases de residuos módulo n son incongruentes módulo n. Además, todo número entero pertenece a una y sólo una clase de residuo módulo n.

El conjunto de números enteros {0, 1, 2,..., n − 1} se llama el sistema de residuos mínimos módulo n. Cualquier conjunto de n enteros, de los cuales dos no son congruentes módulo n, se llama un sistema completo de residuos módulo n.

El sistema de residuos mínimos es un sistema de residuos completo, y un sistema de residuos completo es simplemente un conjunto que contiene exactamente un representante de cada clase de residuo módulo n. Por ejemplo. el sistema de mínimo residuo módulo 4 es {0, 1, 2, 3}. Algunos otros sistemas completos de residuos módulo 4 incluyen:

• {1, 2, 3, 4}
• {13, 14, 15, 16}
• {2, −1, 0, 1}
• {13, 4, 17, 18}
• {5,} 0, 6, 21}
• {27, 32, 37, 42}

Algunos conjuntos que no son sistemas de residuos completos módulo 4 son:

• {5, - 0, 6, 22}, ya que 6 es congruente con 22 modulos 4.
• {5, 15}, ya que un sistema de residuos completo modulo 4 debe tener exactamente 4 clases de residuos incongruentes.

Sistemas de residuos reducidos

Dada la función totient de Euler φ(n), cualquier conjunto de φ(n) enteros que son primos relativos a n y mutuamente incongruentes bajo el módulo <span class="texhtml" n se denomina sistema de residuos reducidos módulo n. El conjunto {5,15} de arriba, por ejemplo, es una instancia de un módulo de sistema de residuos reducido 4.

Enteros módulo n

El conjunto de todas las clases de congruencia de los enteros para un módulo n se llama anillo de enteros modulo n, y es denotado Z/nZ{textstyle mathbb {Z} /nmathbb {Z}, Z/n{displaystyle mathbb {Z} /n}, o Zn{displaystyle mathbb {Z} _{n}. La notación Zn{displaystyle mathbb {Z} _{n} es, sin embargo, no recomendado porque puede confundirse con el conjunto de enteros n-adic. El anillo Z/nZ{displaystyle mathbb {Z} /nmathbb {Z} es fundamental para varias ramas de las matemáticas (ver § Aplicaciones a continuación).

El conjunto se define para n > 0 como:

Z/nZ={}ā ̄ n▪ ▪ a▪ ▪ Z}={}0̄ ̄ n,1̄ ̄ n,2̄ ̄ n,...... ,n− − 1̄ ̄ n}.{displaystyle mathbb {Z} /nmathbb {Z} =left{overline {a}_{n}mid ain mathbb {Z} right=left{overline {0}_{n},{overline {1}_{n},{overline {2}_{n},ldots{overline {n{-}_ {n}} {n{n}}} {n{n}}}} {n{n}}}} {n{n}}}} {n{n}}}}}}} {n{n}}}}}}}}}}} {n {n{n}}}}}}}}}}} {n}}}}}}}}}}}}}}} {n}}} {n}}}}} {n}}}}}} {n}}}}}}}}}}}}}}}}}}} {n}} {n}}} {n}}}}}}}}}}}}}}}}} {n}}}}}}}}}}} {n}}}}}}}}}} {n}}}}}}}}}}}} {n}}}}}}}}}}}}}}} {n}}}}}}}}}}}}}}}}}}}}}}}}}}}}

(Cuando n = 0, Z/nZ{displaystyle mathbb {Z} /nmathbb {Z} no es un conjunto vacío; más bien, es isomorfo Z{displaystyle mathbb {Z}, desde a₀ =a}.)

Definimos adición, resta y multiplicación en Z/nZ{displaystyle mathbb {Z} /nmathbb {Z} por las reglas siguientes:

• ā ̄ n+b̄ ̄ n=()a+b)̄ ̄ n{displaystyle {fnline {a}_{n}+{overline {b}_{n}={overline {(a+b)}_{n}} {cH00} {cH00}
• ā ̄ n− − b̄ ̄ n=()a− − b)̄ ̄ n{displaystyle {fnline {a}_{n}-{overline {b}_{n}={overline {(a-b)}_{n}} {cH00} {cH00}
• ā ̄ nb̄ ̄ n=()ab)̄ ̄ n.{displaystyle {fnline {fn} {fn} {fn} {fn} {fn}} {fn}} {fn}} {fn}}} {fn}} {fn}} {fn}} {fn}}}} {fn}}} {\fn}}}}}} {n}}}}}}}} {\\n}}}}}}}}}}\\\\n}}}}}}}}}\\\\\\\n}}}}}}}}}}}}}}}}}\\\\\\\\\\\\\\\\\\\\\\n}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {b}_{n}={overline {(ab)}_{n}

La verificación de que esta es una definición adecuada utiliza las propiedades dadas anteriormente.

De esta manera, Z/nZ{displaystyle mathbb {Z} /nmathbb {Z} se convierte en un anillo comunicativo. Por ejemplo, en el anillo Z/24Z{displaystyle mathbb {Z} /24mathbb {Z}, tenemos

12̄ ̄ 24+21̄ ̄ 24=33̄ ̄ 24=9̄ ̄ 24{displaystyle {fnline {12}_{24}+{overline {21}_{24}={overline {33}_{24}={overline {9}_{24}

como en la aritmética del reloj de 24 horas.

Usamos la notación Z/nZ{displaystyle mathbb {Z} /nmathbb {Z} porque este es el anillo cociente Z{displaystyle mathbb {Z} por el ideal nZ{displaystyle nmathbb {Z}, un conjunto que contiene todos los enteros divisibles por n, donde 0Z{displaystyle 0mathbb {Z} es el conjunto de singleton {0}}. Así Z/nZ{displaystyle mathbb {Z} /nmathbb {Z} es un campo cuando nZ{displaystyle nmathbb {Z} es un ideal máximo (es decir, cuando n es primo).

Esto también se puede construir desde el grupo Z{displaystyle mathbb {Z} solo bajo la operación adicional. La clase de residuos a_n es el conjunto del grupo a en el grupo de referencia Z/nZ{displaystyle mathbb {Z} /nmathbb {Z}, un grupo cíclico.

En lugar de excluir el caso especial n = 0, es más útil incluir Z/0Z{displaystyle mathbb {Z} /0mathbb {Z} (que, como se mencionó anteriormente, es isomorfa al anillo Z{displaystyle mathbb {Z} de enteros). De hecho, esta inclusión es útil cuando se discute la característica de un anillo.

El anillo de los enteros modulo n es un campo finito si y sólo si n es primo (esto asegura que cada elemento no cero tiene un inverso multiplicativo). Si n=pk{displaystyle n=p^{k} es un poder primario con k Ø 1, existe un campo finito único (hasta el isomorfismo) GF()n)=Fn{displaystyle mathrm {GF} (n)=mathbb {fn} con n elementos, pero esto es no Z/nZ{displaystyle mathbb {Z} /nmathbb {Z}, que no es un campo porque tiene cero visores.

El subgrupo multiplicativo de enteros modulo n es denotado por ()Z/nZ)× × {fnMicrosoft Sans Serif}. Esto consiste en ā ̄ n{displaystyle {fnMicrosoft Sans Serif} {fn} (donde) a es coprime n), que son precisamente las clases que poseen un inverso multiplicativo. Esto forma un grupo conmutativo bajo multiplicación, con orden φ φ ()n){displaystyle varphi (n)}.

Extensión a números reales

Aplicaciones

En las matemáticas teóricas, la aritmética modular es uno de los fundamentos de la teoría de números y toca casi todos los aspectos de su estudio, y también se usa ampliamente en la teoría de grupos, la teoría de anillos, la teoría de nudos y el álgebra abstracta. En matemáticas aplicadas, se utiliza en álgebra informática, criptografía, informática, química y artes visuales y musicales.

Una aplicación muy práctica es calcular sumas de verificación dentro de identificadores de números de serie. Por ejemplo, el número internacional normalizado de libros (ISBN) utiliza aritmética de módulo 11 (para ISBN de 10 dígitos) o módulo 10 (para ISBN de 13 dígitos) para la detección de errores. Del mismo modo, los números de cuenta bancaria internacional (IBAN), por ejemplo, utilizan la aritmética del módulo 97 para detectar errores de entrada del usuario en los números de cuenta bancaria. En química, el último dígito del número de registro CAS (un número de identificación único para cada compuesto químico) es un dígito de control, que se calcula multiplicando el último dígito de las dos primeras partes del número de registro CAS por 1, el dígito anterior multiplicado por 2, el dígito anterior multiplicado por 3, etc., sumándolos todos y calculando la suma módulo 10.

En criptografía, la aritmética modular respalda directamente los sistemas de clave pública como RSA y Diffie-Hellman, y proporciona campos finitos que subyacen a las curvas elípticas, y se utiliza en una variedad de algoritmos de clave simétrica, incluido el Estándar de cifrado avanzado (AES), International Data Algoritmo de cifrado (IDEA) y RC4. RSA y Diffie-Hellman usan exponenciación modular.

En álgebra informática, la aritmética modular se usa comúnmente para limitar el tamaño de los coeficientes enteros en cálculos y datos intermedios. Se usa en la factorización de polinomios, un problema para el cual todos los algoritmos eficientes conocidos usan aritmética modular. Lo utilizan las implementaciones más eficientes del máximo común divisor polinomial, el álgebra lineal exacta y los algoritmos de base de Gröbner sobre los números enteros y los números racionales. Tal como se publicó en Fidonet en la década de 1980 y se archivó en Rosetta Code, la aritmética modular se usó para refutar la conjetura de la suma de potencias de Euler en una microcomputadora Sinclair QL utilizando solo una cuarta parte de la precisión de enteros utilizada por una supercomputadora CDC 6600 para refutar dos décadas antes a través de una búsqueda de fuerza bruta.

En informática, la aritmética modular se aplica a menudo en operaciones bit a bit y otras operaciones que involucran estructuras de datos cíclicas de ancho fijo. La operación módulo, implementada en muchos lenguajes de programación y calculadoras, es una aplicación de la aritmética modular que se usa a menudo en este contexto. El operador lógico XOR suma 2 bits, módulo 2.

En música, la aritmética módulo 12 se usa en la consideración del sistema de temperamento igual de doce tonos, donde ocurre la equivalencia de octava y enarmónico (es decir, los tonos en una proporción de 1:2 o 2:1 son equivalentes, y C -sostenido se considera lo mismo que re bemol).

El método de expulsar nueves ofrece una comprobación rápida de los cálculos aritméticos decimales realizados a mano. Se basa en la aritmética modular módulo 9, y específicamente en la propiedad crucial de que 10 ≡ 1 (módulo 9).

El módulo aritmético 7 se utiliza en algoritmos que determinan el día de la semana para una fecha determinada. En particular, la congruencia de Zeller y el algoritmo Doomsday hacen un uso intensivo de la aritmética de módulo 7.

En términos más generales, la aritmética modular también tiene aplicación en disciplinas como el derecho (p. ej., prorrateo), la economía (p. ej., teoría de juegos) y otras áreas de las ciencias sociales, donde la división proporcional y la asignación de recursos juegan un papel central en la análisis.

Complejidad computacional

Dado que la aritmética modular tiene una gama tan amplia de aplicaciones, es importante saber lo difícil que es resolver un sistema de congruencias. Un sistema lineal de congruencias se puede resolver en tiempo polinomial con una forma de eliminación gaussiana; para obtener detalles, consulte el teorema de congruencia lineal. Los algoritmos, como la reducción de Montgomery, también existen para permitir que operaciones aritméticas simples, como la multiplicación y el módulo n de exponenciación, se realicen de manera eficiente en números grandes.

Algunas operaciones, como encontrar un logaritmo discreto o una congruencia cuadrática, parecen ser tan difíciles como la factorización de números enteros y, por lo tanto, son un punto de partida para los algoritmos criptográficos y el cifrado. Estos problemas pueden ser NP-intermedios.

Resolver un sistema de ecuaciones aritméticas modulares no lineales es NP-completo.

Implementaciones de ejemplo

A continuación se muestran tres funciones de C razonablemente rápidas, dos para realizar multiplicaciones modulares y una para exponenciación modular en enteros sin signo de no más de 63 bits, sin desbordamiento de las operaciones transitorias.

Una forma algorítmica de calcular a⋅ ⋅ b()modm){displaystyle acdot b{pmod {m}:

uint64_t mul_mod()uint64_t a, uint64_t b, uint64_t m) {} si ()!()a Silencio b) " ()0xFFFFFFULL .. 32)) retorno a * b % m; uint64_t d = 0, mp2 = m > 1; int i; si ()a >= m) a %= m; si ()b >= m) b %= m; para ()i = 0; i . 64; ++i) {} d = ()d ■ mp2) ? ()d .. 1) - m : d .. 1; si ()a " 0x8000000000000000ULL) d += b; si ()d >= m) d -= m; a " 1; } retorno d;}

En arquitecturas informáticas donde está disponible un formato de precisión extendida con al menos 64 bits de mantisa (como el tipo doble largo de la mayoría de los compiladores x86 C), la siguiente rutina es más rápida que una solución que usa un bucle, empleando el truco que, por hardware, la multiplicación de punto flotante da como resultado que se mantengan los bits más significativos del producto, mientras que la multiplicación de enteros da como resultado que se mantengan los bits menos significativos:

uint64_t mul_mod()uint64_t a, uint64_t b, uint64_t m) {} largo doble x; uint64_t c; int64_t r; si ()a >= m) a %= m; si ()b >= m) b %= m; x = a; c = x * b / m; r = ()int64_t)a * b - c * m) % ()int64_t)m; retorno r . 0 ? r + m : r;}

A continuación se muestra una función de C para realizar la exponenciación modular, que utiliza la función mul_mod implementada anteriormente.

Una forma algorítmica de calcular ab()modm){displaystyle a^{b}{pmod {m}}:

uint64_t pow_mod()uint64_t a, uint64_t b, uint64_t m) {} uint64_t r = m == 1 ? 0 : 1; mientras ()b ■ 0) {} si ()b " 1) r = mul_mod()r, a, m); b = b > 1; a = mul_mod()a, a, m); } retorno r;}

Sin embargo, para que todas las rutinas anteriores funcionen, m no debe exceder los 63 bits.