13,005
回編集
「情報理論 - ガロア体」の版間の差分
ナビゲーションに移動
検索に移動
→GF(2)の既約多項式の求め方
| 106行目: | 106行目: | ||
<br> | <br> | ||
* 2次既約多項式 | * 2次既約多項式 | ||
2次既約多項式を求めるには、<math>f(x) = x^2 + ax + 1</math>とする時、<math> | 2次既約多項式を求めるには、<math>f(x) = x^2 + ax + 1</math>とする時、<math>\left \lfloor \frac{m}{2} \right \rfloor = 1</math> (床関数)だから、<br> | ||
f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から<math>f(0) \ne 0, \quad f(1) \ne 0</math>ならばよい。<br> | f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から<math>f(0) \ne 0, \quad f(1) \ne 0</math>ならばよい。<br> | ||
(床関数とは、<math>n \le x < n + 1</math>を満たす整数nのことを<math>\lfloor x \rfloor</math>と記述する。<math>\lfloor x \rfloor</math>は、xを超えない最大の整数とも言える。)<br> | |||
<br> | |||
<math>f(0) = 1 \ne 0</math><br> | <math>f(0) = 1 \ne 0</math><br> | ||
<math>f(1) = 1 + a + 1 = a \ne 0 \quad \mbox{す な わ ち} \quad a = 1</math><br> | <math>f(1) = 1 + a + 1 = a \ne 0 \quad \mbox{す な わ ち} \quad a = 1</math><br> | ||
| 113行目: | 115行目: | ||
<br> | <br> | ||
* 3次既約多項式 | * 3次既約多項式 | ||
3次既約多項式を求めるには、<math>f(x) = x^3 + ax^2 + bx + 1</math>とする時、<math> | 3次既約多項式を求めるには、<math>f(x) = x^3 + ax^2 + bx + 1</math>とする時、<math>\left \lfloor \frac{m}{2} \right \rfloor = 1</math>だから、<br> | ||
f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から<math>f(0) \ne 0, \quad f(1) \ne 0</math>ならばよい。<br> | f(x)が1次既約多項式で因数分解できなければよく、かつ、剰余定理から<math>f(0) \ne 0, \quad f(1) \ne 0</math>ならばよい。<br> | ||
<math>f(0) = 1 \ne 0</math><br> | <math>f(0) = 1 \ne 0</math><br> | ||
<math>f(1) = 1 + a + b + 1 = a + b \ne 0 \quad \mbox{す な わ ち} \quad (a, b) = (1, 0) \quad \mbox{ま た は} \quad (0, 1)</math><br> | <math>f(1) = 1 + a + b + 1 = a + b \ne 0 \quad \mbox{す な わ ち} \quad (a, b) = (1, 0) \quad \mbox{ま た は} \quad (0, 1)</math><br> | ||
したがって、3次既約多項式は、<math>f(x) = x^3 + x^2 + 1, \quad f(x) = x^3 + x + 1</math> の2つとなる。<br> | したがって、3次既約多項式は、<math>f(x) = x^3 + x^2 + 1, \quad f(x) = x^3 + x + 1</math> の2つとなる。<br> | ||
<br> | |||
* 4次既約多項式 | |||
4次既約多項式を求めるには、<math>f(x) = x^4 + ax^3 + bx^2 + cx + 1</math>とする時、<math>\left \lfloor \frac{m}{2} \right \rfloor = 2</math>だから、<br> | |||
f(x)が2次以下の既約多項式で因数分解できなければよく、かつ、剰余定理から<math>f(0) \ne 0, \quad f(1) \ne 0</math>ならばよい。<br> | |||
<math>f(0) = 1 \ne 0</math><br> | |||
<math>f(1) = 1 + a + b + c + 1 = a + b + c \ne 0 \quad \mbox{し た が っ て} \quad a + b + c = 1</math><br> | |||
<br> | |||
f(x)を2次の既約多項式<math>x^2 + x + 1</math>で割った剰余は、<math>x(b + c + 1) + (a + b + 1)</math><br> | |||
<br> | |||
<math>b + c + 1, \quad a + b + 1</math>が同時に0になってはならないため、<math>b + c = 0 \quad \mbox{ま た は} \quad a + b = 0</math><br> | |||
<math>a + b = 0 \quad \mbox{の 時 、} \quad a + b + c = c = 1 \quad \mbox{し た が っ て} \quad (a, b) = (0, 0), (1, 1) \quad \mbox{よ り} \quad (a, b, c) = (0, 0, 1), (1, 1, 1)</math><br> | |||
<math>b + c = 0 \quad \mbox{の 時 、} \quad a + b + c = a = 1 \quad \mbox{し た が っ て} \quad (b, c) = (0, 0), (1, 1) \quad \mbox{よ り} \quad (a, b, c) = (1, 0, 0), (1, 1, 1)</math><br> | |||
<br> | |||
<math>\mbox{上 記 よ り} \quad (a, b, c) = (1, 1, 1), (1, 0, 0), (0, 0, 1)</math><br> | |||
したがって、4次既約多項式は、<math>f(x) = x^4 + x^3 + x^2 + x + 1, \quad x^4 + x^3 + 1, \quad x^4 + x + 1</math> の3つとなる。<br> | |||
<br><br> | <br><br> | ||
__FORCETOC__ | __FORCETOC__ | ||
[[カテゴリ:情報理論]] | [[カテゴリ:情報理論]] | ||