ikautak.log

C/C++, Python, CUDA, Android, Linux kernel, Network, etc.

暗号理論入門 3.19〜3.22

暗号理論入門 原書第3版

暗号理論入門 原書第3版

3.19 体上の多項式

 K を体とする。 f,\  g \in K[x],\ \ \ f,\ \ g \ne 0 であれば、 deg(fg) = deg\ f + deg\ g が成立する。

整数環と同様、多項式環  K [x] でも割り算をして余りを計算することが可能。

 f,\ g \in K[x],\ \ \ g \ne 0 とする。このとき、 f = qg + r であり、 r = 0 または  deg\ r \lt deg\ g となる一意的に定まる多項式  q,\ \ r \in K[x] が存在する。
 q  fg による除法の(quotient)、r余りまたは剰余(remainder)といい、 r = f\ mod\ g と書く。

f  K[x] の0でない多項式で、af は零点であるとき、ある q \in K[x] について、  f = (x - a)q であり、f多項式  (x - a) で割り切れる。

3.20 有限体の構成法

任意の素数 p自然数 n について p^{n} 個の元をもつ有限体は GF(p^{n}) と書く。
素数 p を体  GF(p^{n}) の標数という。体  GF(p) を素体という。

例.(\mathbb{Z}/2 \mathbb{Z})[X] での mod\ f(X) = X^{2} + X + 1 の剰余類は
f(\mathbb{Z} / 2 \mathbb{Z})
1 + f(\mathbb{Z} / 2 \mathbb{Z})
X + f(\mathbb{Z} / 2 \mathbb{Z})
X + 1 + f(\mathbb{Z} / 2 \mathbb{Z})
である。

3.21 有限体の単数群の構造

K q 個の元をもつ有限体とする。このとき、q - 1 の任意の約数 d はちょうど  \varphi(d) 個の位数 d の元を単数群 K^{*} にもつ。

K が有限体で q 個の元をもつとすると、単位群 K^{*} は位数  q - 1巡回群である。この巡回群 \varphi(q - 1) 個の生成元をもつ。

3.22 素数を法とする既約剰余群の構造

p を素数とする。mod\ p の既約剰余群は巡回群で、その位数は  p - 1 である。

剰余類  a + p \mathbb{Z} が既約剰余群 (\mathbb{Z} / p \mathbb{Z})^{*} を生成するような整数 amod\ p原始根とよばれる。

参考サイト
http://www.epii.jp/articles/note/math/primitive_root