情報科学 › 乱数と確率的数値計算 › 擬似乱数生成器

$F_2$ 線形生成器の最大周期

定理 5.3（「擬似乱数生成器」§5）・ ✓公理まで証明済み

$A$ を $\mathbb{F}_2$ 上の $n$ 次正方行列とする。次の 2 条件は同値である。

零でないある種 $x_0 \in \mathbb{F}_2^n$ について、状態の列 $x_k = A^kx_0$ が純周期的で周期が $2^n - 1$ である。
特性多項式 $\chi_A$ が $\mathbb{F}_2$ 上の原始多項式である。

このとき、零でないすべての種について列は純周期的で周期は $2^n - 1$ である。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 8 件、定義なども含めて 8 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義（直接 3 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

ケーリー・ハミルトンの定理✓系 7.3・加群と PID 上の構造定理
- 有理標準形✓定理 7.2・加群と PID 上の構造定理
  - 整数環と多項式環は単項イデアル整域✓命題 7.2・イデアルと剰余環
  - PID 上の有限生成加群の構造定理（不変因子形）✓定理 5.1・加群と PID 上の構造定理
    自由加群の部分加群は自由✓定理 3.1・加群と PID 上の構造定理
    スミス標準形✓定理 4.1・加群と PID 上の構造定理
    加群の準同型定理✓定理 2.3・加群と PID 上の構造定理
  - スミス標準形✓定理 4.1・加群と PID 上の構造定理
有限状態の生成器は最終的に周期的✓命題 2.3・擬似乱数生成器
整数環と多項式環は単項イデアル整域✓命題 7.2・イデアルと剰余環

これを使っている定理証明で参照している 1 件

原始多項式の存在✓命題 5.4・擬似乱数生成器

関連するノック 1 問

乱数と確率的数値計算第 6 問