Thread: multiple exponent modular exponentiation

I am implementing a cryptographic accumulator and I need to obtain the value a ^ b ^ c ^ d ^ e mod f where a b c d and e are very large numbers. It is written A^bcde mod f with the bcde above the A as in normal exponentiation. I am not sure how to do this with multiple exponents and I can not find much to clarify it for me. I imagine it must not be asking me for a ** b ** c ** d ** e mod f because that would never finish computing due to the very large (over 1000 bits each) size of the variables. I have access to a method that does modular exponentiation but it only allows one exponent. The only way I can imagine it making sense is if it is asking for ((((a ** b) mod f) ** c) mod f) etc because any other way seems like it would take too much processing time and memory. Can anyone clear up for me what exactly I am suppoused to do, and maybe point me in the right direction?

disclaimer: I know I should not rely on my own cryptography especially if I don't know how to do multi exponent modular exponentiation, however I do not plan to rely on what I am implementing until and unless people who know more about crypto than I do look over it and tell me I did a good enough job , and I am mostly just doing this fun.

Originally Posted by exponentialtroubles

I imagine it must not be asking me for a ** b ** c ** d ** e mod f because that would never finish computing due to the very large (over 1000 bits each) size of the variables.

Indeed a^b^c^d^e = (((a^b)^c)^d)^e is the same as a^(bcde). To prove that it works consider an example: suppose a=2, b= 2, c=3, d= 1, and e = 4. Then a^b^c^d^e = (((2^2)^3)^1)^4 = ((4^3)^1)^4 = (64^1)^4 = 64^4 = 16777216, which is the same as 2^(2x3x1x4) = 2^24

So you can multiply b x c x d x e to get a big number (call it g), and what you're trying to find is a^g mod f.

But I do believe it's true that a^(bcde) mod f is the same as (((a^b mod f)^c mod f)^d mod f)^e mod f. I don't have a proof, but it seems to work.

to avoid confusion i will write [a] for a (mod n).

then [a^bcde] = [a^bcd]^e

= [a^bc]^de = [a^b]^dce = [a]^bcde

this is because [a]*[b] = [ab], so when a = b, by induction we have: [a]^k = [a^k].

(that is, you can always reduce the base mod n, not the exponent).

however, it is generally NOT true, that:

[a^g] = [a^[g]].

for example, let the modulus be 10, and let a = 2, and g = 12.

then [2¹²] = [4096] = 6 while:

[2^[12]] = [2²] = 4

if it so happens that the base and the modulus are co-prime, then we can reduce the base (mod n), and the exponent (mod φ(n), where φ is the euler totient function).

for example:

3047⁶⁰¹⁵ mod 17

= (3047 (mod 17))^{(6015 (mod 16))} (mod 17)

= 4¹⁵ (mod 17)

= 13 (mod 17)

so primes make good things to reduce by, composite numbers, not so much (but in some cases, we can still make it work).