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 cuerpos finitos , en particular la multiplicación de polinomios de GF(2)[ X ], el anillo de polinomios sobre GF(2) .
La operación también se conoce como multiplicación XOR , ya que la suma con descarte de acarreo es equivalente a una operación OR exclusiva.
Dados dos números y , con denotando los bits de estos números, el producto sin acarreo de estos dos números se define como , con cada bit calculado como el o exclusivo de productos de bits de los números de entrada de la siguiente manera: [1]
Consideremos a = 10100010 2 y b = 10010110 2 , con todos los números expresados en binario. Entonces, la multiplicación sin acarreo de estos números 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 = un ---------------|---|-------|-- 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 ^ ^
Por lo tanto, el producto sin acarreo de a y b sería c = 101100011101100 2 . Por cada bit establecido en el número a , el número b se desplaza hacia la izquierda tantos bits como lo indica la posición del bit en a . Todas estas versiones desplazadas se combinan luego utilizando un o exclusivo, en lugar de la suma regular que se usaría para la multiplicación larga regular. Esto se puede ver en las columnas indicadas por ^, donde la suma regular causaría un acarreo a la columna de la izquierda, lo que no sucede aquí.
El producto sin acarreo también puede verse como una multiplicación de polinomios sobre el cuerpo GF(2) . Esto se debe a que la o exclusiva corresponde a la adición en este cuerpo.
En el ejemplo anterior, los números a y b corresponden a polinomios.
y el producto de estos es
que es lo que codifica el número c calculado anteriormente. Observe cómo y gracias a la aritmética en GF(2). Esto corresponde a las columnas marcadas en el ejemplo.^
Los elementos de GF(2 n ), es decir, un cuerpo finito cuyo orden es una potencia de dos , se representan habitualmente como polinomios en GF(2)[ X ]. La multiplicación de dos de estos elementos de cuerpo 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 cuerpo. Si los polinomios se codifican 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 en algunos algoritmos de suma de comprobación .
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.
También es parte de las extensiones ISA de manipulación de bits RISC-V Zbc: Multiplicación sin acarreo.
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.
La definición de un producto sin acarreo como resultado de una larga multiplicación descartando el acarreo se aplicaría fácilmente a bases distintas de 2. Pero el resultado depende de la base, que es, por lo tanto, una parte esencial de la operación. Como esta operación se utiliza normalmente en ordenadores que funcionan en binario, la forma binaria analizada anteriormente es la que se emplea en la práctica.
Los polinomios sobre otros cuerpos finitos de orden primo tienen aplicaciones, pero tratar los coeficientes de un polinomio de este tipo como los dígitos de un único número es bastante poco común, por lo que la multiplicación de dichos polinomios no sería vista como una multiplicación de números sin acarreo.
