Блог пользователя Sonic_AR

Автор Sonic_AR, история, 4 года назад, По-английски

I have found that the answer to my question is

a^((b^c) % prime — 1) % prime

But I don't know a proof, can anyone tell me the proof or give me a tutorial to read it. Thanks

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 14   Проголосовать: нравится +30 Проголосовать: не нравится

Fermat's little theorem states that for a prime $$$p$$$ and any integer $$$a$$$ such that $$$0 < a < p$$$,

$$$ a^{p-1} \equiv 1 \implies a^b \equiv a^{b \bmod {p-1}} \pmod{p} $$$

In other words, the powers of $$$a$$$ modulo $$$p$$$ repeat with a period of $$$p-1$$$.

This is further generalized by Euler's theorem which implies the powers of $$$a$$$ repeat with a period of $$$p-1$$$. This can be even further generalized with Lagrange's theorem for groups.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://www.geeksforgeeks.org/find-abm-where-b-is-very-large/

You can use above link for better understanding.