/*
 * mod_power.c
 * This program reads three integer numbers and raises the first by the power
 * of the second modulo the third.
 */

#include <stdio.h>

/* Prototypes: */
int pow_mod (int a, int n, int m);

int main ()
{
  int    base;
  int    power;
  int    mod;

  /* Read the input numbers. */
  printf ("Please enter the base, the power and the modulo: ");
  scanf ("%d %d %d", &base, &power, &mod);

  if (base < 0 || power < 0 || mod < 0)
  {
    printf ("Invalid input.\n");
    return (1);
  }

  /* Compute and print the result. */
  printf ("(%d ^ %d) mod %d = %d\n", base, power, mod,
                                     pow_mod (base, power, mod));

  return (0);
}

/* ------------------------------------------------------------------------
 * Function: pow_mod
 * Purpose : Compute the power of a number using modular arithmetic.
 * Input   : a - The base.
 *           n - The power.
 *           m - The modulo. 
 * Returns : The value of (a ^ n) mod m.
 */
int pow_mod (int a, int n, int m)
{
  int       k;
  int       res;

  /* Stop if the power is zero: */
  if (n == 0)
    return (1);

  /* Act according to the parity of n. */
  if (n % 2 == 0)
  {
    /*                       n            2k             k
     * n = 2k is even, so: (a ) mod m = (a  ) mod m = ((a ) ^ 2) mod m
     */
    k = n / 2;
    res = pow_mod (a, k, m);
    
    return ((res * res) % m);
  }
  else
  {
    /*                         n            2k+1                 k
     * n = 2k+1 is even, so: (a ) mod m = (a    ) mod m = (a * (a ) ^ 2) mod m
     */
    k = n / 2;                /* We use integer arithmetic ... */
    res = pow_mod (a, k, m);
    
    return ((a * res * res) % m);
  }
}