# Aritmética módulo 2

A aritmética módulo 2 é uma forma de aritmética modular especialmente usada em ciência da computação por ser facilmente implementada dentro de processadores utilizando o sistema binário. Uma característica importante desta forma de aritmética é o fato de não haver propagação de dígitos (carry) entre as casas binárias nas operações aritméticas. Por exemplo, em binário tradicional 01$_2$ + 01$_2$ = 10$_2$, onde há uma propagação do dígito 1 para uma casa à esquerda. Na aritmética módulo 2 temos que 01$_2$ + 01$_2$ = 00$_2$, onde não há propagação do dígito 1. Ter em conta que, ao longo deste tópico, a nomenclatura "X$_2$" refere-se a um número binário X (i.e. na base 2).

## Representação polinomial

Os números binários usados na aritmética módulo 2 podem ser vistos como sendo polinômios onde cada dígito é um dos coeficientes do polinômio. Assim o número 10010$_2$ pode ser representado por $1x^{4}+0x^{3}+0x^{2}+1x^{1}+0x^{0}$, ou simplesmente $x^{4}+x$. As operações sobre estes coeficientes obedecem a aritmética modular de base 2, onde temos:
    ${\begin{cases}0+0{\pmod {2}}&=0\\0+1{\pmod {2}}&=1\\1+0{\pmod {2}}&=1\\1+1{\pmod {2}}&=0\end{cases}}$
    Obs: 1 + 1 = 0 (e vai 1 que se soma ao dígito seguinte)
Igualmente, a operação de subtração segue a mesma regra de aritmética modular em relação aos coeficientes dos polinômios:
    ${\begin{cases}0-0{\pmod {2}}&=0\\0-1{\pmod {2}}&=1\\1-0{\pmod {2}}&=1\\1-1{\pmod {2}}&=0\end{cases}}$
    Obs: 0 - 1 = 1 (e vai 1 que se subtrai ao dígito seguinte)

## Soma e subtração : caso comum

Podemos notar no diagrama supracitado, que as duas operações tem sempre o mesmo resultado equivalente ao da operação lógica de ou exclusivo (ou XOR, da sigla em inglês eXclusive OR). A aritmética módulo 2 pode então ser facilmente calculada através de uma operação de ou-exclusivo realizada bit a bit entre os coeficientes do polinômio, ou seja, dos dígitos binários.
Como exemplo podemos somar o polinômio $x^{4}+x$ com outro polinômio $x^{4}+x^{3}+1$. O primeiro passo é a transformação do polinômio em um número binário:
    $x^{4}+x=10010_{2}$
e
    $x^{4}+x^{3}+1=11001_{2}$
Procedemos então ao ou-exclusivo bit-a-bit (designada também por "soma polinomial em módulo 2"):
    ${\begin{alignedat}{2}&(x^{4}+x)+(x^{4}+x^{3}+1)\\=&(1+1)x^{4}+(0+1)x^{3}+(0+0)x^{2}+(0+1)x^{1}+(0+1)x^{0}\\=&(0)x^{4}+(1)x^{3}+(0)x^{2}+(1)x^{1}+(1)x^{0}\\=&x^{3}+x+1\end{alignedat}}$
ou ainda:
    $10010_{2}\oplus 11001_{2}=01011_{2}$

## Divisão

Existem diversas formas realizar a divisão de módulo 2 entre dois números binarios. A melhor maneira é fazer a representação polinomial do Dividendo D e do Divisor d , e subtrair consequentemente os monómios do polinômio D. Ao Dividendo polinomial D inicial, é concantenado á sua direita tantos monómios quanto o grau do polinômio d .
Exemplo: Dividir 101011 por 11001
11001 corresponde ao Divisor d(o qual também é designado por polinômio "gerador"), e é representado pelo polinômio de grau 4, 1$x^{4}$ + 1$x^{3}$ + 0$x^{2}$+ 0$x^{1}$ + 1$x^{0}$ = $x^{4}+x^{3}+1$
101011 corresponde ao Dividendo inicial D
1010110000 corresponde ao Dividendo inicial D concatenado com tantos bits nulos quanto o grau do polinômio d (Neste caso o grau polinomial é de 4)
Assim sendo, 1010110000 o qual corresponde ao Dividendo final , será expresso pelo polinômio
Procedemos á divisão :
$x^{9}$__ $x^{7}$__$x^{5}$ $x^{4}$ __ __ __ __ | $x^{4}+x^{3}+1$
-$x^{9}$$x^{8}$__ __$x^{5}$ $x^{5}+x^{4}+1$  0 $x^{8}$ $x^{7}$__0 -$x^{8}$ $x^{7}$ __0 $x^{4}$  0 0 $x^{4}$  -$x^{4}$ $x^{3}$ 1  0 $x^{3}$ 1
RESTO : $x^{3}$+1 = 1 $x^{3}$+ 0$x^{2}$+ 0$x^{1}$+ 1 $x^{0}$; EM BINARIO : 1 0 0 1
QUOCIENTE : $x^{5}+x^{4}+1$ = 1 $x^{5}$+ 1 $x^{4}$+ 0 $x^{3}$+ 0 $x^{2}$+ 0$x^{1}$+ 1 $x^{0}$; EM BINARIO: 1 1 0 0 0 1