スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

法mに関する逆元を計算するCプログラムの例

互いに素な整数 a, m が与えられたとき、a * x = 1 mod m を満たす整数 x を計算する C プログラムの例。

拡張 Euclid 互除法によるプログラム

拡張 Euclid 互除法は、最大公約数 d と、方程式 a * x + m * y = d の整数解 (x, y) を同時に求めるアルゴリズムです。d = 1 をあらかじめ仮定すれば、任意の整数解 (x, y) に対して a * x = 1 mod m が成り立ちます。

#include <stdio.h>

/* a^{-1} mod m */
int inv_mod( int a, int m )
{
  int b, x, u, q, abs_m, tmp; 

  abs_m = ( m < 0 ) ? -m : m;
  b = m; x = 1; u = 0; 
  while ( b > 0 ) {
    q = a / b; 
    tmp = u; u = x - q * u; x = tmp;
    tmp = b; b = a - q * b; a = tmp;
  }

  return ( x < 0 ) ? abs_m + x : x;
}

int main(void)
{
  int a, m, x;

  a = 19; m = 41; 
  x = inv_mod( a, m );

  printf( "%d * x = 1 mod %d の整数解: x = %d\n", a, m, x );

  return 0;
}

法 m についての逆元を返す関数 inv_mod は、本来の拡張 Euclid 互除法のプログラムから、y を計算する部分と、a, m の最大公約数を返す部分を省いたものになっています。

実行結果:

19 * x = 1 mod 41 の整数解: x = 13

Euler の定理に基づく方法

Euler の定理とは、「m を正の整数、a を m と互いに素な整数とするとき、a^{φ(m)} = 1 mod m が成り立つ」という主張です。ここで、φ(m) は Euler の関数です。このとき、a^{φ(m)-1} は方程式 a * x = 1 mod m の整数解です。

#include <stdio.h>

/* a^n mod m */
int power_mod( int a, unsigned n, unsigned m )
{
  int r = 1;

  a %= m; 
  while ( n > 0 ) {
    if ( n % 2 == 1 ) { r *= a; r %= m; }
    a *= a; a %= m;
    n /= 2;
  }

  return r;
}

/* Euler の関数 */
unsigned phi( unsigned n )
{
  unsigned res, p;

  res = n;
  if ( n % 2 == 0 ) {
    res /= 2;
    do { n /= 2; } while( n % 2 == 0 );
  }
  p = 3;
  while ( p <= n / p ) {
    if ( n % p == 0 ) {
      res = res / p * ( p - 1 );
      do { n /= p; } while( n % p == 0 ); 
    }
    p += 2;
  }
  if ( n > 1 ) { res = res / n * (n - 1); }

  return res;
}

/* a^{-1} mod m */
int inv_mod( int a, int m )
{
  unsigned abs_m = m < 0 ? -m : m;

  return power_mod( a, phi(abs_m) - 1, abs_m );
}

main 関数および実行結果は、拡張 Euclid 互除法によるプログラムと同じです。

関連記事

拡張Euclid互除法のC言語によるプログラム例
Eulerの関数を計算するCプログラムの例

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。