How to implement such an algorithm?

Question

C++ / C#

It is required to implement the binary exponentiation algorithm

std::vector<bool> temp = toBinary(power);
  std::vector<long> result;
  long S = 1, c = base;

  for (auto i = 0; i < temp.size(); ++i)
  {
    if (temp[i] == 1)
    {
      S = (S * c) % mod;
      std::cout << "S = " << S << std::endl;
    }
    else
    {
      c = (c * c) % mod;
      std::cout << "c = " << c << std::endl;
    }
  }

I wrote this, and it does not work as it should. Tell me what needs to be fixed?

Answer 1

uint64_t mod_power(uint64_t a, uint64_t b, uint64_t n) {
  uint64_t bit = 0x8000000000000000ui64;
  uint64_t result = a % n;
  while (bit && (bit & b == 0))
    bit = bit >> 1;
  while ((bit = bit >> 1))
    result = (result * result * ((bit & b) ? a : 1)) % n;
  return result;
}

Answer 2

First, long is int32, so if your mod is greater than 2^15, it's better to use long long.
Secondly, the line

S = (S * c) % mod;

should be replaced with

c*=base;
c%=mod;
c*=c;
c%=mod;

(if you want to follow the algorithm), in addition, set the condition that temp[i] is not the last bit of the bit representation of the number - otherwise we will once again bring it to the square.
The following code works correctly:

long long bp(long long base, long long power)
{
  std::vector<bool> temp = toBinary(power);
  std::vector<long> result;
  long long c = 1;

  for (auto i = 0; i<temp.size(); i++)
  {
    if (temp[i] == 1)
    {
      c = (c*base)%mod;
    }
    if(i!=temp.size()-1)
        c*=c;
    c%=mod;
  }
  return c;
}

I did not understand the meaning of the S variable, if you explain, perhaps your code will be edited "softer" (it seems that I rewrote half of your code, sorry)
Generally speaking, the binary construction function in recursive form looks like this:

long long binpow(long long base, long long power)
{
    if(power==0)
        return 1;
    if(power%2)
        return (binpow(base, power-1)*base)%mod;
    long long tmp = binpow(base, power/2);
    return (tmp*tmp)%mod;
}

You might find it easier to write a non-recursive function with an understanding of recursive.