El producto sin acarreo de dos números binarios es el resultado de la multiplicación sin acarreo de estos números. Esta operación funciona conceptualmente como una multiplicación larga excepto por el hecho de que el acarreo se descarta en lugar de aplicarse a la posición más significativa. Se puede utilizar para modelar operaciones sobre campos finitos , en particular la multiplicación de polinomios de GF (2) [ X ], el anillo polinomial sobre GF (2) .
La operación también se conoce como multiplicación XOR , ya que la adición de acarreo y descarte es equivalente a un o exclusivo.
Definición
Dados dos números y , con que denota los bits de estos números. Entonces, el producto sin acarreo de estos dos números se define como, con cada bit calculado como exclusivo o de productos de bits a partir de los números de entrada de la siguiente manera: [1]
Ejemplo
Considere a = 10100010 2 y b = 10010110 2 , con todos los números dados en binario. Entonces, la multiplicación sin acarreo de estos es esencialmente lo que se obtendría al realizar una multiplicación larga pero ignorando los acarreos.
1 0 1 0 0 0 1 0 = a --------------- | --- | ------- | - 1 0 0 1 0 1 1 0 | 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 | 0 0 0 0 0 1 0 0 1 0 1 1 0 | 0 ------------------------------ 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0 ^ ^
Así el producto equipaje de menos de una y b sería c = 101100011101100 2 . Para cada bit establecido en el número a , el número b se desplaza hacia la izquierda tantos bits como indique la posición del bit en a . Todas estas versiones desplazadas se combinan luego usando un exclusivo o, en lugar de la adición regular que se usaría para la multiplicación larga regular. Esto se puede ver en las columnas indicadas por ^
, donde la adición regular causaría un acarreo a la columna de la izquierda, lo que no ocurre aquí.
Multiplicación de polinomios
El producto sin acarreo también puede verse como una multiplicación de polinomios sobre el campo GF (2) . Esto se debe a que el exclusivo o corresponde a la adición en este campo.
En el ejemplo anterior, los números a y b se corresponde con polinomios
y el producto de estos es
que es lo que codifica el número c calculado anteriormente. Date cuenta cómo y gracias a la aritmética en GF (2). Esto corresponde a las columnas marcadas ^
en el ejemplo.
Aplicaciones
Los elementos de GF (2 n ), es decir, un campo finito cuyo orden es una potencia de dos , generalmente se representan como polinomios en GF (2) [ X ]. La multiplicación de dos de estos elementos de campo consiste en la multiplicación de los polinomios correspondientes, seguida de una reducción con respecto a algún polinomio irreducible que se toma de la construcción del campo. Si los polinomios están codificados como números binarios, se puede utilizar la multiplicación sin acarreo para realizar el primer paso de este cálculo.
Estos campos tienen aplicaciones en criptografía y para algunos algoritmos de suma de comprobación .
Implementaciones
Los procesadores x86 recientes admiten el conjunto de instrucciones CLMUL y, por lo tanto, proporcionan una instrucción de hardware para realizar esta operación.
Para otros objetivos, es posible implementar el cálculo anterior como un algoritmo de software, y muchas bibliotecas de criptografía contendrán una implementación como parte de sus operaciones aritméticas de campo finito.
Otras bases
La definición de un producto sin acarreo como resultado de un acarreo de descarte de multiplicación larga se aplicaría fácilmente a otras bases distintas de 2. Pero el resultado depende de la base, que por lo tanto es una parte esencial de la operación. Como esta operación se usa típicamente en computadoras que operan en binario, la forma binaria discutida anteriormente es la que se emplea en la práctica.
Los polinomios sobre otros campos finitos de orden primo tienen aplicaciones, pero tratar los coeficientes de tal polinomio como los dígitos de un solo número es bastante poco común, por lo que la multiplicación de tales polinomios no se vería como una multiplicación de números sin acarreo.
Ver también
Referencias
- ↑ Shay Gueron (13 de abril de 2011). "Instrucción de multiplicación sin transporte de Intel y su uso para calcular el modo GCM - Rev 2" . Intel .