# multiple exponent modular exponentiation

• Jul 25th 2012, 06:15 AM
exponentialtroubles
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.
• Jul 25th 2012, 11:20 AM
ebaines
Re: multiple exponent modular exponentiation
Quote:

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.
• Jul 25th 2012, 06:12 PM
Deveno
Re: multiple exponent modular exponentiation
to avoid confusion i will write [a] for a (mod n).

then [abcde] = [abcd]e

= [abc]de = [ab]dce = [a]bcde

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

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

however, it is generally NOT true, that:

[ag] = [a[g]].

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

then [212] = [4096] = 6 while:

[2[12]] = [22] = 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:

30476015 mod 17

= (3047 (mod 17))(6015 (mod 16)) (mod 17)

= 415 (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).