कुठलेही गणितीय प्रश्न सोडवा

चरणानुक्रमे

1. 2790^{2753} \bmod 3233

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

2. 2790 \equiv 2790 \pmod{3233}

   Reduce the base first.

3. 2753 = 101011000001_2

   Write the exponent in binary: 12 squarings at most.

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

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

5. 2790^2 \equiv 2269 \pmod{3233}

   Square the running power.

6. 2269^2 \equiv 1425 \pmod{3233}

   Square the running power.

7. 1425^2 \equiv 301 \pmod{3233}

   Square the running power.

8. 301^2 \equiv 77 \pmod{3233}

   Square the running power.

9. 77^2 \equiv 2696 \pmod{3233}

   Square the running power.

10. 2696^2 \equiv 632 \pmod{3233}

    Square the running power.

11. r \leftarrow r \cdot 632 \equiv 1295 \pmod{3233}

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

12. 632^2 \equiv 1765 \pmod{3233}

    Square the running power.

13. r \leftarrow r \cdot 1765 \equiv 3177 \pmod{3233}

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

14. 1765^2 \equiv 1846 \pmod{3233}

    Square the running power.

15. 1846^2 \equiv 134 \pmod{3233}

    Square the running power.

16. r \leftarrow r \cdot 134 \equiv 2195 \pmod{3233}

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

17. 134^2 \equiv 1791 \pmod{3233}

    Square the running power.

18. \vdots

    Same pattern for the remaining bits.

19. 2790^{2753} \equiv 65 \pmod{3233}

    Done.

उत्तर उघडा

2790^{2753} \bmod 3233 = 65