Finding x in Modular Equations with Large Exponents

[coolul007]

I am wondering if there is a way to solve the following: (Chinese Remainder Theorem does not apply)

n == a mod(m)

m == b mod(r)

n == x mod(r), I need to know x, without dealing with a gigantic number(n),

I can find a and b, as I chose m to give me predictable results.

I appreciate any insight...

Sorry, for not including work so far, etc. Here is an example of what I am trying to do with manageable numbers:

5^(2)^13 = 5^8192 == 25 mod(5^13 -1), (always comes out 5^2)

5^13 - 1 == 614 mod(7927)

5^8192 == ? mod(7927) here is my dilemma. I know Power Residues will eventually crank out an answer, but my exponents are so large that it is prohibitive.

 

[dodo]

Hello,
any solution, if it exists, will be unique modulo lcm(m,r). Is that lcm too "gigantic" for your purposes?

Also, I'd try to think how many solutions are there using only the first two equations, since those already produce a value for n. (Hope this helps.)

Edit: Hmmm, more to the point: exactly what is fixed and what can be moved? It sounds like only m is taken as fixed. In that case, what is wrong with any r > m, b=m, and any n=a=x < m ?

 

[coolul007]

Hello,
any solution, if it exists, will be unique modulo lcm(m,r). Is that lcm too "gigantic" for your purposes?

Also, I'd try to think how many solutions are there using only the first two equations, since those already produce a value for n. (Hope this helps.)

Edit: Hmmm, more to the point: exactly what is fixed and what can be moved? It sounds like only m is taken as fixed. In that case, what is wrong with any r > m, b=m, and any n=a=x < m ?

r is fixed to be less than m, in fact r is a number less than m, I chose m because it has predictable results on n. The problem remains n == ? mod(r), knowing n,m,r as being fixed.

 

[dodo]

Ah. If I understand you correctly, your problem is just solving the last equation, not really a system of 3. Here are some ideas, but they depend on what else do you know about your numbers:

- Is Euler's theorem applicable?
- Does the base (in your example, 5) is coprime to the modulus? (Thus, has an inverse)

Where I'm going to, is that maybe your big exponentiation a^big can be reduced if you know that a^something == 1.

-- Edit:

All this not helping, there are ways of computing the exponent without too much hassle. For example, say the exponent is 11. (Could be much bigger as well.) In binary, this exponent is 11=8+2+1. So a^11 = a^8 * a^2 * a^1 . In practice, you begin with the base a, and square it on each iteration; whenever a bit in the exponent is one, you multiply that power of a into an accumulator (which began as 1). Notice that there are plenty of intermediate steps to reduce modulo m.

 

[coolul007]

My exponents are on the order of 2^9,876,543 not the real exponents, but size is right. It is always a power of 2. The base is 5. Thank you for the leads, I will investigate a^something == 1 mod(r).