% $OpenXM: OpenXM/doc/sci-semi2001/factorb.tex,v 1.3 2001/07/24 09:35:54 noro Exp $

\Large
\parskip 0pt

\begin{slide}{}
\fbox{\sc 1. はじめに}

computer = compute するためのもの

compute = {\ec 計算}する

最近では {\ec デジタル情報通信} の手段となってしまった

$\Rightarrow$ 「計算」に使っている人はごく少数

{\bf 例} : email, ウェブ {\eec 「インターネットする」}

しかし, 計算機の能力は異様に向上


{\ec 計算に使わないのはもったいない}(と思う)
\end{slide}

\begin{slide}{}
\fbox{\sc 2. コンピュータについてのイロハ}

\begin{itemize}
\item {\eec CPU}

プログラムに従って命令を実行

\item {\eec メモリ}

プログラム, データを置く場所. 場所 (番地) を指定して高速に出し入れができる. 

\item {\eec レジスタ}

CPU が持っている特別なメモリで, 演算の対象になる. 数は多くなく, 大きさ
(長さ) も小さい.
\end{itemize}

\end{slide}

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

\underline{\uc 扱える数}

レジスタの大きさ = 扱える数の範囲

32ビットレジスタ $\Rightarrow$ 0 から $2^{32}-1$ までの整数しか扱えない

\end{slide}

\begin{slide}{}
\underline{\uc 数学に使う場合を考えると...}

$11111111111 \times 11111111111$

$\Rightarrow$ {\ec 1332508849} ??? (=結果を $2^{32}$ で割った余り)

かといって

$11111111111 \times 11111111111$

$\Rightarrow 1.234567 \times 10^{20}$ 

も困る

{\ec 誤差が入ると数学としては無意味な計算}
\end{slide}

\begin{slide}{}
\underline{\uc とりあえず大きな整数は扱えないといけない}

$\Rightarrow$ {\eec プログラム}を書けばよい

メモリ上に整数を並べて, コンピュータに {\eec 「筆算」}をさせればよい

\begin{itemize}
\item {\eec 人間}

ひとけた : 0 以上 9 以下

\item {\eec コンピュータ}

ひとけた : 0 以上 $2^{32}-1$ 以下
\end{itemize}
\end{slide}

\begin{slide}{}
\underline{\uc 例 : 整数の足し算}

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

\vskip 1cm

\underline{\uc 一変数多項式}

各次数の係数を並べればよい

$\Rightarrow$ これで{\ec 整数係数の多項式を数学的に扱える}

\end{slide}

\begin{slide}{}
\fbox{\sc 3. 多項式の因数分解 --- 中学高校的方法}
{
\Large\parskip 0pt

\begin{enumerate}
\item {\eec 眼力法} (解と係数の関係)

$x^2+ax+b \Rightarrow$ 足して $a$, かけて $b$ になる数の組

$x^3+ax^2+bx+c$ はどうする?

\item {\eec 因数定理}

代入して 0 になる数を探す (どうやって探す?)

\item {\eec 解の公式}

$x^2+ax+b=0$ の根 ${-b \pm \sqrt{a^2-4b}} \over 2$

$\Rightarrow$ $a^2-4b = t^2$ ($t$ : 整数) とかけるかどうか調べる
\end{enumerate}
}
\end{slide}

\begin{slide}{}
\underline{\uc 眼力法は問題を難しくしている}

例 : $x^2+11508x+28386587$

$28386587=3581\times 7927$ が眼力で分かる人は少ない(と思う)

\vskip 1cm

\underline{\uc 解の公式法は有望}

$(a^2-4b)/4 = 4717584 = 2172^2$ なら何とかなる?

$\Rightarrow$ {\bf \ec $x^2-t=0$ の整数根を探す方法があればよい}
\end{slide}

\begin{slide}{}
\underline{\uc 3 次以下の多項式}

{\eec 整数上で分解できるなら, 一次因子を持つ}

$\Rightarrow$ {\ec 根を探す方法が適用できる}

{\eec 根拠 : 中間値の定理}
「$f(a) < 0, f(b) > 0$ なら $a$, $b$ の間に $f(c)=0$ なる $c$ がある.」

\begin{itemize}
\item {\eec 二分法}

区間を半分ずつ狭めて追い込む

\item {\eec Newton 法}

二分法よりずっと高速
\end{itemize}

\end{slide}

\begin{slide}{}
\underline{\uc 4 次以上の場合}

いろいろな分解パターンがあり得る

4 次 = 2 次 $\times$ 2 次

$\Rightarrow$ {\ec 根を探す方法は適用困難}

\vskip 1cm

\underline{\uc コンピュータには力技(繰り返し)が似合う}

{\eec 中間値の定理} = {\eec 実数における近似} の利用

別の近似 $\Rightarrow$ {\ec 割った余り}に注目
\end{slide}

\begin{slide}{}
\fbox{\sc 4. $p$-進近似による多項式の因数分解}
{\Large\parskip 0pt

\underline{\uc 原理} : {\eec 整数 $m$ が 0} $\Leftrightarrow$

{\eec $m$ はどんな整数でも割り切れる}

({\eec $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=1,2,\ldots$)

\item $g_1$, $h_1$ が正解に対応していれば, 適当な $k$ のところでほんとに割り切れるだろう. 
\end{enumerate}}
\end{slide}

\begin{slide}{}
\underline{\uc 言いかえれば...}

以下, {\ec 簡単のため}, $f(x)$ および因子の係数は全て正であるとする. 

{\eec $f(x) = a_0(x)+p \cdot a_1(x)+p^2\cdot a_2(x)+\cdots$}

と「べき級数展開」 ( $a_i$ の係数は $p-1$ 以下)

{\ec $g(x) = b_0(x)+p\cdot b_1(x)+p^2\cdot b_2(x)+\cdots$}

{\ec $h(x) = c_0(x)+p\cdot c_1(x)+p^2\cdot c_2(x)+\cdots$}

($b_i$, $c_i$ の係数は $p-1$ 以下)

とおいて $f(x)-g(x)h(x)=0$ から $b_i$, $c_i$ を決める. 
\end{slide}

\begin{slide}{}
\underline{\uc 記号 $a \equiv b \bmod M$}

$M$ を整数とする. {\eec $a \equiv b \bmod M$} とは

\begin{itemize}
\item $a,b$ が整数のとき, 

{\eec $a-b$ が $M$ で割り切れる}こと

\item $a,b$ が整数係数多項式のとき

{\eec $a-b$ の各係数が $M$ で割り切れる}こと
\end{itemize}

\vskip 1cm

\underline{\uc $a$ を $M$ で割った余りも $a \bmod M$ と書く}
\end{slide}

\begin{slide}{}
\underline{\uc $b_0(x)$, $c_0(x)$ からスタート}

$f-gh$

$\quad = a_0-${\ec $b_0c_0$} + ($p$で割り切れる多項式)

だから, $f=gh$ なら

$a_0 \equiv$ {\ec $b_0c_0$} $\bmod p$ のはず

\underline{\uc 例}

{\eec
\begin{tabbing}
$f(x)=$ \= $x^4+17056x^3+72658809x^2$ \\
\> $+3504023212x+30603759869$
\end{tabbing}}

$p = 3$ とすると $a_0(x)=x^4+x^3+x+2$
\end{slide}

\begin{slide}{}
\underline{\uc 一次因子があるか?}

{\ec $b_0(x) = x+q$}, 
{\ec $c_0(x) = x^3+rx^2+sx+t$} とおく. 

$a_0 \equiv b_0c_0 \bmod 3$ より\\

{\ec
$\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$ に 0, 1, 2 をどう入れてもダメ. 

よって, {\eec 一次因子はない}.

\end{slide}

\begin{slide}{}
\underline{\uc 二次因子はあるか? --- まず $b_0$, $c_0$ を探す}

{\ec $b_0(x) = x^2+qx+r$},
{\ec $c_0(x) = x^2+sx+t$}

とおくと, $a_0 \equiv b_0c_0 \bmod 3$ より\\

{\ec
$\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, 2 の値を入れてみれば

{\eec $(q,r,s,t) = (0,1,1,2), (1,2,0,1)$}

一方が $b_0$, 他方が $c_0$ $\Rightarrow$ これらは同じもの
\end{slide}

\begin{slide}{}
\underline{\uc 二次因子つづき --- $b_1$, $c_1$ が満たす性質}

{\Large\parskip 0pt
{\eec $b_0 = x^2+1$}, 
{\eec $c_0 = x^2+x+2$} とすると

\centerline{\eec $f-b_0c_0 \equiv 0 \bmod 3$}

$f-gh \equiv a_0-b_0c_0+p(a_1-$
$(b_0${\ec$c_1$}$+c_0${\ec$b_1$}$))\bmod 3^2$

より, 両辺を 3 で割って

${{f-gh}\over 3} \equiv {{a_0-b_0c_0}\over 3}+(a_1-$
$(b_0${\ec$c_1$}$+c_0${\ec$b_1$}$))\bmod 3$

左辺は $3$ で何回でも割れる $\Rightarrow$  右辺は $3$ で割れる

補正項 {\ec $b_1$}, {\ec $c_1$} : $x^2$ の係数は 0 としてよい}

\end{slide}

\begin{slide}{}
\underline{\uc 二次因子つづき --- $b_1$, $c_1$ が満たす方程式}

{\Large\parskip 0pt
{\ec $b_1 = qx+r$},
{\ec $c_1 = sx+t$} とおく.

\begin{tabbing}
右辺 = \= {\ec $-(q+s)x^3-(q+r+t+1)x^2$}\\
\> {\ec $-(2q+r+s-1)x-(2r+t)$}
\end{tabbing}

$右辺 \equiv 0 \bmod 3$ より\\

{\ec 
$\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.$\\}

こんどは連立一次方程式(合同式). これを解くと

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

\end{slide}

\begin{slide}{}
\underline{\uc 二次因子つづき --- $b_k$, $c_k$ も同様}

{\Large\parskip 0pt
これで, 

\centerline{\eec $f \equiv (b_0+3b_1)(c_0+3c_1) \bmod 3^2$}

以下同様に, 

\centerline{\ec $b_k = qx+r, c_k = sx+t$}

とおいて, $(q,r,s,t)$ の連立一次方程式を解けば

\centerline{\eec $f \equiv (b_0+\ldots+3^{k-1}b_{k-1})(c_0+\ldots+3^{k-1}c_{k-1}) \bmod 3^k$}

すなわち 

\centerline{\eec $f \equiv g_kh_k \bmod 3^k$}

となる $g_k, h_k$ が決まる. }

\end{slide}

\begin{slide}{}
\underline{\uc $(g_k, h_k)$ の表}

{\large
\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&{\ec $x^2+7821x+89347$}&{\ec $x^2+9235x+342527$}\\ \hline
13&{\ec $x^2+7821x+89347$}&{\ec $x^2+9235x+342527$}\\ \hline
\end{tabular}}
\end{slide}

\begin{slide}{}
\underline{\uc $\bmod 3^k$ での因子から真の因子へ}

表で見ると, {\eec $k=12 \rightarrow 13$ で変化がない}

$\Rightarrow$ {\ec $f-g_{13}h_{13}$ を計算してみると 0!}

{\eec
$f(x) = (x^2+7821x+89347) \times$

$(x^2+9235x+342527)$}

\underline{\uc 実際には...}

\begin{itemize}
\item 負の係数の場合を扱うための工夫が必要

\item 失敗の可能性もあるので, $k$ をどこまで上げればいいかの上限が必要
\end{itemize}
\end{slide}

\begin{slide}{}
\underline{\uc $\bmod p$ での分解が一番大切}

各ステップで出て来る係数の方程式

\begin{itemize}
\item {\eec $k > 1$}

連立一次方程式 (実際には合同式)

\item {\eec $k = 1$}

一次方程式でない 

$\Rightarrow$ しらみつぶしで解くのはあまりに効率
がわるい (いくらコンピュータでも)
\end{itemize}
\end{slide}

\begin{slide}{}
\fbox{\sc 5. 有限体 $GF(p) = \{0,1,\cdots,p-1\}$ }

$p$ が{\ec 素数}のとき, 

{\eec $GF(p) = \{0,1,\cdots,p-1\}$} に, $+$, $-$, $\times$ を
{\eec 「結果を $p$ で 割った余り」}で定義すると

\begin{enumerate}
\item 加減乗算で閉じている. 
\item {\eec 0 以外の元で割算ができる. }

「$a {\not \equiv} 0 \bmod p$ なら $ab \equiv 1 \bmod p$ なる $b$ がある」
\end{enumerate}

すなわち, {\eec $GF(p)$ は体(タイ)} 

元の個数が有限個 ($p$ 個)なので {\ec 有限体} とよぶ. 

\end{slide}

\begin{slide}{}
\underline{\uc $k=1$ $\Rightarrow$  有限体上での因数分解}

$a_0 \equiv f \bmod p$ を $GF(p)$ 係数多項式とみる. 

$\Rightarrow$ $a_0 \equiv b_0c_0 \bmod p$ となる $b_0$, $c_0$ を
求めることは, $GF(p)$ 上での因数分解に相当

$\Rightarrow$ {\eec 実はよいアルゴリズムがある}

\vskip 1cm

\underline{\uc $k > 1$ $\Rightarrow$ 有限体上での連立一次方程式求解}

実際には, $k=1$ の結果から機械的に計算できる.
\end{slide}

\begin{slide}{}
\underline{\uc 因数分解まとめ (Zassenhaus アルゴリズム)}

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

{\eec 「よい」} とは

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

\item $GF(p)$ での因子が全て異なる etc.
\end{itemize}

\item {\eec 次を繰り返し}

\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}
\end{slide}

\begin{slide}{}
\underline{\uc 裏にはいろいろ数学が隠れている}

\begin{itemize}
\item {\eec 体の上での因数分解の一意性}

体上の多項式環の性質

\item {\eec 有限体上での因数分解アルゴリズム}

Berlekamp アルゴリズム

\item {\eec $\bmod p$ から $\bmod p^k$ への持ち上げ}

Euclid の互除法, Hensel の補題
\end{itemize}

$\Rightarrow$ 計算機のパワーだけではダメ.

{\ec 数学をうまく使ったアルゴリズム設計が必要}

\end{slide}

\begin{slide}{}
\fbox{\sc 6. 有限体の応用例 : 暗号}

\underline{\uc ネットワーク上での通信は基本的に筒抜け}

自分の身は自分で守る $\Rightarrow$ 通信内容を{\ec 暗号}化

\underline{\uc 暗号化通信の一例}

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

\item 送信側 : 鍵で暗号化 $\Rightarrow$ 受信側 : 鍵で復号化
\end{enumerate}

\underline{\uc 問題 : 通信路が筒抜けのときに,}

\underline{\uc どうやって鍵を共有?}
\end{slide}

\begin{slide}{}
{\Large\parskip 0pt
\underline{\uc A さんと B さんが鍵を共有 --- Diffie-Hellman}

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

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

\item {\eec A さんの仕事}

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

\item {\eec B さんの仕事}

\begin{enumerate}
\item $0 < s_B < p$ なる整数 {\eec $s_B$} (秘密) を作る.
\item $w_B =$ {\eec $g^{s_B} \bmod p$} を A さんに送る.
\item $s =$ {\eec $w_A^{s_B} \bmod p$} を作る. 
\end{enumerate}

\end{itemize}}
\end{slide}

\begin{slide}{}
\underline{\uc 大事な点}

\begin{itemize}
\item {\eec $w_B^{s_A} = w_A^{s_B} \bmod p$}

これで鍵が共有できた

\item {\eec $w_A$, $w_B$ は暗号化されない}

$g^{s_A} \bmod p$ から $s_A$ を求めるのは難しい

{\ec (有限体の乗法群における離散対数問題)}

\item $\overline{a^b} = a^b \bmod p$ は {\eec $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}}$

\end{itemize}
\end{slide}

\begin{slide}{}
\underline{\uc 他にもいろいろある}

\begin{itemize}
\item {\eec RSA 暗号}

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

\item {\eec 楕円曲線暗号}

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

{\eec $kP$ から $k$ を求める計算の難しさ}を利用
\end{itemize}

$\Rightarrow$ {\ec 直接, 間接に整数の剰余演算が関与}
\end{slide}

\begin{slide}{}
\fbox{\sc 7. まとめ}

\begin{enumerate}
\item {\eec 多項式因数分解程度でも, 効率よい実現は大変}

数学が意外に役に立つ $\cdots$ 特に{\ec 有限体}

\item {\eec でも有限体なんて他に何の役に立つの?}

実は IT 社会を裏で支えていたりする. 

\item {\eec 数学の懐の深さ}

後になってとんでもないところに応用される可能性

計算の難しさが役に立つこともあるという不思議


\end{enumerate}

\end{slide}

%\begin{slide}{}
%\fbox{\bf}
%\end{slide}