べき剰余を求める

RSA暗号プログラムでべき剰余を計算する必要がありましたが、べき剰余を計算するプログラムをまだ紹介していなかったのでここで。

#include <stdio.h>
#define N 28

int imod(int a, int n)
{
  int r;
  r = (a + n) % n;
  if(r < 0) r += n;
  return r;
}

int pow_mod(int a, int e, int n)
{
  int r = 1;
  a = imod(a, n);
  while(e > 0){
    if ((e & 1) == 1) r = imod(r*a, n); 
    e >>= 1;
    a = imod(a*a, n);
  }
  return r;
}

int main(void)
{
  int a, e;
  printf("input a:"); scanf("%d", &a);
  printf("input e:"); scanf("%d", &e);

  printf("%d^%d (mod %d) = %d\n"
          , a, e, N, pow_mod(a, e, N));

  return 0;
}

べき剰余を計算するのは関数pow_modです。