Sistema de numeración de residuos

Un sistema de numeración residual o sistema de numeración residual ( SNR ) es un sistema numérico que representa los números enteros mediante sus valores módulo varios enteros coprimos entre sí, denominados módulos. Esta representación es posible gracias al teorema chino del resto , que afirma que, si M es el producto de los módulos, existe, en un intervalo de longitud M , exactamente un entero con cualquier conjunto dado de valores modulares. El uso de un sistema de numeración residual para operaciones aritméticas también se denomina aritmética multimodular .

La aritmética multimodular se utiliza ampliamente para cálculos con números enteros grandes, típicamente en álgebra lineal , porque proporciona cálculos más rápidos que con los sistemas numéricos habituales, incluso teniendo 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 de polinomios , el cálculo de bases de Gröbner y la criptografía .

Un sistema de numeración residual se define mediante un conjunto de k números enteros.

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

denominados módulos , que generalmente se supone que son coprimos entre sí (es decir, cualesquiera dos de ellos tienen un máximo común divisor igual a uno). Se han definido sistemas de numeración de residuos para módulos no coprimos, pero no se utilizan comúnmente debido a sus peores propiedades. ^{[ 1 ]}

Un número entero x se representa en el sistema de numeración residual mediante la familia de sus restos (indexados por los módulos de los índices de los módulos).

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

bajo la división euclidiana por los módulos. Es decir

${\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${\displaystyle m_{i}}$Dos enteros cuya diferencia es un múltiplo de M tienen la misma representación en el sistema de numeración de residuos definido por los m _i s. Más precisamente, el teorema chino del resto 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 entero${\displaystyle X}$en el intervalo${\displaystyle 0,\dots ,M-1}$. Para números con signo, el rango dinámico es${\textstyle {-\lfloor M/2\rfloor }\leq X\leq \lfloor (M-1)/2\rfloor }$ (cuando${\displaystyle M}$es par, generalmente se representa un valor negativo adicional). ^{[ 2 ]}

Para sumar, restar y multiplicar números representados en un sistema de numeración 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 enteros x e y , respectivamente representados por los residuos${\displaystyle [x_{1},\ldots ,x_{k}]}$y${\displaystyle [y_{1},\ldots ,y_{k}],}$es el entero z representado por${\displaystyle [z_{1},\ldots,z_{k}],}$de tal manera que

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

para i = 1, ..., k (como es habitual, mod denota la operación 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 forma similar.

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

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

Los sistemas de números aleatorios (SNR) tienen aplicaciones en el campo de la aritmética informática digital . Al descomponer un número entero grande en un conjunto de números enteros más pequeños, un cálculo grande puede realizarse como una serie de cálculos más pequeños que pueden ejecutarse de forma independiente y en paralelo.

• Sistema de cobertura
• Sistema de residuos reducidos

• Szabo, Nicholas S.; Tanaka, Richard I. (1967). Aritmética de residuos y sus aplicaciones a la tecnología informática (1.ª  ed.). Nueva York, EE. UU.: McGraw-Hill .
• Sonderstrand, Michael A.; Jenkins, W. Kenneth; Jullien, Graham A.; Taylor, Fred J., eds. (1986). Aritmética del sistema de numeración residual: aplicaciones modernas en el procesamiento digital de señales . Serie de reimpresiones de IEEE Press (1.ª  ed.). Nueva York, EE. UU.: IEEE Circuits and Systems Society , IEEE Press . ISBN 0-87942-205-XLCCN 86-10516 . Código de pedido IEEE PC01982. (viii+418+6 páginas)
• Chervyakov, NI; Molahosseini, AS; Lyakhov, PA (2017). Conversión de residuos a binario para conjuntos de módulos generales basada en el teorema aproximado del resto chino . International Journal of Computer Mathematics , 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 . CÓDIGO AURCAT . Mi at1588 .     
• Chervyakov, NI; Lyakhov, PA; Deryabin, MA (2020). Solución basada en el sistema de numeración de residuos para reducir el costo de hardware de una red neuronal convolucional . Neurocomputing , 407, 439-453, doi: 10.1016/j.neucom.2020.04.018.
• Bajard, Jean-Claude; Méloni, Nicolas; Plantard, Thomas (06-10-2006) [julio de 2005]. "Bases RNS eficientes para criptografía" (PDF) . IMACS'05: Congreso Mundial: Computación Científica, Matemáticas Aplicadas y Simulación . París, Francia. HAL Id: lirmm-00106470. Archivado (PDF) del original el 23-01-2021 . Recuperado el 23-01-2021 .(1+7 páginas)
• Omondi, Amos; Premkumar, Benjamin (2007). Sistemas de numeración residual: 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 numeración residual: teoría y aplicaciones (1.ª  ed.). Birkhäuser / Springer International Publishing Switzerland . 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 embebidos con sistemas aritméticos y numéricos 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 del 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 Electronic Journal on Informatics and Operations Research . 5 (1): 1– 10.
• Orange, Sébastien; Renault, Guénaël; Yokoyama, Kazuhiro (2012). "Aritmética eficiente en campos de extensión algebraica sucesivos mediante simetrías" . Matemáticas en Ciencias de la Computación . 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 computacional en computación científica . Berlín/Heidelberg, Alemania: Springer. pp. 361–362 . 
• Hladík, Jakub; Šimeček, Ivan (enero de 2012). "Aritmética modular para la resolución de ecuaciones lineales en la GPU". Seminario de Análisis Numérico . págs. 68–70 . 
• Pernet, Clément (junio de 2015). "Algebra lineal algorítmica exacta: teoría y práctica". Actas del Simposio Internacional de Computación Simbólica y Algebraica de la ACM de 2015. Association for Computing Machinery . págs. 17-18 . 
• Lecerf, Grégoire (2018). "Sobre la complejidad del algoritmo subresultante de Lickteig-Roy". Journal of Symbolic Computation .
• Yokoyama, Kazuhiro; Noro, Masayuki; Takeshima, Taku (1994). "Enfoque multimodular para la factorización en tiempo polinomial de polinomios integrales bivariados" . Journal of Symbolic Computation . 17 (6): 545– 563. doi : 10.1006/jsco.1994.1034 .
• Isupov, Konstantin (2021). "Cálculo de alto rendimiento en el sistema de numeración residual mediante aritmética de punto flotante". Computation . 9 (2): 9. doi:10.3390/computation9020009 . ISSN 2079-3197.