I-ScrabbleName

Inyathelo ngenyathelo

1. 65^{17} \bmod 3233

   Never compute the huge power. Reduce after every multiplication (repeated squaring).

2. 65 \equiv 65 \pmod{3233}

   Reduce the base first.

3. 17 = 10001_2

   Write the exponent in binary: 5 squarings at most.

4. r \leftarrow r \cdot 65 \equiv 65 \pmod{3233}

   This bit is 1: multiply the result by the current power.

5. 65^2 \equiv 992 \pmod{3233}

   Square the running power.

6. 992^2 \equiv 1232 \pmod{3233}

   Square the running power.

7. 1232^2 \equiv 1547 \pmod{3233}

   Square the running power.

8. 1547^2 \equiv 789 \pmod{3233}

   Square the running power.

9. r \leftarrow r \cdot 789 \equiv 2790 \pmod{3233}

   This bit is 1: multiply the result by the current power.

10. 65^{17} \equiv 2790 \pmod{3233}

    Done.

Bonisa impendulo

65^{17} \bmod 3233 = 2790