フィールド モジュロ 2 とフィールド モジュロ 3 で、次の多項式 (2 つの個別の質問) の GCD を見つけようとしています。
a(x) =x5+x3+x2+ 1,
b(x) =x3+x for mod 2
a(x) = 2x3+2x2+x+1
b(x) =x2+2 for mod 3
最初のものについては、多項式を 1 と 0 のビット (例: 101101 と 1010) として表現しようとし、ユークリッドのアルゴリズムを使用して GCD を見つけようとしましたが、ある時点でゼロにつながります。計算を正しく。
多項式の 2 番目のセットは、係数が 1 より大きいため、まったくわかりません。
どんな助けでも大歓迎です。
させて
f_1 = x^5 + x^3 + x^2 + 1 および
f_2 = x^3 + x
mod 2 の作業で、表記を次のように変更できます。
f_1 = (1,0,1,1,0,1) および
f_2 = (1,0,1,0)。
長除算を行うと、f_1 = q_2 * f_2 + f_3 が得られます。ここで、f_3 は厳密に f_2 の次数よりも小さい次数です。
判明したのは
q_2 = (1,0,0) つまり q_2 = x^2
f_3 = (1,0,1) つまり f_3 = x^2 + 1
継続して取得します
f_2 = q_3 * f_3 + f_4
判明したのは
q_3 = (1,0) および
f_4 = (0)
後者は、ユークリッドのアルゴリズムが完了し、f_n の最後の非ゼロ多項式が GCD であることを通知します。したがって、f_3 は GCD です。f_3 が実際に公約数であることを示すのは簡単です。
2 番目のケースでは、上記の (1,0,1) のようにタプルを使用しますが、今回は座標が 0、1、または 2 (余りは mod 3) です。それ以外の場合、アルゴリズムは同じです。
アルゴリズムを何らかのプログラミング言語で実装すると、理解が深まります。