1
$\begingroup$

I was studying CRC and came across modulo 2 arithmetic. When we add two 1 bit numbers like 1 + 1, 0 + 1, then the result is summation modulo 2 which is similar to XORing of the two bits. My doubt is when this is extended to multiple bits why is the solution not summation modulo 2 i.e. one bit result either 0 or 1, instead it is defined as XOR of the two n-bit numbers to be added. Modulo 2 addition should be sum modulo 2 right?

$\endgroup$

1 Answer 1

0
$\begingroup$

There is a difference between applying the modulus to the entire integer, or applying it to the individual bits. The first would have the effect you describe here: $1010_b + 0101_b \equiv 1_b(\mod 2)$. However, that is not always very useful. Bitwise application of the modulus can give you arithmetic in finite fields. In particular, bitwise addition of $2^k$-ary binary integers can be extended into the finite field $\mathbb{F}_{2^k}$.

Much of the theory of cryptography and coding theory rely on finite fields, both because arithmetic tends to be more computationally challenging (for crypto, this means we can design encryption methods that are hard to decrypt, for coding theory, this means that there is something complicated to study ;) ), especially compared with infinite fields such as the real numbers, $\mathbb{R}$. If all this went over your head, just remember that there is a difference between bitwise and ordinary modulus, and that the bitwise modulus has a well-known and solid theoretical component as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.