\chapter{はじめに} 計算機代数は, 計算機上で, 代数的計算を正確に行なうことを目標としている. 計算機が実用化されて以来, 計算機上での計算とは, 固定長, すなわち計算機 が提供するサイズの整数あるいは浮動小数を用いた計算を意味する場合がほと んどであった. 特に, 浮動小数を用いる, いわゆる数値計算の場合, 計算誤差 は避けられず, 一つのアルゴリズムに対して, その結果の誤差の解析は必須で あった. 実際, 通常の数値計算では誤差の累積が大き過ぎて, 実用には適さな いとされるアルゴリズムも存在する. また, 数値計算は, 代数的計算に限らず, 代数方程式, 微分方程式などの近似解の計算などに広く用いられているが, そ れらの場合における, 代数方程式, 微分方程式は, 多くの場合, その数学的構 造は重視されず, ある点における値を生成するブラックボックスとして用いら れる. このような方法は, 広い範囲の入力に対してなんらかの近似解を生成す ることができる反面, 得られた解から, もとの方程式が本来持っていた数学的 な性質を得ることは多くの場合困難である. 計算機代数は, 数学的対象を, 忠実に計算機上に表現し, 誤差のない計算を行 なうことにより, 数学的に明確な意味をもつ結果を得ることを主眼としている. 当然, 数値計算に比較して, 扱える対象は限られる. 今のところ, 整数, 有理数およびそれらを係数とする多項式, 有理式が主な対 象であるため, 計算機 $<$代数 $>$と呼ばれる. しかし, その及ぶ範囲は, 多 項式の因数分解を初めとして, 多項式イデアル論の応用としての代数幾何学を カバーするまでになり, イデアルの準素イデアル分解が構成的に可能となって いる. この分野における基本的なツールは, Buchberger により考案された \gr である. これと同等な概念は, Standard basis として, 広中により Buchberger 以前に考案されていたが, 構成的な生成アルゴリズムを Buchberger が与えたことにより, 以上のことが計算機上で可能となったわけ である. 以上のように, 計算機代数においては, 正確な計算ということが基本となって いる. 最も基本的な単位である整数も, 必要なだけの桁数をすべて表現でき る任意多倍長整数 (bignum) という形で表現されなければならない. 当然なが ら, 桁数が増えれば増えるほど, それらの間の演算にかかる時間は増える. 実 際, bignum の計算時間が, 全体の計算時間の主要な部分を占める場合もしば しば生ずる. よって, 計算機代数においては, 計算機が提供する整数演算の性 能が, 計算全体の効率を大きく左右する. 残念ながら, つい最近まで, 計算性能の向上は, いわゆる High Performace Computing のための浮動小数演算に対してのみ計られてきた. しかし, Pentium, SPARC などの CPU では 整数演算性能の向上も図られており, 計算機代数システムの性能もそれに 応じて飛躍的に向上してきた. さらに, 最近大きく注目されている暗号技術は, RSA 暗号, 楕円曲線暗号 など, bignum あるいはその上の多項式演算をベースとしているものが多く, 計算機代数で培われたさまざな手法がそのまま役立つケースも多い. 計算機代数では, 多項式, 有理式など, 木構造をもつ対象が数多く 用いられるため, 数の演算性能だけでなく, データ構造の表現方法, さまざま なアルゴリズムの効率の向上, あるいはメモリ管理などを深く考慮する必要が ある. 本講では, \begin{itemize} \item 整数, 多項式の表現および四則演算アルゴリズム \item 多項式 GCD, 終結式, 中国剰余定理 \item 多項式の因数分解, 有理関数の不定積分 \item グレブナ基底, 代数方程式の求解, イデアルの準素分解 \end{itemize} について述べる. ここで述べられるアルゴリズムのほとんどは, 筆者らが開発, 配布中の計算機代数システム Risa/Asir \cite{NS} 上に実装され, 用いられている. \begin{nt} \begin{tabbing} \end{tabbing} \begin{description} \item[$\Z$] 有理整数環 \item[$\N$] 非負整数全体 \item[$\Q$] 有理数体 \item[$\C$] 複素数 \item[$|F|$] $F$ が数のとき絶対値, $F$ が集合のとき元の個数 (濃度) \end{description} \end{nt} \chapter{準備} 本章では, 以下で述べるさまざまなアルゴリズムを理解し, 計算機上に実装 するために必要なことがらについて説明する. \section{CPU の構造および動作} どのような言語でアルゴリズムが記述されるにせよ, 最終的には そのアルゴリズムは CPU 固有の命令として実行される. ここでは, CPU の基本的な構造, 動作について解説する. \subsection{CPU についてのあらまし} CPU に対する命令は, 32bit あるいは 64bit というある決まった大きさの bit 列で表現されている. CPU は, メモリ中に置かれた一連の命令列を順 に読み出し, 対応する操作を実行する. CPU は, レジスタと呼ばれる 特殊なメモリを持っている. レジスタは, CPU の構成に応じて 32bit あるいは 64 bit という大きさを持つ. その本数は通常数本から数十本程度と少ないが, 主記憶と比較して高速に読み書きでき, CPU のデータ操作の対象となる. CPU が行う基本操作には, 次のようなものがある. \begin{itemize} \item メモリに対する命令 メモリからレジスタへのデータの読み込み, レジスタからメモリへの データの書き出しを行う. \item 演算命令 幾つかのレジスタに置かれたデータを用いて種々の演算を行う. 演算命令には, 整数演算命令, 浮動小数演算命令などがある. \item 分岐命令 レジスタの値をテストして, その結果に応じてプログラム中の指定された 場所にジャンプする. \end{itemize} \subsection{整数演算命令} \label{cpuint} 計算機代数においては, 誤差のない演算を実現するため整数演算を多用する. ここでは, 整数演算命令について簡単に解説する. レジスタの bit 長 $n$ に対し $2^n$ を $B$ と書く. レジスタ上のデータ は, 0 以上 $B-1$ 以下の非負整数を表すことができる. すなわち, $a_i$ を 0 または 1 とすると, bit 列 $(a_{n-1}a_{n-2}\cdots a_1a_0)$は $$a=\sum_{i=0}^{n-1}a_i2^i$$ なる整数 $a$ を表す (二進数). 一方で, 負数は 2 の 補数表示と呼ばれる方法で, やはり $n$ bit のデータで表す. この場合 bit 列 $(a_{n-1}a_{n-2}\cdots a_1a_0)$ は $$a=-a_{n-1}2^{n-1}+\sum_{i=0}^{n-2}a_i2^i$$ なる整数 $a$ を表す. 例え ば, $-1$ は $(11\cdots 1)$ なる bit 列で表される. この方法によれば, $n$ bit のデータで $-B/2 \le a \le B/2-1$ なる整数を表すことができ る. 注意すべき点は, 加減乗算を法 $B$ で行う場合, どちらで解釈しても結果は 同一となることである. これは, 上記二つの表現の違いが 法 $B$ での代表元 の取り方の違いであることからわかる. 以下で, $r = a \bmod B$ は $0\le r < B$ なる剰余を表す. 通常, CPU には次のような整数演算命令が用 意されている. \begin{itemize} \item 加算 $(a+b) \bmod B$ \item 減算 $(a-b) \bmod B$ \item 比較 if $a > b$ then 1 else 0 \item 左シフト $a$ の $k$ bit 左シフト $\bmod B$ \item 右シフト $a$ の $k$ bit 右シフト (右 $k$ bit は捨てられる) \end{itemize} シフト演算は, 論理演算に用いられるだけでなく, 整数の $2^k$ 倍, あるいは $2^k$ で割った剰余の計算に用いられる. これら以外に, CPU によっては次の 演算が用意されている場合がある. \begin{itemize} \item 乗算 $(a\times b) \bmod B$ \item 倍精度乗算 $(a\times b) \bmod B^2$ \item 除算 $a = qd+r$ なる $q$, $r$ ($0\le r < d$) \item 倍精度除算 $aB+b = qd+r$ なる $q$, $r$ ($0\le r < d$) \end{itemize} これらの基本操作を用いて, 次節で述べる, 多倍長整数の四則演算が実現 される. \section{C 言語について} 本講では, アルゴリズムおよびデータ構造の計算機上での実装例を C 言語により示す. ここでは, C 言語の文法に関して, ごく基本的 なことについて解説する. 詳細は, \cite{KR} などを参照されたい. \subsection{変数} 変数とはデータを格納しておく場所である. データの種類には整数, 浮動小数 をはじめとしてさまざまなもの (型) がある. 変数を使用するためには, 型お よび名前を宣言しなければならない. 例えば次は, {\tt a}, {\tt b}, {\tt xyz} という名前の符号つき整数型変数, および {\tt p}, {\tt q}という名前 の符号なし整数型変数の宣言である. 整数型変数のサイズが 32bit の場合, {\tt int} 型の変数は $-2^{31} \le x \le 2^{31}-1$, {\tt unsigned int} 型の変数は$0 \le x \le 2^{32}-1$ なる整数 $x$ を表現することができる. \begin{verbatim} int a,b,xyz; unsigned int p,q; \end{verbatim} \subsection{式} 変数および定数に対する一連の四則演算, シフト演算などをまとめて一つの式 として記述することができる. 加, 減, 乗はそれぞれ {\tt +}, {\tt -}, {\tt *} で表す. {\tt /} は除算における商 (整数部分), {\tt \%} は剰余を 表す. 式の中で用いることができる演算子には, 他に, {\tt <<} (左シフト), {\tt >>} (右シフト), {\tt |} (bit ごとの or), {\tt \&} (bit ごとの and), \verb+^+ (bit ごとの exclusive or) などがある. また, {\tt <}, {\tt <=}, {\tt >}, {\tt >=}, {\tt ==} (等しい), {\tt !=}(等しくない)なども, 正しければ 1, そうでなければ 0 という値を返す 2 項演算子として用いるこ とができる. 符号なし整数に対する加減乗算, 左シフト演算は, 整数型のサ イズを $n$ bit とするとき, 法 $2^n$ で計算される. 例えば, 整数型が 32bit のとき, \begin{verbatim} unsigned int a,r; a = 1<<31; r = a+a; \end{verbatim} を実行すると {\tt r} は 0 となる. \subsection{文} 文は C 言語の実行単位である. 文には, 式にセミコロン {\tt;} を付けた 単文の他に, 幾つかの文を \verb+{+, \verb+}+ で括った複文, {\tt if} 文, {\tt for} 文, {\tt while} 文, {\tt switch} 文などの制御を伴う 文などがある. 次の例は, 小さな {\tt n} に対して階乗を計算する文である. \begin{verbatim} unsigned int f; for ( f = 1; n >= 1; n-- ) f *= n; \end{verbatim} ここで, {\tt n--} は {\tt n = n-1}, {\tt f *= n} は {\tt f = f*n} をそ れぞれ意味する. この文は, 整数型が 32bit の場合, {\tt n} が 12 以下で のみ正しい値を与える. これは, 13 以上では結果が $2^{32}$ 以上となるためで あり, このような場合にも正しい結果を得るためには, 次節で述べるような 任意多倍長整数の表現およびそれに対するアルゴリズムが必要となる. \subsection{関数} C 言語においては, プログラムは関数として記述される. 関数は,引数 (入力) に対する操作をいくつかの文により記述し, 必要があれば結果を返す, という 操作をまとめたものである. 先に述べた階乗計算を関数にすると次のようになる. \begin{verbatim} unsigned int factorial(unsigned int n) { unsigned int f; for ( f = 1; n >= 1; n-- ) f *= n; return f; } \end{verbatim} この例では, 符号なし整数 {\tt n} を受け取り, その階乗を符号なし整数として 返す {\tt factorial} という関数が宣言されている. \subsection{配列, ポインタ} 任意多倍長整数は, メモリ上の十分な長さの連続領域として表現される. このような 領域は, C 言語では配列として表現される. \begin{verbatim} unsigned int a[10]; \end{verbatim} これは, 長さ 10 の符号なし整数配列 {\tt a} を宣言している. 配列の各要 素は, {\tt a[0]}, $\cdots$, {\tt a[9]} により得られる. (添字が 0 から 始まることに注意.) 次のプログラムは, 長さ 10 の配列の {\tt i} 番目の 要素に {\tt i} を代入する. \begin{verbatim} unsigned int a[10]; int i; for ( i = 0; i < 10; i++ ) a[i] = i; \end{verbatim} このプログラムは次のようにも書ける. \begin{verbatim} unsigned int a[10]; int i; unsigned int *p; for ( i = 0, p = a; i < 10; i++, p++ ) *p = i; \end{verbatim} {\tt p} はポインタと呼ばれる型の変数である. ポインタは, メモリのアドレス を抽象化したものである. この例の場合には, {\tt p = a} により 最初 {\tt p} は配列 {\tt a} の先頭を指している. そして, {\tt i} が 1 増えるたびに, {\tt p} の指す位置も, 配列中で 1 要素ずつ先を指すように 変化していく. すなわち, {\tt p++} による {\tt p} のアドレスとしての 変化量は {\tt unsigned int *p} なる宣言により規定されるのである. また, {\tt *p = i} は, {\tt p} の指す領域の内容を {\tt i} という値 に書き換えることを意味する. ポインタを導入する必要性にはさまざまなものがある. ここでは次の 3 つについて説明する. \begin{itemize} \item 動的なメモリ割り当て 我々の演算対象である整数は, 計算の過程でいくらでも大きな値となっていく 可能性がある. そのため, 例えば加算を行う関数は, 任意の大きさの引数に対 して, 結果を保持するだけの領域を確保してそこに結果を書くという形が自然 である. このとき, 記憶割り当てルーチンが返す値は, メモリ中のある領域の 先頭アドレスであり, 受け取る側は必然的にポインタとして扱う必要がある. \item 木構造の表現 多項式は, 後に述べるように木構造により表現される. その名の通り, 木は根 から枝わかれしながらつながるデータを表現する. これは, メモリ上では, 他 の領域を指すポインタを保持するデータ構造により表現するのが自然である. \item 関数呼び出し側の変数の書き換え C 言語では, 関数呼び出しは値による呼び出し (call by value) と呼ばれる 方法で行われる. すなわち, 呼び出し側の変数を, 関数呼び出しの引数として 渡しても, 呼び出された関数にはその値のみが渡されるため, 呼び出された関 数は, その変数の中身を書き換えることができない. このような場合に, 引数として変数を指すポインタを与えることにより, その変数の中身を書き換える ことが可能になる. 変数 {\tt a} に対し, {\tt a} を指すポインタの値は {\tt \&a} で得られる. {\tt \&} と {\tt *} は互いに逆の操作となっている. \end{itemize} \subsection{構造体} 例えば多倍長整数を計算機上で表現する場合, 各桁を表す整数配列および符号, 桁数 の情報は最低限必要である. これらはそれぞれ個別の変数に割り当てることも可能 であるが, 一つの対象が複数の変数に別れて保持されるのは, その取扱いを 複雑にし, またプログラムの可読性の点からも好ましくない. このような 場合に, 複数の要素を一つにまとめた構造体を用いることができる. 例えば, 整数は次のような構造体で表すことができる. \begin{verbatim} struct Integer { int n; /* 桁数 = |n|; n の符号がこの整数の符号 */ unsigned int *digits; /* 各桁を表す配列へのポインタ */ }; \end{verbatim} もちろん, ポインタ {\tt digits} は長さ {\tt |n|} 以上の符号なし 整数配列を指していなければならない.