Raising numbers to a power of two

jfollas · 2004-07-02, 13:18

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.

dave_dm · 2004-07-02, 17:09

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

jfollas · 2004-07-02, 22:01

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).

jfollas · 2004-07-02, 22:26

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

2004-07-02, 13:18	#1
jfollas Jul 2004 1110₂ Posts	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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
TDP as power used?	CRGreathouse	Hardware	9	2016-02-06 18:46
prime power Sierpinski numbers	snorton	Prime Sierpinski Project	1	2015-03-25 03:07
The Chinese should be thanked for raising the bar...	chalsall	Science & Technology	4	2013-12-16 03:43
IBM Power 6	Unregistered	Information & Answers	7	2008-08-30 14:36
Now power consumption numbers using Prime95	Dresdenboy	Hardware	1	2004-11-23 18:29

2004-07-02, 17:09	#2
dave_dm May 2004 80₁₀ Posts	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

2004-07-02, 22:01	#3
jfollas Jul 2004 E₁₆ Posts	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).

2004-07-02, 22:26	#4
jfollas Jul 2004 2·7 Posts	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