random number理論

note math

深入探索 random number

LSFR

特徵多項式

  • LSFR中儲存的為一個2元序列序列
  • 因此可以將LSFR內的值表達成
b1,b2,..,bn{b_1,b_2,..,b_n}
  • 而其中的第 n+1n+1 位為
bn+1=c1b1⊕c2b2⊕..⊕cnbn其中bi,i∈[1,n]表示LSFR中的數據0or1ci,i∈[1,n]表示第i位是否存在,如果存在則ci=1表示該位參與了運算\begin{align*} b_\text{n+1} = c1b1 \oplus c2b2 \oplus .. \oplus c_nbn \text{其中} b_i, i \in [1,n] \text{表示LSFR中的數據0or1} \\ c_i, i \in [1,n] \text{表示第i位是否存在,如果存在則} c_i = 1 \text{表示該位參與了運算} \end{align*}

有限域

  • 這邊接使用 GF(2)\mathbb{GF(2)} 來表達有限域
    1. 系數只有 0,10 , 1
    2. 加法和減法都等同於找XOR運算
GF(2)∈ZGF(2)中的規則很簡單\begin{align*} \mathbb{GF(2)} \in \mathbb{Z} \\ \mathbb{GF(2)} \text{中的規則很簡單} \end{align*}
  • GF(2)\mathbb{GF(2)}運算核心
    • 所有的運算都需要 mod2mod2
  • 因此可以知道正負號在 GF(2)\mathbb{GF(2)} 下是相等的,原因如下
加法1+1≡0(mod2)減法相當於找一個a來滿足(−1)+a≡0(mod2)因此a=1\begin{align*} \text{加法} 1 + 1 \equiv 0 (mod2) \\ \text{減法相當於找一個a來滿足} (-1) + a \equiv 0 (mod2) \\ \text{因此} a = 1 \end{align*}
  • 如果一個LSFR可以表示為
bn+1 =c1b1⊕c2b2⊕..⊕cnbn b_\text{n+1}\ = c_1b_1 \oplus c_2b_2 \oplus .. \oplus c_nb_n
  • 其對應的特徵多項式為
f(x)=cnxn+cn-1xn-1+..+c1x1+1 f(x) = c_nx^n + c_\text{n-1}x^\text{n-1} + .. + c_1x^1 + 1
  • 現在假設我們有 f(b1,b2,b3)=b1⊕b3f(b1,b2,b3) = b1 \oplus b3 則其特徵多項式為 f(x)=x3+x+1f(x) = x^3+x+1
    • 特徵多項式從定義得知最後都需要 +1+1
  • 其中
b3=c3≡1→x3b2=c2≡0→0b1=c1≡1→x1\begin{align*} b3 = c_3 \equiv 1 \rightarrow x^3 \\ b2 = c_2 \equiv 0 \rightarrow 0 \\ b1 = c_1 \equiv 1 \rightarrow x^1 \end{align*}