Groups

Қадами ба қадам

1. 3^{100} \bmod 7

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

2. 3 \equiv 3 \pmod{7}

   Reduce the base first.

3. 100 = 1100100_2

   Write the exponent in binary: 7 squarings at most.

4. 3^2 \equiv 2 \pmod{7}

   Square the running power.

5. 2^2 \equiv 4 \pmod{7}

   Square the running power.

6. r \leftarrow r \cdot 4 \equiv 4 \pmod{7}

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

7. 4^2 \equiv 2 \pmod{7}

   Square the running power.

8. 2^2 \equiv 4 \pmod{7}

   Square the running power.

9. 4^2 \equiv 2 \pmod{7}

   Square the running power.

10. r \leftarrow r \cdot 2 \equiv 1 \pmod{7}

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

11. 2^2 \equiv 4 \pmod{7}

    Square the running power.

12. r \leftarrow r \cdot 4 \equiv 4 \pmod{7}

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

13. 3^{100} \equiv 4 \pmod{7}

    Done.