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.

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On May 3, 3:52 pm, Peter_APIIT <PeterAP...@gmail.com> wrote:
> 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.

Integer product = 1;

Integer factor = *this;

for (unsigned int i = 0; i < exponent_extent_bits; ++i)
{
   if (exponent.buffer[i / WORD_LENGTH_BITS] & (1 << (i %
WORD_LENGTH_BITS)))
     product = product * factor % modulus;
   if (i < (exponent_extent_bits - 1))
     factor = factor.squared() % modulus;
}

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

Surely you know the answer. Think about what would happen if you did
it outside the loop, and the exponent is 1,000,000, and the modulus is
only 15.

> My current code.
[snipped]

If this is homework, your instructor will not be happy with the half-
C. You need to make full transition to C++ using a large integer
class. If this is professional work, same reason applies.

Big Integer arithmetic is an excellent example of where C++ far
outshines C in facility. You really should make full transition. You
need to have a class called "Integer", and overload the operators,
etc.

-Le Chaud Lapin-


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On May 4, 3:09 pm, Le Chaud Lapin <jaibudu...@gmail.com> wrote:
> On May 3, 3:52 pm, Peter_APIIT <PeterAP...@gmail.com> wrote:
>
>
>
> > 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.
>
> Integer product = 1;
>
> Integer factor = *this;
>
> for (unsigned int i = 0; i < exponent_extent_bits; ++i)
> {
>    if (exponent.buffer[i / WORD_LENGTH_BITS] & (1 << (i %
> WORD_LENGTH_BITS)))
>      product = product * factor % modulus;
>    if (i < (exponent_extent_bits - 1))
>      factor = factor.squared() % modulus;
>
> }

Why your approach put the in array ? Can you explain this algorithm ?

Thanks.


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On May 6, 2:31 am, Peter_APIIT <PeterAP...@gmail.com> wrote:
> > Integer product = 1;
>
> > Integer factor = *this;
>
> > for (unsigned int i = 0; i < exponent_extent_bits; ++i)
> > {
> >    if (exponent.buffer[i / WORD_LENGTH_BITS] & (1 << (i %
> > WORD_LENGTH_BITS)))
> >      product = product * factor % modulus;
> >    if (i < (exponent_extent_bits - 1))
> >      factor = factor.squared() % modulus;

I just took a look at your original code. I did not examine whether
you bit reversal in exponent is correct. But as you can see in my
code, I have a real Integer class, not ulong "hoping to be big enough
to be an Integer".  All I am doing is taking the bit that I need in
the loop directly from the left end of the bit array.

You can do the same.

But you probably realize now that the wrong answer will be yielded in
your code do to overflow. Ulong is not enough. Think about it.. 11 is
arguably a low number, and so is 12, but 11 ^ 13 = 3,138,428,376,721,
which is obvioulsy greater than 2 ^ 32.  I am sure you already thought
about overflow and asked yourself if it will be a problem, and the
answer is "yes".  You are effectively adding (mod 2^32) to every
single big integer operation you are performing, which would be fine
if the modulus really were 2^32, but it isn't. :)

You are going to have to go to a real Big Integer class, not unsigned
long int. There are many Big Integer libraries on the Internet.
Choose the one that is easiest for you. It does not matter which one
you pick, really, but a warning: do not spend too much time on
division if this is homework, because division, done right, is non-
trivial.

-Le Chaud Lapin-


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]