Left Right Binary Exponentiation

[Peter_APIIT]

Hello to all, i try to code the binary exponentiation algorithm but unfortunately it is not working as desire.

I decided to switch back to You could try using std::numeric_limits<int>::digits to determine the values and sizes or using CHAR_BIT.

My logic is define at below.

Look at most significant set bit(1) and discard it which follow by scanning from Left to right

If bit Is 1 then
base * result * result % modulus;
else
result * result % modulus;

My question is how to translate these to code.
Another question is i doubt whether the modulus step need to performed in each loop or outside the loop.

result = result % modulus at outside of loop or inside of loop at every step.

My current code.

Code:

ulong LeftRightExponentiation(ulong& base, 
				ulong& exponent, const ulong& modulus)
{
	
	ulong result(1);

	// Reverse exponent
 exponent = (((exponent & 0xaaaaaaaa) >> 1) | ((exponent & 0x55555555) << 1));
	exponent = (((exponent & 0xcccccccc) >> 2) | ((exponent & 0x33333333) << 2));
	exponent = (((exponent & 0xf0f0f0f0) >> 4) | ((exponent & 0x0f0f0f0f) << 4));
	exponent = (((exponent & 0xff00ff00) >> 8) | ((exponent & 0x00ff00ff) << 8));
	exponent = ((exponent >> 16) | (exponent << 16));

	while (exponent)
	{
		// Check Least Significant Bit after reverse
		if ((exponent & 1) == 1)
		{
			// Square and Multiply Base
			result = base * (result * result);
		}
		else
		{
			// Square only
			result = result * result ;
		}
		exponent >>= 1;
	}

	result = result % modulus;

	return result;
}

Thanks for your help.

[Peter_APIIT]

My logic is discard the first most significant set bit at left hand side.

Then continue in loop

while no more bit no process
If bit Is 1
base * result * result
else
result * result;

How to translate these to code ?

Thanks.

A billion thanks for your help.

[Peter_APIIT]

Any help please.

Thanks.

[BosByte]

Instead of reversing the bits in exponent and shifting to the right while checking the least-significant bit, you could use a left-shift en check the most-significant bit. Something like this:

while(exponent){
		result *= result;
		if (exponent & 0x80000000) result *= base;
		result %= modulus;
		exponent <<=1;
	}

[Peter_APIIT]

if (exponent & 0x80000000) equal in 0001(Binary) 1 in decimal

I think you are checking least significant bit.

Malaysia Boleh.
Please clarify.

I need to discard the most significant set bit first then scan from left to right.

Do you have similar approach ?

Thanks.

[BosByte]

... if 0x00000001 (1 in decimal) is the least siginificant bit, then 0x80000000 is the most significant bit... right?

[BosByte]

I need to discard the most significant set bit first then scan from left to right.

Well, your code will reverse the bits in exponent, and then scan it from right to left.. the code I posted above will simply scan it from left to right, so you don't have to reverse the bits first... the result should be the same..

[Peter_APIIT]

What is the logic behind your code since it loop 30 times ?
Can you explain it ?

I try it under debugging and the exponent value become unsigned and signed value and why ?

I need algorithm that loop only the number of bit set -1.
For example, 11001(25), i just need to loop four times after discard the first bit of most significant bit.

Thanks for your help and explanation.

[Peter_APIIT]

Since left to right binary exponentiation is faster than right to left but the implementation is difficult for left to right. Therefore, i need good algorithm.

Thanks.

[Peter_APIIT]

I looking for help.