የቁጥር ችግር

እርምጃ በደረጃ

1. 2^{1000} \bmod 13

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

2. 2 \equiv 2 \pmod{13}

   Reduce the base first.

3. 1000 = 1111101000_2

   Write the exponent in binary: 10 squarings at most.

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

   Square the running power.

5. 4^2 \equiv 3 \pmod{13}

   Square the running power.

6. 3^2 \equiv 9 \pmod{13}

   Square the running power.

7. r \leftarrow r \cdot 9 \equiv 9 \pmod{13}

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

8. 9^2 \equiv 3 \pmod{13}

   Square the running power.

9. 3^2 \equiv 9 \pmod{13}

   Square the running power.

10. r \leftarrow r \cdot 9 \equiv 3 \pmod{13}

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

11. 9^2 \equiv 3 \pmod{13}

    Square the running power.

12. r \leftarrow r \cdot 3 \equiv 9 \pmod{13}

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

13. 3^2 \equiv 9 \pmod{13}

    Square the running power.

14. r \leftarrow r \cdot 9 \equiv 3 \pmod{13}

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

15. 9^2 \equiv 3 \pmod{13}

    Square the running power.

16. r \leftarrow r \cdot 3 \equiv 9 \pmod{13}

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

17. 3^2 \equiv 9 \pmod{13}

    Square the running power.

18. r \leftarrow r \cdot 9 \equiv 3 \pmod{13}

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

19. \vdots

    Same pattern for the remaining bits.

20. 2^{1000} \equiv 3 \pmod{13}

    Done.

መልሱን አሳይ

2^{1000} \bmod 13 = 3