Shrinking down a^b mod m when b is huge and a is irrational?

[SeventhSigma]

Is there a good way to do this?

I am trying to figure out a good way to calculate a^b mod m, but the problem is that b is huge and a is irrational, and therefore I am getting inaccurate values because too much precision is required. I'm trying to find a smaller, "equivalent" ^b mod m to use so that b is not so huge and thus not as much precision would be needed in my a-term.

Is this doable?

 

[Citan Uzuki]

In general no, although if a is known to be algebraic you might be able to work something out. But if a is transcendental, then all values a^b mod m will be distinct as b varies over the natural numbers (proof: if a^(b_1) = a^(b_2) mod m for some b_1≠b_2, then for some integer k, a^(b_1) - a^(b_2) + km = 0, so a satisfies a nontrivial polynomial over the integers and so is algebraic).

By the way, can you tell us more about the problem you're working on? I can't think of why you would need to calculate powers of an irrational number modulo an integer.

 

[SeventhSigma]

It's for an online game/learning challenge, of sorts: http://tinyurl.com/3vldxfc
This problem in particular has been stumping me for a while and I'm trying to learn another way to tackle it.

 

[Citan Uzuki]

I see. Well in this case you DO know that a is algebraic, so you can compute a^987654321 in the polynomial ring Z[x]/(x^3-2^n·x^2+n) to get an exact representation of the number in terms of a and a^2. Then you'll only need to compute a and a^2 to the necessary precision to get the right integer part of $\lfloor a^{987654321} \rfloor$. Of course, the coefficients you'll get in your result will be huge, potentially over a billion digits, so you'll need access to a bignum library and to compute a and a^2 to ridiculous precision to get this method to work. Probably there's a special property of the polynomial we can exploit to simplify the computations further, but I'm not sure what.

 

[SeventhSigma]

Yeah but I don't think you need billions of digits of precision to make this calculation -- that's usually the "trick" in these types of problems. There's a longwinded, obvious brute-force method that isn't really feasible, and some quirky shortcut/insight that let's you bypass the brute-forcing. In this case it seems like there's some clever offset between the vast amount of precision needed in the a-term versus the huge number of digits a^b would have... some way to cancel the two out against each other and just use what little precision we have to somehow get the last few digits of a^b

 

[SeventhSigma]

I figured out that Euler's Identity can be used to simplify the exponent because:

a^b mod m = a^(b mod totient(m)) mod m

Which brought down my power to 27,654,321, but it's still much too large (I can't reduce the power any further here because the modulus of 100,000,000, the mod I'm using, is larger than my power).

I've read via extensive Googling that factoring the modulus and using the Chinese Remainder Theorem might be of service, but I'm still not quite sure how to do it.

 

[Citan Uzuki]

a^b mod m = a^(b mod totient(m)) mod m

That only works when a is an integer. It's not true in general -- consider (√2)^3 ≢ √2 mod 3, even though 3≡1 mod φ(3)=2.

 

[SeventhSigma]

Damn, you're right. I seriously feel like throwing myself out the window right now. Every single method I've tried on this problem has resulted in a dead end because my a-terms are non-integers.

EDIT: Well, technically, your case would be resolved this way:

(√2)^3 mod 3 = 2^(3/2) mod 3
phi(3) = 2
3/2 mod 2 = 3/2
So the answer doesn't change, it remains (√2)^3 mod 3 because the modulus (3) is larger than the exponent (1.5)

So in my case, I'd have to figure out how to squeeze the non-integer portion of the a-term out into the exponent

 

[I like Serena]

It's for an online game/learning challenge, of sorts: http://tinyurl.com/3vldxfc
This problem in particular has been stumping me for a while and I'm trying to learn another way to tackle it.

Just an observation.
(I was kind of hoping to reduce the expression using the polynomial.)

Your root "a" must satisfy a^3 - 4a^2 + 2=0.
Since 3 divides b, we have:

$a^b = (a^3)^{b/3} = (4a^2 - 2)^{b/3}$

Not sure though if this leads anywhere.