/**
 * expmod-recursive.c
 *   A recursive, somewhat efficient implementation of expmod.
 */

// +---------+-------------------------------------------------------
// | Headers |
// +---------+

#include "expmod.h"

// +--------------------+--------------------------------------------
// | Exported Functions |
// +--------------------+

long
expmod (long x, long n, long m)
{
  if (0 == n)                               // x^0 = 1
    {
      return 1;
    }
  else if ((n % 2) == 0) // even
    { 
      long tmp = expmod (x, n/2, m);       // x^(2k) = x^k * x^k
      return (tmp * tmp) % m;
    }
  else 
    {
      long tmp = expmod (x, n-1, m);       // x^(k+1) = x^k * x
      return (x * tmp) % m;
    }
} // expmod