Sistema de numeración de residuos

Aritmética multimodular

Un sistema de numeración de residuos ( RNS ) es un sistema de numeración que representa números enteros por sus valores módulo de varios enteros coprimos por pares llamados módulos. Esta representación está permitida por el teorema del resto chino , que afirma que, si M es el producto de los módulos, hay, en un intervalo de longitud M , exactamente un número entero que tiene cualquier conjunto dado de valores modulares. La aritmética de un sistema numérico de residuos también se llama aritmética multimodular .

La aritmética multimodular se usa ampliamente para el cálculo con números enteros grandes, generalmente en álgebra lineal , porque proporciona un cálculo más rápido que con los sistemas numéricos habituales, incluso cuando se tiene en cuenta el tiempo de conversión entre sistemas numéricos. Otras aplicaciones de la aritmética multimodular incluyen el máximo común divisor polinomial , el cálculo de bases de Gröbner y la criptografía .

Definición

Un sistema de numeración de residuos está definido por un conjunto de k números enteros

${\displaystyle \{m_{1},m_{2},m_{3},\ldots ,m_{k}\},}$

llamados módulos , que generalmente se supone que son coprimos por pares (es decir, dos de ellos tienen un máximo común divisor igual a uno). Se han definido sistemas de números de residuos para módulos no coprimos, pero no se utilizan habitualmente debido a sus peores propiedades. Por lo tanto, no serán considerados en lo que resta de este artículo. ^[1]

Un número entero x está representado en el sistema de numeración de residuos por el conjunto de sus restos.

${\displaystyle \{x_{1},x_{2},x_{3},\ldots ,x_{k}\}}$

bajo división euclidiana por módulos. Eso es

${\displaystyle x_{i}=x\operatorname {mod} m_{i},}$

y

${\displaystyle 0\leq x_{i}<m_{i}}$

por cada yo

Sea M el producto de todos los . Dos números enteros cuya diferencia es múltiplo de M tienen la misma representación en el sistema de numeración de residuos definido por m _i s. Más precisamente, el teorema del resto chino afirma que cada uno de los M conjuntos diferentes de posibles residuos representa exactamente una clase de residuo módulo M. Es decir, cada conjunto de residuos representa exactamente un número entero en el intervalo . Para números con signo, el rango dinámico es (cuando es par, generalmente se representa un valor negativo adicional). ^[2] ${\displaystyle m_{i}}$ ${\displaystyle X}$ ${\displaystyle 0,\dots ,M-1}$ ${\textstyle {-\lfloor M/2\rfloor }\leq X\leq \lfloor (M-1)/2\rfloor }$ ${\displaystyle M}$

Operaciones aritmeticas

Para sumar, restar y multiplicar números representados en un sistema numérico de residuos, basta con realizar la misma operación modular en cada par de residuos. Más precisamente, si

${\displaystyle [m_{1},\ldots ,m_{k}]}$

es la lista de módulos, la suma de los números enteros x e y , representados respectivamente por los residuos y es el número entero z representado por tal que ${\displaystyle [x_{1},\ldots ,x_{k}]}$ ${\displaystyle [y_{1},\ldots ,y_{k}],}$ ${\displaystyle [z_{1},\ldots ,z_{k}],}$

${\displaystyle z_{i}=(x_{i}+y_{i})\operatorname {mod} m_{i},}$

para i = 1, ..., k (como es habitual, mod denota la operación de módulo que consiste en tomar el resto de la división euclidiana por el operando derecho). La resta y la multiplicación se definen de manera similar.

Para una sucesión de operaciones, no es necesario aplicar la operación de módulo en cada paso. Puede aplicarse al final del cálculo o, durante el cálculo, para evitar el desbordamiento de las operaciones de hardware.

Sin embargo, operaciones como comparación de magnitudes, cálculo de signos, detección de desbordamiento, escalado y división son difíciles de realizar en un sistema de número de residuos. ^[3]

Comparación

Si dos números enteros son iguales, entonces todos sus residuos son iguales. Por el contrario, si todos los residuos son iguales, entonces los dos números enteros son iguales o sus diferencias son múltiplos de M. De ello se deduce que probar la igualdad es fácil.

Por el contrario, probar desigualdades ( x < y ) es difícil y, por lo general, requiere convertir números enteros a la representación estándar. Como consecuencia, esta representación de números no es adecuada para algoritmos que utilizan pruebas de desigualdad, como la división euclidiana y el algoritmo euclidiano .

División

La división en los sistemas de numeración de residuos es problemática. Por otro lado, si es coprimo con (es decir ), entonces ${\displaystyle B}$ ${\displaystyle M}$ ${\displaystyle b_{i}\not =0}$

${\displaystyle C=A\cdot B^{-1}\mod M}$

se puede calcular fácilmente mediante

${\displaystyle c_{i}=a_{i}\cdot b_{i}^{-1}\mod m_{i},}$

donde es el inverso multiplicativo del módulo y es el inverso multiplicativo del módulo . ${\displaystyle B^{-1}}$ ${\displaystyle B}$ ${\displaystyle M}$ ${\displaystyle b_{i}^{-1}}$ ${\displaystyle b_{i}}$ ${\displaystyle m_{i}}$

Aplicaciones

RNS tiene aplicaciones en el campo de la aritmética informática digital . Al descomponer en esto un número entero grande en un conjunto de números enteros más pequeños, se puede realizar un cálculo grande como una serie de cálculos más pequeños que se pueden realizar de forma independiente y en paralelo.

Ver también

• Sistema de cobertura
• Sistema de residuos reducidos

Referencias

1. Parhami, Behrooz (2010). Aritmética informática: algoritmos y diseños de hardware (2 ed.). Nueva York, Estados Unidos: Oxford University Press . ISBN 978-0-19-532848-6. Archivado desde el original el 4 de agosto de 2020 . Consultado el 23 de enero de 2021 .(xxv+641 páginas)
2. Colgado, CY; Parhami, B. (1 de febrero de 1994). "Un método aproximado de detección de signos para números de residuos y su aplicación a la división RNS" (PDF) . Computadoras y Matemáticas con Aplicaciones . 27 (4): 23–35. doi :10.1016/0898-1221(94)90052-3.
3. Isupov, Konstantin (7 de abril de 2020) [20 de marzo de 2020, 8 de marzo de 2020, 17 de febrero de 2020]. "Uso de intervalos de coma flotante para cálculos no modulares en el sistema de numeración de residuos". Acceso IEEE . 8 : 58603–58619. Código Bib : 2020IEEEA...858603I. doi : 10.1109/ACCESS.2020.2982365 . ISSN  2169-3536.

Otras lecturas

• Szabo, Nicolás S.; Tanaka, Richard I. (1967). Aritmética de residuos y sus aplicaciones a la tecnología informática (1 ed.). Nueva York, Estados Unidos: McGraw-Hill .
• Sonderstrand, Michael A.; Jenkins, W. Kenneth; Jullien, Graham A.; Taylor, Fred J., eds. (1986). Aritmética del sistema de número de residuos: aplicaciones modernas en el procesamiento de señales digitales . Serie de reimpresiones de prensa IEEE (1 ed.). Nueva York, Estados Unidos: Sociedad de Sistemas y Circuitos IEEE , IEEE Press . ISBN 0-87942-205-X. LCCN  86-10516. Código de pedido IEEE PC01982.(viii+418+6 páginas)
• Cherviakov, NI; Molahosseini, AS; Lyakhov, PA (2017). Conversión de residuo a binario para conjuntos de módulos generales basada en el teorema chino aproximado del resto. Revista internacional de matemáticas informáticas , 94:9, 1833-1849, doi: 10.1080/00207160.2016.1247439.
• Fin'ko [Финько], Oleg Anatolevich [Олег Анатольевич] (junio de 2004). "Grandes sistemas de funciones booleanas: realización mediante métodos aritméticos modulares". Automatización y Control Remoto . 65 (6): 871–892. doi :10.1023/B:AURC.0000030901.74901.44. ISSN  0005-1179. LCCN  56038628. S2CID  123623780. CODEN  AURCAT. Mi  at1588.
• Cherviakov, NI; Lyakhov, PA; Deryabin, MA (2020). Solución basada en el sistema de números residuales para reducir el costo de hardware de una red neuronal convolucional. Neurocomputación , 407, 439-453, doi: 10.1016/j.neucom.2020.04.018.
• Bajard, Jean-Claude; Méloni, Nicolás; Plantard, Thomas (6 de octubre de 2006) [julio de 2005]. «Bases RNS eficientes para Criptografía» (PDF) . IMACS'05: Congreso Mundial: Computación Científica Matemática Aplicada y Simulación . París, Francia. Identificación de HAL: lirmm-00106470. Archivado (PDF) desde el original el 23 de enero de 2021 . Consultado el 23 de enero de 2021 .(1+7 páginas)
• Omondi, Amós; Premkumar, Benjamín (2007). Sistemas de números de residuos: teoría e implementación . Londres, Reino Unido: Imperial College Press . ISBN 978-1-86094-866-4.(296 páginas)
• Mohan, PV Ananda (2016). Sistemas de números de residuos: teoría y aplicaciones (1 ed.). Birkhäuser / Springer International Publishing Suiza . doi :10.1007/978-3-319-41385-3. ISBN 978-3-319-41383-9. LCCN  2016947081.(351 páginas)
• Amir Sabbagh, Molahosseini; de Sousa, Leonel Seabra; Chip-Hong Chang, eds. (21 de marzo de 2017). Diseño de sistemas integrados con sistemas numéricos y aritméticos especiales (1 ed.). Springer International Publishing AG . doi :10.1007/978-3-319-49742-6. ISBN 978-3-319-49741-9. LCCN  2017934074.(389 páginas)
• "Algoritmos de división". Archivado desde el original el 17 de febrero de 2005 . Consultado el 24 de agosto de 2023 .
• Knuth, Donald Ervin . El arte de la programación informática . Addison Wesley .
• Harvey, David (2010). "Un algoritmo multimodular para calcular números de Bernoulli". Matemáticas de la Computación . 79 (272): 2361–2370. arXiv : 0807.1347 . doi : 10.1090/S0025-5718-2010-02367-1 . S2CID  11329343.
• Lecerf, Grégoire; Schost, Éric (2003). "Multiplicación rápida de series de potencias multivariadas en característica cero". SADIO Revista Electrónica de Informática e Investigación Operativa . 5 (1): 1–10.
• Naranja, Sébastien; Renault, Guenaël; Yokoyama, Kazuhiro (2012). "Aritmética eficiente en sucesivos campos de extensión algebraica mediante simetrías". Matemáticas en Informática . 6 (3): 217–233. doi :10.1007/s11786-012-0112-y. S2CID  14360845.
• Yokoyama, Kazuhiro (septiembre de 2012). "Uso de técnicas modulares para el cálculo eficiente de operaciones ideales". Taller Internacional sobre Álgebra Informática en Computación Científica . Berlín / Heidelberg, Alemania: Springer. págs. 361–362.
• Hladík, Jakub; Šimeček, Ivan (enero de 2012). "Aritmética modular para resolver ecuaciones lineales en la GPU". Seminario de Análisis Numérico . págs. 68–70.
• Pernet, Clément (junio de 2015). "Algebra algorítmica lineal exacta: teoría y práctica". Actas de la ACM de 2015 sobre el Simposio internacional sobre computación simbólica y algebraica . Asociación para Maquinaria de Computación . págs. 17-18.
• Lecerf, Grégoire (2018). "Sobre la complejidad del algoritmo subresultante de Lickteig-Roy". Revista de Computación Simbólica .
• Yokoyama, Kazuhiro; Noro, Masayuki; Takeshima, Taku (1994). "Enfoque multimodular para la factorización en tiempo polinomial de polinomios integrales bivariados". Revista de Computación Simbólica . 17 (6): 545–563. doi : 10.1006/jsco.1994.1034 .
• Isupov, Konstantin (2021). "Computación de alto rendimiento en el sistema de número de residuos utilizando aritmética de coma flotante". Computación . 9 (2): 9. doi:10.3390/computation9020009. ISSN 2079-3197.