//
// Szybkie Potegowanie modulo
//
// www.algorytm.org
// (c)2006 Tomasz Lubinski
//

#include "stdio.h"
#include "stdlib.h"

// calculates a^b mod m
int power_modulo_fast(int a, int b, int m)
{
   int i;
   int result = 1;
   long int x = a%m;

   for (i=1; i<=b; i<<=1)
   {
      x %= m;
      if ((b&i) != 0)
      {
         result *= x;
         result %= m;
      }
      x *= x;
   }

   return result;
}



int main(void)
{
   //9688563^45896 mod 71 = 30
   printf("9688563^458926 mod 71 = %d\n", power_modulo_fast(9688563, 458926, 71));

   //12^53 mod 7 = 3
   printf("12^53 mod 7 = %d\n", power_modulo_fast(12, 53, 7));

   return 0;
}