12,966
回編集
「情報理論 - ガロア体」の版間の差分
ナビゲーションに移動
検索に移動
→多項式
(→既約多項式) |
(→多項式) |
||
| 91行目: | 91行目: | ||
例.3<br> | 例.3<br> | ||
5次多項式<math>1 + x + x^2 + x^5</math> は、<math>(1 + x^2)(1 + x + x^3)</math>と因数分解できるため、既約多項式ではない。<br> | 5次多項式<math>1 + x + x^2 + x^5</math> は、<math>(1 + x^2)(1 + x + x^3)</math>と因数分解できるため、既約多項式ではない。<br> | ||
<br> | |||
==== GF(2)の既約多項式の求め方 ==== | |||
m次の既約多項式を求めるには、まず、m次の次数が存在する必要がある。(例. 3次既約多項式ではx<sup>3</sup>、5次既約多項式ではx<sup>5</sup>等)<br> | |||
<br> | |||
<u><math>GF(2) = \{0, 1\}</math> のため、係数は0、 1のいずれかである。</u><br> | |||
もし、係数が2以上の値の時は、係数に<math>\bmod 2</math>を用いて計算する。<br> | |||
<br> | |||
* 1次既約多項式 | |||
GF(2)上の1次既約多項式を求めるには、<math>f(x) = ax + b</math>において、因数分解できないため、1次既約多項式は、<math>x, \quad x + 1</math>の2つである。<br> | |||
<br> | |||
<u>2次以降の既約多項式では、必ず定数項を含むことに注意する。</u><br> | |||
<u>なぜなら、定数項が存在しない場合、<math>f(0) = 0</math>となり、また、f(x)は1次既約多項式xで可約(因数分解)できるからである。</u><br> | |||
<br> | |||
* 2次既約多項式 | |||
2次既約多項式を求めるには、<math>f(x) = x^2 + ax + 1</math>とする時、<math>[\frac{m}{2}] = 1</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(1) = 1 + a + 1 = a \ne 0 \quad \mbox{す な わ ち} \quad a = 1</math><br> | |||
したがって、2次既約多項式は、<math>f(x) = x^2 + x + 1</math>となる。<br> | |||
<br> | |||
* 3次既約多項式 | |||
3次既約多項式を求めるには、<math>f(x) = x^3 + ax^2 + bx + 1</math>とする時、<math>[\frac{m}{2}] = 1</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(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> | |||
<br><br> | <br><br> | ||
__FORCETOC__ | __FORCETOC__ | ||
[[カテゴリ:情報理論]] | [[カテゴリ:情報理論]] | ||