What is the explanation for being able to simplify 'A^(B^C) mod prim' such that it is efficiently computable?

Question

Prelude

We want compute the modular exponentiation A^(BC) mod p = ?, where A, B, C, and p are known and p is a prim number. For example: 2⁴³mod 23 = 6

If we compute it in a straightforward way, first B^C = e, and then A^e = n, and finally n mod p; we will run into the problem of creating (potentially) very large intermediary results for e and n. For example: e = 4³ = 64, n = 2⁶⁴ ≈ 1.845x10¹⁹, and finally n mod 23 = 6

However, doing it in the straightforward way we did not take advantage of the fact that p is a prim number and that we are doing modular exponentiation. And also doing so, we will run into problems computing the result with a computer program in terms of time (CPU) and space (memory).

(Yes, we could do fast modular exponentiation using the identity (a ⋅ b) mod m = [(a mod m) ⋅ (b mod m)] mod m by first reducing A^(BC) mod p to A^e mode p. For exmaple A² mod p = (A ⋅ A) mod p = [(A mod p) ⋅ (A mod p)] mod p – but that is not where we want to go with this).

The smart way – use Fermat's little theorem

As documented in Find power of power under mod of a prime on GeeksforGeeks and the origin of this question, our exponent B^C in A^(BC) mod p can be expressed differently using Fermat's little theorem.

Fermat's little theorem states: a^{(p - 1)} ≡ 1 (mod p) if p is a prime

Leading to following transformations:

1. It is possible to rewrite the exponent B^C as x ⋅ (p - 1) + y

2. Using that alternate expression our A^BC becomes A^{x ⋅ (p - 1) + y} = A^{x ⋅ (p - 1)} ⋅ A^y

3. Using Fermat's little theorem A^{x ⋅ (p - 1)} = 1; computing A^(BC) mod p becomes computing A^y

4. Using B^C = x ⋅ (p - 1) + y then y can be written as B^C mod (p - 1)

From the above we get A^(BC) mod p = (A^y) mod p

And with all of that we can compute A^(BC) mod p in two steps while keeping the intermediary results small.

1. y = (B^C) mod (p - 1)
2. result = (A^y) mod p

For example: 2⁴³mod 23

1. y = 4³ mod (23 - 1) = 64 mod 22 = 20
2. result = 2²⁰ mod 23 = 1048576 mod 23 = 6

Question

My question is about above transformations, and I could not find an (easy to understand) explanation anywhere. Also intensly looking at Fermat's little theorem did not help. Possibly these transformations should be obvious, but it is simply not clear to me.

In particular, I do not understand why the exponent B^C can be expressed as x ⋅ (p - 1) + y. – What is the reasoning behind this?

And also, why should it be "obvious" when using Fermat's little theorem:

a^{(p - 1)} ≡ 1 (mod p) that A^{x ⋅ (p - 1)} = 1?

It would be great if someone could explain those transformations in an easy understandable way.

Answer 1

Let me address the two main questions you have:

In particular, I do not understand why the exponent B^C can be expressed as x ⋅ (p - 1) + y. – What is the reasoning behind this?

Any integer k can be expressed as k = xm + y for some modulus m. Think of it as dividing k by m, and getting the quotient x and the remainder y. So let k = B^C and m = p - 1 and tada.

If it helps you understand, an analogy is that you can turn any amount of minutes into "hours + minutes", when m = 60, then x = hours, y = remaining minutes.

And also, why should it be "obvious" when using Fermat's little theorem:

a^{(p - 1)} ≡ 1 (mod p) that A^{x ⋅ (p - 1)} = 1?

Say we have a^{(p - 1)} ≡ 1 (mod p). What happens if we multiply both sides by a^{(p - 1)}? We get:

    a^{(p - 1)} a^{(p - 1)} ≡ a^{(p - 1)} (mod p)
    a^{(p - 1) + (p - 1)} ≡ 1 (mod p)             (z^xz^y = z^x+y and the right hand side is equivalent to 1 as we've seen before)
    a^{2(p - 1)} ≡ 1 (mod p)

We can repeatedly multiply both sides by a^{(p - 1)} to get a^{3(p - 1)}, a^{4(p - 1)}, etc, so we say that for any integer x we have a^{x(p - 1)} ≡ 1 (mod p).