/*
* 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);
}
}