ochiai/book/CA

「計算機代数の基礎理論」長坂、岩根、北本、讃岐、照井、鍋島、共立出版, 2019.

• p50, 例題3-21.「$\mathbb{Z}[x]$ においては $\gcd(f,g) \equiv x^2+3x+2 \mod 5$」。よくわからない。左辺は $x+2$ であると２行目に書いてあるが、「$x+2 \equiv x^2+3x+2 \mod 5$」は正しくないので。
• p55, line 14 の事例。ちょっと趣旨がよくわからないのだが、$p=5$, $f(x) = x^2+13x+42$, $g_0(x)=x+1$, $h_0(x)=x+2$, $d=3$, の場合に、$g_3(x) = x+6, h_3(x) =x+7$ は適格だと思うのだが、$g_3(x) = 7x+42$, $h_3(x) = 18x+1$ は、条件 $g_3(x) \equiv g_0(x) \mod p$, $h_3(x) \equiv h_0(x) \mod p$ を満たしていないように思う。 単元倍による不定性であれば例えば $g_3(x) = 6x+36$ のような事態を想定している？いや、おそらくもっと適切な事例があるのだと思う。
• 定理3-37. 十分性の証明。本の証明で正しいが簡潔にできそう。$\gcd(f,f') \neq 1$ とする。$g | \gcd(f,f')$ を既約多項式とする。$f(x) = g(x) h(x)$ と書ける。$f' = g h' + g' h$ と $g | f'$ より、$g | g' h$ である。$g'$ の次数が $g$ の次数未満であることから $g'$ は $g$ で割り切れないから、 $g$ の既約性より $g|h$ である。すなわち、$h(x) = g(x) k(x)$ であり、$f(x) =g(x)^2 k(x)$ となる。証明終わり。
• アルゴリズム5-1の中の $g_i(x)$ と、定理5-15の中の$g_i(x)$ は異なるものである。それぞれはそれぞれの subroutine の中で使われていて齟齬はないのだが、定理5-16 の証明に $g_i(x)$ が現れたタイミングでアルゴリズム 5-1 と書いてあるので、ついついアルゴリズム 5-1 の $g_i(x)$ と誤認しがちだが、ここの $g_i(x)$ は定理5-15 の $g_i(x)$ である。できれば異なる記号で書いたほうが親切では、と思いました。
• p144, line -10. 「すべて」。アルゴリズムを走らせると、最初の $g(x)$ に対しても、ある $\alpha$ に対する $g(x)-\alpha$ が分離多項式になる可能性がある程度あると思う。その分離多項式を用いて $f$ を２つの多項式の積に分けられるので次数が下がる。　$g,\alpha$ の「すべて」を走らせる必要があるのだろうか。
• p144, line -6. 「事前計算」。結局 $\mathcal{A}$ を求める時に、すべての $\alpha$ に対する $\gcd(f(x),g(x)-\alpha)$ を計算しているように思うので、どう効率的なのかがよくわからないです。
• p122, line 1. 分離多項式の定義。前のページの line -2 で「一部の $i$」と文章的に書いている。この「一部の $i$」 の趣旨は「全体でも空でもない」ということかな。数式を使うと、$1 \neq \gcd(f,g) \neq f$ ということで良いか？
• p122, line 5. 「$g(x)$」は「分離多項式」としたい。line 14 の $g(x)$ と、ここの $g(x)$ は異なるので、ここで $g(x)$ の文字を使いたくない感じがする。
• 同じ趣旨。３行目でも「$g(x)$ として $f$-簡約多項式を扱った」は「分離多項式として $f$-簡約多項式を扱った」とか「$f$-簡約多項式を分離多項式に用いた」のように書きたい。
• 同じ趣旨。４行目でも「$g(x)$ を無作為（ランダム）に」も「$h(x)$ をランダムに」としたい感じ。ただ、$h(x)$ はline 16 まで出てこないので、書きづらいけど。文字を使わないで、「ランダムに与えた多項式を用いて分離多項式を探索する」のように書くことも可能かな。
• p122, line 16. 「任意の」。任意の... が ... を満たす、と読めてしまうと誤り。
• p122, line 23. 「それら」。２行上の $h(x)^e\pm 1$ を指している。
• p123 の証明の最後の行。余事象を求めているところ、「$\chi_i(h^e-1)$ $(i=1,\ldots,k)$ の値がすべて等しく」なる確率を $2\times (1/2)^k$ と積で求めている。一つ一つが $1/2$ であることは line 8 に解説済みであるが、「$i$ に関して互いに独立事象である」ということをどこかで示しているだろうか？

• 補題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$ となった。