Multiply on One Bits - Modular Exponentiation

A one bit multiplies the squared value by the base. A zero bit keeps the square.

highlighted = computed this step

The first one bit starts the value

The ladder begins at 1. Because the first bit is 1, multiplying by base 7 gives row result 7.

1\cdot7\bmod{}33=7

When the bit is 1, the row multiplies the square by base 7.

\text{bit}=1

Here square 16 times base 7 reduces to 13.

16\cdot7\bmod{}33=13

When the bit is 0, the multiply column is skipped and the row result stays 4.

\text{bit}=0\Rightarrow r=4

Skip does not mean ignore the row. It means the square value 4 is already the row result 4.

\text{square only}=4

A bit chooses between square-only and square-then-multiply; both paths still reduce to one row result.

\text{bit controls multiply}