虚2次体の類数を計算するプログラムの例

虚2次体の類数を、簡約2次形式を数えることによって計算するプログラムの例。

C言語によるプログラム例

/* 
  判別式が D (<0) であるような虚2次体の類数は、
  判別式 D をもつ整係数2元2次形式
  ax^2 + bxy + cy^2 (a > 0)
  を対等関係で類別したときの類数に一致する。
  その類数は、判別式 D をもつ簡約2次形式の個数に等しい。

  2次形式が簡約(reduced)であるための必要十分条件:
  -a < b <= a < c または 0 <= b <= a = c 
*/

#include <stdio.h>
#include <math.h>    /* sqrt() */
#include <limits.h>  /* ULONG_MAX */

#define BASE 10  /* 基数(10進数) */

void usage(char *command) {
  printf("usage: %s <absolute value of " \
    "a discriminant up to %lu>\n", command, ULONG_MAX);   
}

int main(int argc, char* argv[]) 
{
  unsigned long int a, b, c, ac, sqrt_ac, 
    neg_disc, clNum, bBound;
  char *p;

  if (argc > 1) {
    /* neg_disc = -D */
    neg_disc = strtoul(argv[1], &p, BASE);
    if (p == argv[1] || (*p != '\0' && *p != '\n')) {
      usage(argv[0]);
      return 1;
    }
  }
  else {
    usage(argv[0]);
    return 0;
  }

  /* 類数 */
  clNum = 0;

  /* 係数 b の上限 */
  bBound = (unsigned long int) sqrt(neg_disc / 3.0);

  b = neg_disc % 2;  /* D = 0, 1 mod 4 に従って b = 0, 1 から開始 */
  while (b <= bBound) {
    /* ac = (b * b + neg_disc) / 4; 
       桁あふれ防止のため、割り算を先に行う */
    if (neg_disc % 2 == 0)  /* D = 0 mod 4 */
      ac = (b / 2) * (b / 2) + (neg_disc / 4);
    else  /* D = 1 mod 4 */
      ac = ((b + 1) / 2) * ((b - 1) / 2) + ((neg_disc - 3) / 4) + 1;
    sqrt_ac = (unsigned long int) sqrt(ac);
    a = (b == 0) ? 1 : b;  /* b <= a && 0 <= b && 0 < a */
    while (a <= sqrt_ac) {  
      if (ac % a == 0) {
        c = ac / a;
        /* 簡約の条件:-a < b <= a < c || 0 <= b <= a = c */
        if (b == 0) {
          clNum += 1;
          printf("(a, b, c) = (%lu, %lu, %lu)\n", a, b, c);
        }
        else if (a < c) {
          if(b < a) {  /*  => -a < -b */
            clNum += 2;
            printf("(a, b, c) = (%lu, %lu, %lu)\n", a, b, c);
            printf("(a, b, c) = (%lu, -%lu, %lu)\n", a, b, c);
          }
          else if (b == a) {
            clNum += 1;
            printf("(a, b, c) = (%lu, %lu, %lu)\n", a, b, c);
          }
        }
        else {  /* a == c && b <= a */
          printf("(a, b, c) = (%lu, %lu, %lu)\n", a, b, c);
          clNum += 1;
        }
      }
      a += 1;
    }
    b += 2;
  }
  printf("discriminant = -%lu\n", neg_disc);
  printf("class number = %lu\n", clNum);

  return 0;
}

実行例

プログラムを実行するとき、第1引数に判別式の絶対値を指定します。

なお、m を square-free な整数とするとき、2次体 Q(√m) の判別式 D は以下のとおり。

m = 1 mod 4 のとき, D = m. 
m = 2, 3 mod 4 のとき, D = 4m. 

例えば、m = -5 のとき、D = -20 です。このとき、プログラムの実行結果は以下の通りです:

(a, b, c) = (1, 0, 5)
(a, b, c) = (2, 2, 3)
discriminant = -20
class number = 2

参考文献

  • H. Cohen: A course in computational algebraic number theory, GTM 138, Springer, 1993, Section 5.3.

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

プロフィール

よしいず

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

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

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

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

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

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示