Multiplication in binary is remarkably refreshing, compared to four-digit multiplications you might have labored through in school. The multipication table could hardly be simpler.
x| 0 1 -+------- 0| 0 0 1| 0 1
Because we only ever multiply by zero or one, long multiplication is just a matter of shifting and adding.
Here is the product \( 1300 = 100 \times 13 \).
01100100 100 x 00001101 x 13 -------------- ------ 01100100 1300 01100100 + 01100100 -------------- 10100010100 1024+256+16+4 xxx00010100 20 = 1300 mod 256
Each step of the multiplication is easy, because the only multiplication is by zero or one. The diagram above omits the zero rows, as we do in decimal.
The product of two 8-bit bytes can require a full two bytes to hold the result In the example above, the one-byte result is gotten by lopping off all the high bits beyond the lowest 8 bits. This is similar to what we did with a carry-out in addition.
In mathematical terms, taking the low byte of the result is equivalent to computing the result modulo \( 256 = 2^{8} \). Discarding the higher bits is the same is ignoring multiples of \( 256 \).