Results 1 to 3 of 3

Math Help - multiple exponent modular exponentiation

  1. #1
    Newbie
    Joined
    Jul 2012
    From
    around
    Posts
    1

    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.
    Last edited by exponentialtroubles; July 25th 2012 at 06:18 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor ebaines's Avatar
    Joined
    Jun 2008
    From
    Illinois
    Posts
    1,021
    Thanks
    280

    Re: multiple exponent modular exponentiation

    Quote Originally Posted by exponentialtroubles View Post
    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.
    Last edited by ebaines; July 25th 2012 at 11:31 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,286
    Thanks
    673

    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular exponentiation example
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 3rd 2012, 12:03 PM
  2. Modular Exponentiation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 13th 2010, 01:54 PM
  3. Modular Exponentiation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 13th 2010, 05:31 PM
  4. Modular exponentiation
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 8th 2009, 11:08 PM
  5. Modular Exponentiation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 27th 2008, 04:31 PM

Search Tags


/mathhelpforum @mathhelpforum