Raising numbers to a power of two
 

Are there any shortcuts for raising a number to a power of two (modulo a mersenne)?

Examples:

37^1024 (mod 127)

65^2048 (mod 8191)

I realize that the exponential operation using the binary method takes P iterations (for the power 2^P).

Example:

37^1024 = ((((((((((37^2)^2)^2)^2)^2)^2)^2)^2)^2)^2)

I just didn't know if there might be more efficient (easier/faster) ways to do it since the exponent is a special number.

Well I suppose it depends what you mean by 'mersenne'. If you mean 'mersenne prime' then yes, there is a shortcut.

Suppose we want to compute a^(2^b) mod (2^c-1), where 2^c-1 is prime and b>0. The group of units modulo 2^c-1 is cyclic of order 2^c-2, so it's enough to compute a^(2^b mod 2^c-2) mod (2^c-1).

But the binary representation of 2^b mod 2^c-2 is a single set bit and is equal to 2^(1 + (b-1) mod (c-1)),

i.e. the shortcut is to calculate a^(2^(1 + ((b-1) mod (c-1)))) mod (2^c-1).

However, if 2^c-1 is not prime then I can't see any (specific) speedups.

Dave

By Mersenne, I simply meant any number in the form of 2^P-1, be it a prime or composite (though primality not necessarily known at the evaluation time).

Hmm, it seems that your explaination works great for the case where the modulus is less than the exponent as in the example 37^1024 (mod 127). Thanks for the details, since I haven't seen that before.

But when the modulus is greater than the exponent, then there's no reduction that takes place.

65^2048 (mod 8191)

a=65, b=11, c=13

a^(2^(1 + ((b-1) mod (c-1)))) mod (2^c-1)
=65^(2^(1 + ((11-1) mod (13-1)))) mod (2^13-1)
=65^(2^(11 mod 12)) mod 8191
=65^2048 mod 8191