%$OpenXM: OpenXM/doc/sci-semi2001/factor-resume.tex,v 1.4 2001/07/28 06:37:39 noro Exp $
\documentclass[12pt]{jarticle}
%\oddsidemargin -0.25in
%\evensidemargin -0.25in
\topmargin -0.5in
\oddsidemargin -0.1in
\evensidemargin -0.1in
\textwidth 6.5in
\textheight 9.5in
\IfFileExists{epsfig.sty}{\usepackage{epsfig}}{}
\usepackage{latexsym}

\title{多項式の因数分解 \\ --- コンピュータ上での代数計算 ---}
\author{野呂 正行 \\ 神戸大学理学部数学科}
\date{2001 年 7 月 29 日}
\begin{document}
\addtolength{\baselineskip}{5pt}
\maketitle
%\begin{center}
%Copyright~\copyright 2000 by Masayuki Noro. All rights reserved.
%\end{center}

\section{はじめに}

computer という言葉は, 文字通りに解釈すれば「計算」するためのものとい
う意味だろうが, 最近では email, ウェブなどデジタル情報通信のためのツー
ルとなってしまった感がある.  結果として, コンピュータを計算に使ってい
る人はごく少数であろう. しかし, コンピュータの能力は最近異様なまでに向
上しており, 計算に使わないのはもったいないと個人的には思う. 実際, 筆者
が本格的にプログラミングをはじめた 15 年程前には, いわゆるワークステー
ションクラスのマシンが一千万円ほどして, しかも計算能力は今の PC の数百
から千分の一程度しかなかったのである. 当時はその非力なマシンを大勢で共
同利用していたわけで, まさに隔世の感がある. 

本稿で述べるような計算は, いわゆる代数計算と呼ばれるもので, より一般的
な数値計算と比べると想像以上に計算パワー, 記憶容量を必要とする. しかし, 
いまや家庭にある普通の PC 上でもこのような計算は容易に実行できる. ここ
で述べることが, コンピュータの新しい使い道あるいは数学の有用性を見出す
ヒントとなれば幸いである.

\section{コンピュータについてのイロハ}

コンピュータの主要部として, プログラムを順に実行する CPU, プログラム, 
データを置く場所であるメモリ, および CPU が持つ特別なメモリであり, 演
算の対象となるレジスタがある. 命令というのは, 例えば次のようなものである. 

\begin{itemize}
\item 10 番地から 1 バイト読んで A レジスタに入れよ
\item A, B レジスタの値を足して C レジスタに入れよ
\item A レジスタの値が 0 なら 100 番地先に飛べ
\end{itemize}

このように CPU への命令の一つ一つは単純なものばかりである. 
扱える数の大きさは, レジスタの大きさで決まると言ってよい. たとえば, 
32 ビットレジスタというのは 0 または 1 を表す記憶装置が 32 個ある
レジスタであるが, このレジスタは 0 から $2^{32}-1$ までの整数しか
保持できないことになる. 

CPU の提供する機能だけでは, 数学に使うには不足であることが明らかである. 
たとえば $11111111111 \times 11111111111$ を計算した結果として
1332508849 という数字が返される場合がある. この結果は, 実は真の積
の値を $2^{32}$ で割った余りである. あるいは, 
電卓のように $1.234567 \times 10^{20}$ という値を返されるのも困る.
誤差が入ってしまうと, 数学的には意味のない結果となりかねない. 
すなわち, 数学に使うには, 扱える整数の大きさに制限があってはならない. 
このためには任意の大きさの整数を扱うためのプログラムを書けばよい. 
すなわち, メモリ上に, 例えば 32ビット整数を並べて, コンピュータに
「筆算」をさせればよい. この場合, 人間と異なるのは, 人間の場合, 
通常ひとけたというのは 0 から 9 までの数だが, コンピュータの場合
ひとけたが 0 以上 $2^{32}-1$ となる点である. 
例として, 整数の足し算は次のようになる. 

\begin{tabular}{ccccc}\\
& $2^{64}$ & $2^{32}$ & $1$ \\
& 5 & 4001257187 & 1914644777 & (= $3^{42}$) \\
+ &  & 2830677074 & 689956897 & (= $3^{40}$) \\ \hline
& 6 & 2536966965 & 2604601674 & (= $10\times 3^{40}$)\\
\end{tabular}\\

かけ算については, CPU が倍長演算を提供していない場合にはやや複雑になるが
あとは足し算と同様である. 割算は, 商の見積りのためにより複雑になるが, 
基本的には人間の行う筆算と同様と考えてよい. このようにして, 任意の大きさ
の整数の四則を行うプログラムを装備すれば, 整数あるいは有理数を数学的に
正確に扱うことができる. これを基礎として, 例えば一変数多項式は, 荒っぽく
言えば各次数の係数を並べたものとして表現できる. よって, 一変数多項式を
コンピュータ上で正確に扱えることになる. 以下では, この応用として, 
中学高校でおなじみの多項式の因数分解を, どうコンピュータに載せるか
について考える. 

\section{多項式の因数分解 --- 中学高校的方法}

多項式の整数の範囲内での因数分解について, おなじみの方法を挙げる. 

\begin{enumerate}
\item {眼力法}

$x^2+ax+b$ を因数分解する際に, 足して $a$, かけて $b$ になる数の組
を求める方法をここでは眼力法と呼ぶことにする. $b$ が小さい場合には
この方法が十分通用するが, 以下で見るように, $b$ が大きくなると
この方法はほとんど無力化する. また, 3 次以上の場合にこの方法を
適用するのは普通は無理であろう. 

\item {因数定理}

これは, 多項式 $f(x)$ に対し, $f(a)=0$ なら $f(x)$ が $x-a$ で
割り切れることを利用する方法である. これも眼力で $a$ を探すのは
難しいが, 探し方によっては有望である. 

\item {解の公式}

$x^2+ax+b=0$ の根が ${-b \pm \sqrt{a^2-4b}} \over 2$ と書けるから, 
$a^2-4b = t^2$ ($t$ : 整数) とかけるかどうか調べれば, もとの多項式
が因数分解できるかどうか分かる. 
\end{enumerate}

さて, 例えば $f(x) = x^2+11508x+28386587$ を因数分解する場合, どの方法
がよいだろうか. $f(x)$ は $f(x)=(x+3581)(x+7927)$ と分解されるが,
$28386587=3581\cdot 7927$ という素因数分解が「眼力」で分かる人は多分少
ないと思う. 実際, 多項式の因数分解に比べて, 整数の素因数分解のほうがは
るかに困難な問題である. また, 素因数分解が簡単でも, 素因数が多すぎると, 
組合せの数が多くなりすぎて, やはり困難になる. つまり, 眼力法は問題をか
えって難しくしていることになる. 
実は, もっとも安直そうに見える, 解の公式の利用がこの場合もっとも有望
である. というのも, 整数が, ある整数の 2 乗になっているかどうか調べるのは, 
素因数分解に比べてずっとやさしいからである. この問題の場合, 
$(a^2-4b)/4 = 4717584$ が $2172^2$ であることは, 手計算でも比較的容易
に分かる. 

多項式の次数が 3 次以下の場合, 整数の範囲内で分解できるなら一次の因子を
持つので, 根を探すうまい方法があればよい. これには, たとえば
中間値の定理
「$f(a) < 0$, $f(b) > 0$ なら $a$, $b$ の間に $f(c)=0$ なる $c$ がある.」
を使って根を探す方法である「二分法」あるいは接線を用いるニュートン法
がある (いずれも高校数学 C にある). 問題は整数根の有無なので, 
これらの方法により比較的容易に根が探せる. しかし, 多項式
の次数が 4 次以上の場合, 因子の次数がさまざまであるため, 根を探す方法
を適用するのは困難であろう. そこで, コンピュータに合った方法を探すこと
にする. ヒントとしては, 

\begin{itemize}
\item 「近似」をうまく使う
\item コンピュータは繰り返し, 試行錯誤が得意 (なにをやらせても文句を言わない)
\end{itemize}
という 2 点である. 前者は, 中間値の定理が実数における近似と
結び付いたように, 他のタイプの近似が使えないか, ということである. 
後者は, そのような近似を繰り返して目的の分解に近付いていこう, という
ことである. 

\section{$p$-進近似による多項式の因数分解}

これから述べる方法は, 因子の形 (次数)を仮定して, その係数を近似に
より求めていく方法である. この場合に指針となる原理は
「整数 $m$ が 0 $\Leftrightarrow$ $m$ はどんな整数でも割り切れる」
というものである. これを用いて, たとえば

\begin{enumerate}
\item 最初, $f(x)-g_1(x)h_1(x)$ の係数が整数 $p$ で割り切れるような $g_1$,
$h_1$ を見つける. 

\item $f(x)-g_k(x)h_k(x)$ の係数が $p^k$ で割り切れるように $g_k$, $h_k$ を
順次作っていく ($k=2,3,\ldots$) --- だんだん「精度」が上がる

\item $g_1$, $h_1$ が正解に対応していれば, 適当な $k$ のところでほんとに割り切れるだろう. 
\end{enumerate}
というタイプのアルゴリズムを構成する. 言いかえると次のようになる. 
以下, 簡単のため $f(x)$ およびその因子の係数は全て正であるとする. 
まず, $f(x)$ の各係数を $p$-進数で表し, 各 $p^k$ ごとにまとめて
$$f(x) = a_0(x)+p \cdot a_1(x)+p^2\cdot a_2(x)+\cdots$$
と「$p$ に関してべき級数展開」する. ( $a_i(x)$ の係数は 0 以上 $p-1$ 以下)
これに対して, 
$$g(x) = b_0(x)+p\cdot b_1(x)+p^2\cdot b_2(x)+\cdots$$
$$h(x) = c_0(x)+p\cdot c_1(x)+p^2\cdot c_2(x)+\cdots$$
($b_i$, $c_i$ の係数は 0 以上 $p-1$ 以下)
とおいて $f(x)-g(x)h(x)=0$ から $b_i$, $c_i$ を, 下から順に決めていく
のである. 

ここで記法を一つ用意しておく. $M$ を整数とするとき, $a \equiv b \bmod M$
とは, 
\begin{itemize}
\item $a$, $b$ が整数のとき, $a-b$ が $M$ で割り切れること

\item $a$, $b$ が整数係数多項式のとき, $a-b$ の各係数が $M$ で割り切れること
\end{itemize}
とする. また, $a$ を $b$ で割った余りも $a \bmod M$ と書くことにする. 

さて, 上のように $g(x)$, $h(x)$ の形を仮定すると
$$f-gh \equiv a_0-b_0c_0 \bmod p$$
だから, $f=gh$ なら $a_0 \equiv b_0c_0 \bmod p$ のはずである. よって, これを
満たす $b_0$, $c_0$ を求めるのが第一歩となる. 以下では, 
$$f(x) =x^4+17056x^3+72658809x^2+3504023212x+30603759869$$
の因数分解を例として説明する. $p=3$ とする (こうとると以下の計算がうまくいく)と

\noindent
$f(x)=(x^4+x^3+x+2)+
3^1(x)+
3^2(2x^3+x+2)+
3^3(x^3+x^2+2x+2)+
3^4(x^2+x+1)+
3^5(x^3)+
3^6(2x^3+x+2)+
3^7(x^3+x^2+x)+
3^8(2x^3+x^2+2x)+
3^9(x^2+2x+1)+
3^{11}(2x^2+x+1)+
3^{12}(x^2+2x+1)+
3^{13}(x+1)+
3^{14} \cdot 2+
3^{15}(2x^2+x+2)+
3^{16}(x^2+2)+
3^{17} \cdot 2+
3^{19} \cdot 2+
3^{20}(x+2)+
3^{21} \cdot 2$

$$a_0(x)=x^4+x^3+x+2$$
である. まず, 1 次因子があるかどうかを調べてみる. 
$$b_0(x) = x+q, c_0(x) = x^3+rx^2+sx+t$$ とおく. $a_0 \equiv b_0c_0 \bmod 3$
より\\

$\left\{
\parbox[c]{6in}{ 
$q+r \equiv 1 \bmod 3$ \\
$qr+s \equiv 0 \bmod 3$ \\
$qs+t \equiv 1 \bmod 3$ \\
$qt \equiv 2 \bmod 3$}\\
\right.$\\

これは $q,r,s,t$ に関する連立合同式だが, $q,r,s,t$ に 0,1,2 をどう入れ
ても満たされないことから 1 次因子がないことが分かる. ($f(0)$,
$f(1)$, $f(2)$ が 3 で割り切れないことからもすぐに分かる.)

つぎは, 2 次因子の存在を調べる. 
$$b_0(x) = x^2+qx+r, c_0(x) = x^2+sx+t$$ とおく. $a_0 \equiv b_0c_0 \bmod 3$
より\\

$\left\{
\parbox[c]{6in}{
$q+s \equiv 1 \bmod 3$ \\
$qs+r+t \equiv 0 \bmod 3$ \\
$qt+rs \equiv 1 \bmod 3$ \\
$tr \equiv 2 \bmod 3$}\\
\right.$\\

今度は, $$(q,r,s,t) = (0,1,1,2), (1,2,0,1)$$ という解が見つかる. これは

\centerline{$(b_0,c_0) = (x^2+1,x^2+x+2)$ または $(x^2+x+2,x^2+1)$}

\noindent
を意味するが, これらはペアとしては同じものである.
$b_0=x^2+1$, $c_0=x^2+x+2$ とすると確かに
$f \equiv b_0c_0 \bmod 3$ が成り立つ. 
もとの式に戻ると, 
$$gh \equiv (b_0+3b_1)(c_0+3c_1) \bmod 3^2$$ より
$$f-gh \equiv a_0-b_0c_0+3(a_1-(c_0b_1+b_0c_1)) \bmod 3^2$$
$a_0\equiv b_0c_0 \bmod 3$ より両辺を 3 で割ると
$$(f-gh)/3 \equiv (a_0-b_0c_0)/3+(a_1-(c_0b_1+b_0c_1)) \bmod 3$$さて, 
元々左辺が 0 になるように $g$, $h$ を決めたいのだから, 右辺 $\equiv 0
\bmod 3$ のはずである. よって
$b_1$, $c_1$ は
$$(a_0-b_0c_0)/3+(a_1-(c_0b_1+b_0c_1)) \equiv 0 \bmod 3$$
を満たす. ここで, $g$, $h$ の最高次項は $x^2$ としてよい(要証明)から,
補正項である $b_1$, $c_1$ は一次式としてよい. よって
$$b_1 = qx+r, c_1 = sx+t$$ とおける. すると $a_1 = x$ より
$$(a_0-b_0c_0)/3+(a_1-(c_0b_1+b_0c_1)) = -
(q+s)x^3-(q+r+t+1)x^2-(2q+r+s-1)x-(2r+t)$$
より\\

$\left\{
\parbox[c]{6in}{
$q+s \equiv 0 \bmod 3$ \\
$q+r+t+1 \equiv 0 \bmod 3$ \\
$2q+r+s-1 \equiv 0 \bmod 3$ \\
$2r+t \equiv 0 \bmod 3$}\\
\right.$\\

\noindent
今度は連立一次合同式で, 容易に解けて

\centerline{$(q,r,s,t) = (0,1,0,1)$ すなわち $b_1 = 1, c_1 = 1$}

\noindent
これで $$f \equiv (b_0+3b_1)(c_0+3c_1) \bmod 3^2$$ となる $b_1$, $c_1$
が求まったことになる. 次は $a_2$, $b_2$, $c_2$ までとって $\bmod 3^3$ で見と, 
$$f \equiv a_0+3a_1+3^2a_2 \equiv (b_0+3b_1+3^2b_2)(c_0+3c_1+3^2c_2) \bmod 3^3$$
より	
$$((a_0+3a_1)-(b_0+3b_1)(c_0+3c_1))+3^2(a_2-(c_0b_2+b_0c_2)) \equiv 0 \bmod 3^3$$
($3^3$ で割り切れる項は捨てた.) 先頭部分は $3^2$ で割り切れるので,
両辺を $3^2$ で割ると
$$((a_0+3a_1)-(b_0+3b_1)(c_0+3c_1))/3^2+(a_2-(c_0b_2+b_0c_2)) \equiv 0 \bmod 3$$
$b_2 = qx+r, c_2 = sx+t$ とおくと, 前と同様に $(q,r,s,t)$ の連立一次
合同式が得られる. 
以下同様に $b_i = qx+r, c_i = sx+t$ 
($i=3,4,\ldots$) とおいて $(q,r,s,t)$ の連立一次合同式を順次
解いていけば
$$f \equiv (b_0+\ldots+3^{k-1}b_{k-1})(c_0+\ldots+3^{k-1}c_{k-1\
}) \bmod 3^k$$
すなわち$f \equiv g_kh_k \bmod 3^k$ となる $g_k$, $h_k$ が決まる. 
\begin{table}[hbtp]
\label{gh}
\begin{center}
\begin{tabular} { c | c c }
$k$ & $g_k$ & $h_k$ \\ \hline
1&$x^2+1$&$x^2+x+2$\\ \hline
2&$x^2+4$&$x^2+x+5$\\ \hline
3&$x^2+18x+4$&$x^2+x+5$\\ \hline
4&$x^2+45x+4$&$x^2+x+59$\\ \hline
5&$x^2+45x+166$&$x^2+x+140$\\ \hline
6&$x^2+531x+409$&$x^2+487x+626$\\ \hline
7&$x^2+1260x+1867$&$x^2+487x+1355$\\ \hline
8&$x^2+1260x+4054$&$x^2+2674x+1355$\\ \hline
9&$x^2+7821x+10615$&$x^2+9235x+7916$\\ \hline
10&$x^2+7821x+30298$&$x^2+9235x+47282$\\ \hline
11&$x^2+7821x+89347$&$x^2+9235x+165380$\\ \hline
12&{$x^2+7821x+89347$}&{$x^2+9235x+342527$}\\ \hline
13&{$x^2+7821x+89347$}&{$x^2+9235x+342527$}\\ \hline
\end{tabular}
\caption{($g_k$, $h_k$)}
\end{center}
\end{table}
表 1 は, この操作を続けたときの, 各ステップにおける $g_k$, $h_k$ を示す. 
表で見ると, $k = 12$ から $k = 13$ で変化がないことが分かる. 実際に
$f-g_{13}h_{13}$ を計算してみると 0 であることが分かる. 
すなわち
$$f(x) = (x^2+7821x+89347)(x^2+9235x+342527)$$
これで因数分解が完了した. ここでは 「 $\bmod p^k$への持ち上げ」が
そのまま因子となったが, 実際には
\begin{itemize}
\item 負の係数を復元するための工夫
\item $k$ をどこまで上げればよいかという上限の計算
\end{itemize}
が必要となる. 

ここで紹介したアルゴリズムの各ステップで, $b_k$, $c_k$ の係数に関する
連立方程式 (合同式) が現れたが, $k>1$ では一次方程式であり解くのはやさ
しい. 問題は $k=1$ の場合である. この方程式を, 変数にあらゆる値を入れ
て解くというのは, コンピュータの能力を考慮してもあまりにも効率が低
い. そこで, $a_0 \equiv b_0c_0 \bmod p$ を満たす$b_0$, $c_0$ を求める
問題を視点を変えて見ることにする.

\section{有限体 $GF(p) = \{0,1,\cdots,p-1\}$}

$p$ が素数のとき, $GF(p) = \{0,1,\cdots,p-1\}$に, $+$, $-$, $\times$ 
を「結果を $p$ で 割った余り」で定義すると次が成り立つ. 
\begin{enumerate}
\item 加減乗算で閉じている. 

これは自明であろう. 

\item 0 以外の元で割算ができる.

これは言い替えると
「$a {\not \equiv} 0 \bmod p$ なら $ab \equiv 1 \bmod p$ なる $b$ がある」
ということである. 
「$a$, $p$ が互いに素のとき整数 $b$, $q$ が存在して $ab+pq=1$」
と書けば, 見たことがあるかもしれない. これは, ユークリッドの互除法の
副産物として得られる結果である. 
\end{enumerate}
すなわち, $GF(p)$ は体(タイ)をなす. 
元の個数が有限個 ($p$ 個)なので有限体とよぶ. さて, $a_0 \equiv f \bmod p$
を 体 $GF(p)$ に係数をもつ一変数多項式と見ると, $a_0 \equiv b_0c_0 \bmod p$
なる $b_0$, $c_0$ を求めることは, $GF(p)$ 係数多項式の因数分解を行うこと
に相当する. 実は, 有限体上の多項式の因数分解に関しては Berlekamp アルゴリズム, 
Cantor-Zassenhaus アルゴリズムといった大変効率のよいアルゴリズムが
考案されている. また, $k > 1$ についても, $k=1$ で得られた $b_0$, $c_0$
に, $GF(p)$ 上で多項式に対する互除法を適用して得た $v_0b_0+w_0c_0=1$ を
満たす多項式 $v_0$, $w_0$ を使って, $b_k$, $c_k$ が機械的に計算できる. 
以上により, 因数分解アルゴリズム (Zassenhaus アルゴリズム) は次のように
まとめることができる.

\begin{enumerate}
\item よい素数 $p$ を選んで $f \bmod p$ を因数分解

ここで「よい」というのは例えば次のようなことを意味する. 

\begin{itemize}
\item $f$ の最高次係数を割らない

$GF(p)$ 上で考えたときに次数が変わらないようにする. 

\item $GF(p)$ での因子が全て異なる

$k > 1$ で必要となる $v_0$, $w_0$ が存在するために必要な条件である. 

\end{itemize}

\item $f$ の因子の係数の上限を計算し, $p^k$ がそれより十分大きくなる
ように $k$ を決める. 

\item 次を繰り返し

\begin{enumerate}
\item $GF(p)$ 上の因子を二組に分ける. 

\item 各組の積を $g_1$, $h_1$ とする. 

\item $f \equiv g_kh_k \bmod p^k$ なる $g_k$, $h_k$ を作る

\item 係数の正負を調節して試し割り
\end{enumerate}
\end{enumerate}

ここでは, おおざっぱに手続きのみを述べたが, 数学的に正当化するためには
さまざまな数学的裏付けが必要となる. 最も根本的な問題として, 多項式の因
数分解 (有理数体上, 有限体上) が一意的にできるかどうかという問題がある. 
これは, 体の上での多項式の因数分解の一意性という一般論により保証される. 
また, 有限体上の因数分解アルゴリズム自身, そこで用いられている手法がと
ても興味深いが, その理解のためには代数学にある程度習熟している必要があ
る. さらに, $\bmod p$ から $\bmod p^k$ への持ち上げ (lifting と呼ぶ) 
は, Hensel の補題という重要かつ一般的な定理の特別な場合である. 以上
のように, 多項式の因数分解という比較的単純そうに見える操作も, コンピュー
タで実行させようと思うと, 計算パワーだけでは使いものにならず, 数学
をうまく使ったアルゴリズム設計が必要になることが分かる. 

\section{有限体の応用例 : 暗号}

前節で, 有限体という概念を紹介したが, ここでは有限体が実社会に応用され
ている例として, 暗号について述べる. 最初に述べたように, コンピュータは
現在, 通信手段として最も華々しく用いられている. 通信はネットワークを通
じて行われるが, ネットワークを通るデータを第三者が傍受する可能性がある. 
もっと言えば, ネットワーク上での通信は基本的に筒抜けと思ってよい. この
ような状況で, ウェブ上での買物にクレジットカードの番号などを気軽に入力
して大丈夫なのだろうか. 実は, これに答えるのが, 通信の暗号化である. 暗
号にはさまざまな方式があるが, 例えば次のような方法が実際に用いられてい
る.

\begin{enumerate}
\item 暗号化/復号化鍵を共有する.

ここで, 鍵というのはある大きさの整数と思ってよい. 

\item 送信側は鍵で暗号化し, 受信側は鍵で復号化する. 

鍵は一つで暗号化/復号化に使う. もちろん, 暗号化に使った鍵を持ってい
なければ復号できないような暗号方式を用いる. このような暗号は
共通鍵暗号と呼ばれる.
\end{enumerate}
ここで問題が一つある. 暗号化されていない, 筒抜けの通信路を使って
どのように鍵を共有するのだろうか. その方法の一つが次の Diffie-Hellman
鍵交換プロトコルである.

\begin{itemize}
\item {公開情報}

大きい素数 $p$, $0 < g < p$ なる整数 $g$

\item {A さんの仕事}

\begin{enumerate}
\item $0 < s_A < p$ なる整数 {$s_A$} (秘密) を作る. 
\item $w_A =$ {$g^{s_A} \bmod p$} を B さんに送る.
\item 受け取った $w_B$ から $s =$ {$w_B^{s_A} \bmod p$} を作る. 
\end{enumerate}

\item {B さんの仕事}

\begin{enumerate}
\item $0 < s_B < p$ なる整数 {$s_B$} (秘密) を作る.
\item $w_B =$ {$g^{s_B} \bmod p$} を A さんに送る.
\item 受け取った $w_A$ から $s =$ {$w_A^{s_B} \bmod p$} を作る. 
\end{enumerate}
\end{itemize}
この手順が A さん, B さん双方で行われると, A さん, B さんは共通の $s$ という
データを手に入れる. これは $w_B^{s_A} \equiv w_A^{s_B} \bmod p (\equiv g^{s_As_B} \bmod p)$ から分かる. 
あとは $s$ から共通の手順で鍵を作ればよい. ここで, $w_A$, $w_B$ は
暗号化されていないため, 他人が入手することもあり得る. しかし, $s_A$, $s_B$
さえバレなければ, 第三者が $s$ を作ることはできない. 実際, 
$g^{s_A} \bmod p$ から $s_A$ を逆算する問題は, 有限体の乗法群における
離散対数問題とよばれ, $p$ が大きいと計算が困難であると考えられている. 
これが, $w_A$, $w_B$ を暗号化する必要がない根拠となっている. 

なお, 手順中に現れる, $\overline{a^b} = a^b \bmod p$ の計算(べき乗剰余
演算) は, 例えば次のような手順で計算することで, $p$ 程度の大きさの数の
かけ算, 割算の繰り返しに帰着できる.

$\overline{a^{100}} = \overline{(\overline{a^{50}})^2}$,
$\overline{a^{50}} = \overline{(\overline{a^{25}})^2}$,
$\overline{a^{25}} = \overline{\overline{(\overline{a^{12}})^2} 
\times \overline{a}}$,
$\overline{a^{12}} = \overline{(\overline{a^{6}})^2}$,
$\overline{a^{6}} = \overline{(\overline{a^{3}})^2}$,
$\overline{a^{3}} = \overline{\overline{(\overline{a})^2} \times \overline{a}}$

ここで述べたもの以外にも, 有限体を応用した暗号はいろいろある. 代表的
なものを 2 つ挙げる. 
\begin{itemize}
\item RSA 暗号

大きな整数の素因数分解の難しさを利用

\item 楕円曲線暗号

有限体上で $y^2=x^3+ax+b$ の解 $P=(x,y)$ を考えると,
$k$ 倍算 $kP$ が定義できる.

$kP$ から $k$ を求める計算の難しさを利用
\end{itemize}
これらは実際に通信の安全性を保証するために用いられているが, 
コンピュータ上では結局, 整数の加減乗除およびべき乗剰余演算に
より実現されているのである. 

\section{まとめ}

本稿では, 整数係数の多項式の因数分解を, 有限体係数の多項式の因数分解(
$\bmod p$ での因数分解) から Hensel lifting とよばれる方法により$\bmod
p^k$ での因数分解に持ち上げて, 最終的に整数上の因子を得るという方法を
紹介した. そのアルゴリズムは, 初等的ではあるが数学をうまく使って効率よ
い多項式因数分解を可能にする. また, そこで現れた有限体という対象が, 単
に数学的に興味ある対象というだけでなく, さまざま暗号を実現するために用
いられていることも紹介した. コンパクトディスクの信頼性も, 有限体を用い
た符号である Reed-Solomon 符号で支えられていることを考えれば, 有限体が 
IT 社会を裏で支えているといっても過言ではないだろう. 数学を世の中の役
に立てよう, などと考えている数学者はあまりいそうにないし, また, そう
いうしがらみから自由であるところが数学の発展の源泉といえるのかもしれな
い. しかし, そのようにして得られた結果が, 後で想像もつかないところで応
用される場合もある. また, 一般に忌み嫌われる原因となる「難しさ」が, 暗
号の安全性の根拠となるというのもおもしろい話であり, 嫌われものに甘んじ
ながら, 実はこっそり世の中の役に立っているという, 数学の懐の深さを表し

ているという気がする.

\begin{thebibliography}{99}
\bibitem{KNUTH}
Knuth, D.E., The Art of Computer Programming, Vol. 2.
Seminumerical Algorithms, Third ed. Addison-Wesley (1998).

\bibitem{NORO}
野呂, 計算機代数. Rokko Lectures in Mathematics 9, 神戸大学理学部
数学教室 (2001).

\bibitem{ASIR}
野呂 他, 計算機代数システム Risa/Asir (1994-2001).

{\tt ftp://archives.cs.ehime-u.ac.jp/pub/asir2000/}
\end{thebibliography}

本稿で述べたことは, 主にコンピュータが誕生した後に考案された方法で, 文
献はそう多くない. \cite{KNUTH} は大きな整数の演算, 因数分解を含む一変
数多項式に関するアルゴリズムのハンドブック的な本である. 内容は膨大だが
記述は極めて正確である. \cite{NORO} はそのような本と比べられるものでは
ないが, 多変数多項式の因数分解および非線形連立代数方程式の求解について
も詳しく述べている. 他の文献については, これらの本の文献表を参照してほ
しい.  \cite{ASIR} はフリーな計算機代数システム(数式処理システム)で,
\cite{NORO} に書かれたアルゴリズムはほぼ実装されている. 実際にどの程度
使いものになるか試してみてほしい.\\

\noindent
{\large\bf 配布 CD について}
\begin{enumerate}
\item
Windows 版 Asir にはインストーラがありません. いきなり起動できます.
Asir を起動するには, CDROM 上の フォルダ {\tt asir} を開き,さらに {\tt
bin} フォルダを開き {\tt asirgui} アイコンをダブルクリックします.  マ
ニュアル({\tt index.html}), 入門書({\tt index-asir-book.html})なども 
CDROM にいれてあります.  Asir のホームページは, \\
{\tt http://www.math.kobe-u.ac.jp/Asir/asir.html} です. {\tt asirgui} は 
デスクトップへコピーすると動きません.  マイドキュメントへのコピーは(多
分)大丈夫です.  ただし {\tt asir} フォルダ全体をコピーする必要がありま
す.  ({\tt asirgui} は日本語のパス名があるとトラブルを起こす為.  デス
クトップは日本語のパス名を利用している.)

\item
Asir はマシン名が日本語の場合, 動作がおかしくなります.
自分のコンピュータのマシン名を調べるには, デスクトップの
ネットワークコンピュータアイコンをクリックして下さい.
LAN に接続されていない場合は, 1 台だけコンピュータが表示されますが,
その名前が自分のコンピュータの名前です.

\item
CDROM 上の {\tt povwin3} をダブルクリックすると, ray tracer povray の
インストールが始まります.  povray の日本語の説明書としては, アスキー出
版局の「POV-Ray ではじめるレイトレーシング」 小室日出樹著 
(ISBN4-7561-1831-3) があります. \\
{\tt http://hp.vector.co.jp/authors/VA000449/pov/} をみると povray について
のいろんな情報を得ることが可能です.

\item 
神戸大学数学教室の web page に置いてある, 曲面の画像集を収録してありま
す.\\
{\tt web-math-kobe-u} フォルダを開いたのち, {\tt index.html} をダ
ブルクリックして,表示されたページの Mathematical Diversion を開きます。
\end{enumerate}
\end{document}