Processing math: 0%
ochiai/book/CA
をテンプレートにして作成
開始行:
「計算機代数の基礎理論」長坂、岩根、北本、讃岐、照井、鍋...
- p50, 例題3-21.「
においては $\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]")
