Can be calculated efficiently with the Extended Euclidean algorithm.
The beauty of this algorithm is that because exponentiation grows really fast, there is no hope that we can ever learn all the digits of an exponential, as there is simply not enough time or memory for that. Therefore, a natural sub-question is if we can know some part of that number, and knowing the smallest digits is the most natural version of that question.
math.stackexchange.com/questions/2382011/computational-complexity-of-modular-exponentiation-from-rosens-discrete-mathem mentions:
can be calculated in:
Remember that and are the lengths in bits of and , so in terms of the length in bits and we'd get:

Articles by others on the same topic (1)

Modular arithmetic, often referred to as "clock arithmetic," is a system of arithmetic for integers, where numbers wrap around after reaching a certain value known as the modulus. In modular arithmetic, two numbers are considered equivalent if they have the same remainder when divided by the modulus. The basic notation for modular arithmetic is \( a \equiv b \mod m \), which means that \( a \) and \( b \) give the same remainder when divided by \( m \).