スポンサーサイト

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

Jacobi記号の計算のC言語による実装例

Crandall (著)、Pomerance (著)、和田秀男 (監訳) 『素数全書 計算からのアプローチ』 (朝倉書店) のアルゴリズム 2.3.5 (Legendre・Jacobi記号の計算) に書いてあるアルゴリズムに沿って C 言語のプログラムを書いてみた。

2012年4月19日更新 (プログラム修正)。

実装例

正しい計算結果を得るには、Jacobi 記号の定義および諸定理を適用する都合上、m は正の奇数である必要があります。

#include <stdio.h>

/* a を m で割った最小非負剰余 */
int mod( int a, int m )
{
  if ( m < 0 ) { m = -m; }
  if ( a < 0 ) { 
    a = m - ((-a) % m);
  }
  else { 
    a = a % m; 
  }

  return a;
}

/* Jacobi Symbol */
int jacobi_symbol( int a, int m )
{
  int t, temp;

  a = mod( a, m );  
  t = 1;
  while ( a != 0 ) {
    while ( a % 2 == 0 ) {
      a = a / 2;
      if ( m % 8 == 3 || m % 8 == 5 ) { t = -t; }
    }
    temp = a; a = m; m = temp;
    if ( a % 4 == 3 && m % 4 == 3 ) { t = -t; }
    a = a % m;
  }

  if ( m == 1 ) { return t; }
  return 0;
}

int main(void)
{
  printf( "(221/437) = %d\n", jacobi_symbol( 221, 437 ) );  /* => 1 */
  printf( "(439/1201) = %d\n", jacobi_symbol( 439, 1201 ) );  /* => -1 */

  return 0;
}

関連記事

Legendre記号、Jacobi記号、Kronecker指標を計算するRubyプログラム まとめ

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

プロフィール

よしいず

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

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

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

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

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

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