ochiai/book/CA
をテンプレートにして作成
開始行:
「計算機代数の基礎理論」長坂、岩根、北本、讃岐、照井、鍋...
- p50, 例題3-21.「$\mathbb{Z}[x]$ においては $\gcd(f,g) \...
- p55, line 14 の事例。ちょっと趣旨がよくわからないのだが...
単元倍による不定性であれば例えば $g_3(x) = 6x+36$ のよう...
- 定理3-37. 十分性の証明。本の証明で正しいが簡潔にできそ...
- アルゴリズム5-1の中の $g_i(x)$ と、定理5-15の中の$g_i(x...
- p144, line -10. 「すべて」。アルゴリズムを走らせると、...
- p144, line -6. 「事前計算」。結局 $\mathcal{A}$ を求め...
- p122, line 1. 分離多項式の定義。前のページの line -2 で...
- p122, line 5. 「$g(x)$」は「分離多項式」としたい。line ...
- 同じ趣旨。３行目でも「$g(x)$ として $f$-簡約多項式を扱...
- 同じ趣旨。４行目でも「$g(x)$ を無作為（ランダム）に」も...
- p122, line 16. 「任意の」。任意の... が ... を満たす、...
- p122, line 23. 「それら」。２行上の $h(x)^e\pm 1$ を指...
- p123 の証明の最後の行。余事象を求めているところ、「$\ch...
- 補題3-30.
$f(x), g(x) \in \mathbb{F}_q[x]$ の場合は、
$\deg(h^*) \lt q$ ならば同じ結論が成り立つ。
$\deg(h^*) = q$ の時は反例「$f(x)=x(x^q-x)$,
$g(x)=x^q-x$」がある。
- 補題3-30 の背理法を避けた証明。
$k_i(x) := \gcd(\tilde{h}_i(x), h^*(x))$ とする。
$i\neq j$ の時、
$\gcd(\tilde{h}_i,\tilde{h}_j)
=\gcd(\tilde{f}(x), \tilde{h}_j)
= \gcd(\tilde{f}(x), \tilde{g}(x))=1$.
したがって、
$\gcd(k_i,k_j) | \gcd(\tilde{h}_i, \tilde{h}_j)=1$ より
$\gcd(k_i,k_j)=1$.
また、
$k_i | h^*(x)$ だから、
$\prod_{i=1}^{\deg(h^*)+1} k_i(x) | h^*(x)$.
両辺の次数を考えて、
$\sum_{i=1}^{\deg(h^*)+1} \deg k_i \le\deg(h^*)$.
したがって、ある $i$ に対して $\deg k_i=0$ なので、
$\gcd(\tilde{h}_i(x), h^*(x))=1$ となった。
終了行:
「計算機代数の基礎理論」長坂、岩根、北本、讃岐、照井、鍋...
- p50, 例題3-21.「$\mathbb{Z}[x]$ においては $\gcd(f,g) \...
- p55, line 14 の事例。ちょっと趣旨がよくわからないのだが...
単元倍による不定性であれば例えば $g_3(x) = 6x+36$ のよう...
- 定理3-37. 十分性の証明。本の証明で正しいが簡潔にできそ...
- アルゴリズム5-1の中の $g_i(x)$ と、定理5-15の中の$g_i(x...
- p144, line -10. 「すべて」。アルゴリズムを走らせると、...
- p144, line -6. 「事前計算」。結局 $\mathcal{A}$ を求め...
- p122, line 1. 分離多項式の定義。前のページの line -2 で...
- p122, line 5. 「$g(x)$」は「分離多項式」としたい。line ...
- 同じ趣旨。３行目でも「$g(x)$ として $f$-簡約多項式を扱...
- 同じ趣旨。４行目でも「$g(x)$ を無作為（ランダム）に」も...
- p122, line 16. 「任意の」。任意の... が ... を満たす、...
- p122, line 23. 「それら」。２行上の $h(x)^e\pm 1$ を指...
- p123 の証明の最後の行。余事象を求めているところ、「$\ch...
- 補題3-30.
$f(x), g(x) \in \mathbb{F}_q[x]$ の場合は、
$\deg(h^*) \lt q$ ならば同じ結論が成り立つ。
$\deg(h^*) = q$ の時は反例「$f(x)=x(x^q-x)$,
$g(x)=x^q-x$」がある。
- 補題3-30 の背理法を避けた証明。
$k_i(x) := \gcd(\tilde{h}_i(x), h^*(x))$ とする。
$i\neq j$ の時、
$\gcd(\tilde{h}_i,\tilde{h}_j)
=\gcd(\tilde{f}(x), \tilde{h}_j)
= \gcd(\tilde{f}(x), \tilde{g}(x))=1$.
したがって、
$\gcd(k_i,k_j) | \gcd(\tilde{h}_i, \tilde{h}_j)=1$ より
$\gcd(k_i,k_j)=1$.
また、
$k_i | h^*(x)$ だから、
$\prod_{i=1}^{\deg(h^*)+1} k_i(x) | h^*(x)$.
両辺の次数を考えて、
$\sum_{i=1}^{\deg(h^*)+1} \deg k_i \le\deg(h^*)$.
したがって、ある $i$ に対して $\deg k_i=0$ なので、
$\gcd(\tilde{h}_i(x), h^*(x))=1$ となった。
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
