Modular exponentiation question

[Avocado]

I'm trying to solve this problem which basically wants you to calculate something like:

a^(b^(c^d)) mod m

The problem is that a, b, c and d can be as high as 1000, so I can't just calculate the value and then the module because the numbers are huge.

I know how to compute (a^b) mod m for any (a, b, m), but I don't know how to pass the value to the lower levels of the exponentiation so I can find the final result.

For example, if I know that x mod 10 = 4, how do i find (3^x) mod 10? I don't know the exact value of x, but I know how much iterations I've made to find the modulo.

Any ideas? Thanks.

[wooly_chicken]

well, you can compute the number of elements relatively prime to m (the order of (Z/mZ)^X). If this is n, then a^n=1 mod m.

This should allow you to reduce it to seeing what b^(c^d) mod n is. Repeat.

[wooly_chicken]

err . . that only works when (a,m)=1. Somethign similar probably works if this isn't true.

[tshort]

I don't immediately see any mathematical shortcuts which would improve the worst case scenario.

I assume this is more programming tricks.

[wooly_chicken]

[ QUOTE ]
I don't immediately see any mathematical shortcuts which would improve the worst case scenario.

I assume this is more programming tricks.

[/ QUOTE ]

What do you mean by worst case scenario?

You want to figure out how long it takes a^1, a^2, a^3 . . . to cycle (mod m). I don't think you want to brute force this. You probably want to solve the problem when m is a power of a prime first and then use the chinese remainder theorem. If you get this right, I don't see why you'd need any programming tricks.

[tshort]

[ QUOTE ]
[ QUOTE ]
I don't immediately see any mathematical shortcuts which would improve the worst case scenario.

I assume this is more programming tricks.

[/ QUOTE ]

What do you mean by worst case scenario?

You want to figure out how long it takes a^1, a^2, a^3 . . . to cycle (mod m). I don't think you want to brute force this. You probably want to solve the problem when m is a power of a prime first and then use the chinese remainder theorem. If you get this right, I don't see why you'd need any programming tricks.

[/ QUOTE ]

I didn't think too long, but you are def right brute force won't work.

Euler's theorem + Chinese remainder theorem seems like the way to approach it.

[bigpooch]

Euler's theorem
---------------

If m can be any positive integer >2, you want to use Euler's
theorem (I'll use ~ to denote the congruence relation):

x^phi(m) ~ 1 (mod m) where phi(m) is the Euler totient
function and x is RELATIVELY PRIME to m (e.g., if p is
prime, phi(p) = p-1). If x is not relatively prime to m,
then you may want to factor m into prime powers and use the
Chinese remainder theorem.

phi(m) is simply the number of integers between 0 and (m-1)
that are relatively prime to m; it's a multiplicative
function, so if a and b are coprime, phi(ab)=phi(a)phi(b).

Thus, x^y ~ x^z (mod m) when y~z (mod phi(m)).

Thus, if you are to find

a[1]^(a[2]^(a[3]^...(a[N-1]^a[N]))...) mod m,

you really want to know what modulus you are interested in.

For example, if you want to compute:

a^b^c^d (mod m), since the exponentiation is from right to
left, you can see that you should be concerned with the
modulus phi(phi(m)) when working out c^d since you are
concerned with modulus phi(m) when determining b^(c^d). Of
course, you need to check the condition that the "base" is
coprime with the modulus for each modulus.

For example, in the link, when computing 2^3^4^5 (mod 10),
you are interested in 3^(4^5) (mod phi(5)=4) since 10=5x2
and 2^z~0 (mod 2). 3 is relatively prime to 4, so you are
interested in 4^5 mod (phi(4)=2) which is the same as 0.
Then, 3^0~1 (mod 4) and so 2^(3^(4^5))~2^1~2 (mod 5) and
since 2^z is even, 2^3^4^5 ~ 2 (mod 10).


Computational ideas
-------------------

To compute (x^y) (mod z), obviously you only need to keep
results in mod z. Generally, you just compute x^2,(x^2)^2=
x^4,(x^4)^2=x^8, etc. since you have y in binary form (it's
a computer program) and make multiplications mod z. Keeping
the values of x^(2^n) would be especially helpful if certain
calculations are repeated often (e.g., you tend to use
moduli of the form 10^n and the other integers are often 2
or 3) so you might have some "tables" for the most common
calculations. Also, for the "nested" phi functions, you
may want to have those computed beforehand, especially for
moduli of the form 10^n or 5^n.

[m_the0ry]

Find the expression in terms of log base m. This can be done fairly easily with algebra and the definition of logs.

Once we know that the expression is equal to m^some power, you can subtract powers of m from that expression (for example if the expression equals m^15.125823 then we want to start with subtracting m^15) using the identity,

log(a - c) = log(a) + log(1-m^(log(c)-(log(a)))


Iterate this until the result of the subtraction is m^(x) where x is less than 1. antilog that expression for your answer/