C++ Square and Multiply Algorithm

square-and-multiply.cpp

/*
    Square and Multiply Algorithm
    By David J Pfeiffer
    The below function calculates x ^ y % p while avoiding overflow for large values of x and y
*/

int sam(int x, unsigned int y, unsigned int p)
{
    int result = 1;
    x = x % p;

    while (y > 0)
    {
      if (y % 2 == 1)
      {
        result = result * x % p;
      }

      y = y / 2;
      x = x * x % p;
    }

    return result;
}