En matemáticas, la aritmética modular es un sistema de cálculo para números enteros, con la ayuda de los cuales "dan la vuelta" cuando alcanzan un cierto valor: el módulo (o el plural de ellos). El enfoque moderno de este tipo de ciencia fue desarrollado por Carl Friedrich Gauss en su Disquisitiones Arithmeticae publicado en 1801. Los informáticos son muy aficionados a utilizar este método, ya que es muy interesante y abre ciertas posibilidades nuevas en las operaciones con números.
Esencia
Debido a que el número de horas comienza nuevamente después de llegar a 12, es el módulo aritmético 12. De acuerdo con la definición a continuación, 12 corresponde no solo a 12, sino también a 0, por lo que también se puede nombrar el tiempo llamado " 12:00". "0:00". Después de todo, 12 es lo mismo que 0 módulo 12.
La aritmética modular se puede procesar matemáticamente introduciendo una relación congruente con los números enteros que sea compatible con las operaciones con números enterosnúmeros: suma, resta y multiplicación. Para un entero positivo n, se dice que dos números a y b son congruentes módulo n si su diferencia a - b es múltiplo de n (es decir, si existe un entero k tal que a - b=kn).
Deducciones
En matemáticas teóricas, la aritmética modular es uno de los fundamentos de la teoría de números, que afecta a casi todos los aspectos de su estudio, y también se usa ampliamente en la teoría de grupos, anillos, nudos y álgebra abstracta. En el campo de las matemáticas aplicadas, se utiliza en álgebra informática, criptografía, informática, química, artes visuales y música.
Práctica
Una aplicación muy práctica es el cálculo de sumas de verificación en identificadores de números de serie. Por ejemplo, algunos estándares de libros comunes utilizan el módulo aritmético 11 (si se publicaron antes del 1 de enero de 2007) o el módulo 10 (si se publicaron antes o después del 1 de enero de 2007). Del mismo modo, por ejemplo, en Números Internacionales de Cuenta Bancaria (IBAN). Esto utiliza aritmética de módulo 97 para detectar errores de entrada del usuario en números de cuentas bancarias.
En química, el último dígito del número de registro CAS (el número de identificación único para cada compuesto químico) es el dígito de control. Se calcula tomando el último dígito de las dos primeras partes del número de registro CAS multiplicado por 1, el dígito anterior 2 veces, el dígito anterior 3 veces, etc., sumándolo todo y calculando la suma módulo 10.
¿Qué es la criptografía? El hecho es quetiene una conexión muy fuerte con el tema en discusión. En criptografía, las leyes de la aritmética modular subyacen directamente a los sistemas de clave pública como RSA y Diffie-Hellman. Aquí proporciona los campos finitos que subyacen a las curvas elípticas. Se utiliza en varios algoritmos de clave simétrica, incluido el estándar de cifrado avanzado (AES), el algoritmo de cifrado de datos internacional y RC4.
Solicitud
Este método se usa en áreas donde necesita leer números. Fue desarrollado por matemáticos y todos lo usan, especialmente los informáticos. Esto está bien documentado en libros como Modular Arithmetic for Dummies. Sin embargo, varios expertos recomiendan no tomar en serio este tipo de literatura.
En informática, la aritmética modular se usa a menudo en operaciones bit a bit y otras que involucran estructuras de datos circulares de ancho fijo. A los analistas les encanta usarlo. La operación de módulo se implementa en muchos lenguajes de programación y calculadoras. En este caso, es un ejemplo de tal aplicación. La comparación de módulos, la división con resto y otros trucos también se utilizan en la programación.
En música, la aritmética módulo 12 se utiliza cuando se considera un sistema de igual temperamento de doce tonos, en el que la octava y la enarmónica son equivalentes. En otras palabras, las claves en la relación 1-2 o 2-1 son equivalentes. En la música y otras humanidades, la aritmética juega un papel bastante importante, pero en los libros de textoLos informáticos no suelen escribir sobre ello.
Método de reducción de nueves
El método de conversión 9s ofrece una comprobación rápida de los cálculos aritméticos decimales manuales. Se basa en la aritmética modular módulo 9 y en particular en la propiedad decisiva 10 10 1.
hay otros ejemplos. El módulo aritmético 7 se usa en algoritmos que determinan el día de la semana para una fecha en particular. En particular, la congruencia de Zeller y el algoritmo Doomsday hacen un uso intensivo del módulo aritmético 7.
Otras aplicaciones
Ya se ha dicho sobre la aritmética modular en criptografía. En esta área, ella es simplemente insustituible. De manera más general, la aritmética modular también encuentra aplicaciones en disciplinas como el derecho, la economía (como la teoría de juegos) y otras áreas de las ciencias sociales. En otras palabras, donde la división y distribución proporcional de los recursos juega un papel importante.
Debido a que la aritmética modular tiene una gama tan amplia de usos, es importante saber lo difícil que es resolver un sistema de comparaciones. Un sistema lineal de congruencias se puede resolver en tiempo polinomial en forma de eliminación gaussiana. Esto se describe con más detalle mediante el teorema de congruencia lineal. También existen algoritmos como la reducción de Montgomery para permitir que las operaciones aritméticas simples se realicen de manera eficiente. Por ejemplo, multiplicación y exponenciación módulo n, para números grandes. Es muy importante saber esto para entender lo quecriptografía. Después de todo, solo funciona con operaciones similares.
Congruencia
Algunas operaciones, como encontrar el logaritmo discreto o la congruencia cuadrática, parecen ser tan complejas como la factorización de enteros y, por lo tanto, son el punto de partida para los algoritmos criptográficos y el cifrado. Estos problemas pueden ser NP-intermedios.
Ejemplos
Las siguientes son tres funciones de C bastante rápidas: dos para realizar multiplicaciones modulares y una para elevar a números modulares enteros sin signo de hasta 63 bits, sin desbordamiento transitorio.
Poco después del descubrimiento de los números enteros (1, 2, 3, 4, 5…) se hace evidente que se dividen en dos grupos:
- Par: divisible por 2 (0, 2, 4, 6..).
- Impar: no divisible por 2 (1, 3, 5, 7…).
¿Por qué es importante esta distinción? Este es el comienzo de la abstracción. Notamos las propiedades del número (por ejemplo, par o impar) y no solo el número en sí ("37").
Esto nos permite explorar las matemáticas a un nivel más profundo y encontrar relaciones entre tipos de números en lugar de específicos.
Propiedades de un número
Ser un "tres" es solo otra propiedad de un número. Tal vez no sea tan útil de inmediato como par/impar, pero está ahí. Podemos crear reglas como "trece x tres vena=trece" y así sucesivamente. Pero es una locura. No podemos crear palabras nuevas todo el tiempo.
La operación de módulo (mod abreviado o "%" en muchos lenguajes de programación) es el resto cuandodivisión. Por ejemplo, "5 mod 3=2", lo que significa que 2 es el resto cuando divides 5 entre 3.
Al convertir términos cotidianos a matemáticas, un "número par" es "0 mod 2", lo que significa que el resto es 0 cuando se divide por 2. Un número impar es "1 mod 2" (tiene un resto de 1).
Números pares e impares
¿Qué es par x par x impar x impar? Bueno, es 0 x 0 x 1 x 1=0. De hecho, puedes ver si un número par se multiplica en cualquier lugar, donde el resultado total será cero.
El truco con las matemáticas modulares es que ya las hemos usado para almacenar el tiempo, a veces llamado "aritmética del reloj".
Por ejemplo: 7:00 am (am/pm - no importa). ¿Dónde estará la manecilla de la hora dentro de 7 horas?
Modulaciones
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 es el resto cuando 14 se divide por 12. Ecuación 14 mod 12=2 mod 12 significa 14 horas y 2 horas mira el mismo en un reloj de 12 horas. Son congruentes, indicados por un triple signo igual: 14 ≡ 2 mod 12.
Otro ejemplo: son las 8:00 am. ¿Dónde estará la mano grande dentro de 25 horas?
En lugar de sumar 25 a 8, puedes entender que 25 horas son solo "1 día + 1 hora". La respuesta es simple. Entonces, el reloj terminará con 1 hora de adelanto, a las 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Convirtió intuitivamente 25 a 1 y agregó esto a 8.
Usando el reloj como analogía, podemos averiguar si ellas reglas de la aritmética modular, y funcionan.
Suma/Resta
Digamos que dos horas se ven iguales en nuestro reloj ("2:00" y "14:00"). Si sumamos las mismas x horas a ambos, ¿qué sucede? Bueno, ¡cambian por la misma cantidad en el reloj! 2:00 + 5 horas ≡ 14:00 + 5 horas - ambos mostrarán 7:00.
¿Por qué? Simplemente podemos sumar 5 a los 2 residuos que tienen ambos y avanzan de la misma manera. Para todos los números congruentes (2 y 14), la suma y la resta tienen el mismo resultado.
Es más difícil saber si la multiplicación permanece igual. Si 14 ≡ 2 (mod 12), ¿podemos multiplicar ambos números y obtener el mismo resultado? Veamos qué pasa cuando multiplicamos por 3.
Bueno, 2:003 × 6:00. Pero, ¿qué es 14:003?
Recuerda, 14=12 + 2. Entonces podemos decir
143=(12 + 2)3=(123) + (23)
¡La primera parte (123) se puede ignorar! El desbordamiento de 12 horas que lleva 14 simplemente se repite varias veces. ¿Pero a quién le importa? Ignoramos el desbordamiento de todos modos.
Multiplicación
Al multiplicar, solo importa el resto, es decir, las mismas 2 horas para las 14:00 y las 2:00. Intuitivamente, así es como veo que la multiplicación no cambia la relación con las matemáticas modulares (puedes multiplicar ambos lados de una relación modular y obtener el mismo resultado).
Lo hacemos de manera intuitiva, pero es bueno darle un nombre. Tienes un vuelo que llega a las 15:00. Élretraso de 14 horas. ¿A qué hora aterrizará?
14 ≡ 2 mod 12. Piense en ello como las 2 en punto, de modo que el avión aterrizará a las 5 en punto de la mañana. La solución es simple: 3 + 2=5 am. Esto es un poco más complicado que la operación de módulo simple, pero el principio es el mismo.
