大階線性函式是什麼意思？
我正在閱讀這篇論文“Farfalle: parallel permutation-based cryptography”，其中有些術語我不明白。
- 第 4 頁 說
比率效率與安全邊際。
比率效率和安全邊際是什麼意思？
- 第 5 頁 說
通常，rollc 是一個具有大階的輕量級線性函式，
我的問題是：什麼是大階線性函式？
自然，rolle在短週期內應該有可以忽略不計的狀態數量（最好沒有），因為它們會導致周期性的輸出序列
我的問題是：排列在短週期內具有可忽略不計的狀態數量意味著什麼？
TL;DR跳到底部進行更新。
眾所周知，映射$$ L:{0,1}^n\rightarrow {0,1}^n, $$上的原始 LFSR $ n $ bits 有一個很長的長度循環 $ 2^n-1, $ 和一個長度循環 $ 1 $ （將零映射到零）。
作為一個排列，這個映射有很大的順序，即對於幾乎所有的狀態空間，最小的 $ k, $ 使得 $ k- $ 折疊組成 $ L $ 給出恆等映射是 $ k=2^{n}-1: $ $$ L^{k}(\cdot)=L(L(\cdots(L(\cdot)))). $$
隨機選擇的排列 $ {0,1}^n $ 至少有一個具有機率的不動點 $ (1-e^{-1}) $ ，並且被認為是一種狀態映射，它有很多短週期。
隨機排列的預期不動點數實際上是1，但這不是那麼相關，相關性是相對較大的小循環數。
事實上，沒有長度循環的排列分數 $ k $ 或更少是 $ e^{-H_k} $ 在哪裡 $ H_k=1+2+\cdots+k $ 是諧波數。您可以使用近似值 $ H_k \approx\ln k $ 獲得一些粗略的估計。
有關詳細資訊，另請參閱有關 mathoverflow 的答案。這在這裡是不可取的，並且必須仔細選擇排列。
編輯：有關更具體的結果，請參見 *此處*Odlyzko-Flajolet 的論文，例如，證明了預期的“rho 長度”，即初始段後跟從狀態空間中的隨機起點開始的閉合循環是 $ O(\sqrt{N}), $ 對於一個排列 $ N $ 點（定理 7）。
現在與 $ O(N) $ 原始 LFSR 範例中的周期長度 $ N=2^n. $