« public static void main(String[ ] args) | トップページ | 日経Linux2008年3月号 »

2008/02/12

べき剰余を求める

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です。

|

« public static void main(String[ ] args) | トップページ | 日経Linux2008年3月号 »

Algorithm」カテゴリの記事

C」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/222903/40099801

この記事へのトラックバック一覧です: べき剰余を求める:

« public static void main(String[ ] args) | トップページ | 日経Linux2008年3月号 »