度數與規律性指數
我正在研究多元密碼學，特別是使用 Groebner 基礎的攻擊。關於這種直接攻擊的複雜性，眾所周知，最重要的參數是規律性程度。
文獻中存在規律性指標和規律性程度是非常令人困惑的。通常，它們的定義是不同的。例如， Dubois 和 Gama的 HFE 系統的規則度使用非平凡度下降定義了規則度。
然而，在Bardet 等人的二次半正則多項式系統的正則指數的漸近行為中，他們使用希爾伯特多項式定義了正則指數。還有一些文章（我不記得了，抱歉）將規律性指數定義為 Groebner 基的最大程度。
到處參考算法複雜度公式，似乎都是一樣的。這些定義都是等價的嗎？這個例子怎麼樣？
集合的規律性程度或指數是多少 $ {x_1,\cdots,x_n}\subset\mathbb F_q[x_1,\cdots,x_n] $ ? 我認為第一個定義的規律性程度（非平凡程度下降）是 $ (q-1)n $ 因為從來沒有不平凡的程度下降。但是，顯然，第二和第三個定義的規律性指數是 1。
如果您推荐一些材料來閱讀它們，也將不勝感激。
文獻中有幾個定義，每個定義都旨在捕捉學位的一個方面 $ d $ 一個多項式方程組必須在其麥考利矩陣上的線性代數產生解之前對其展開。儘管它們是不同的東西，但其中一些被混淆地稱為規律性程度。我會盡我所能避免這個詞，並用別的東西來稱呼他們。
**規律性指數。**使用希爾伯特多項式和理想序列定義正則性指數 $ \mathcal{I} $
$$ 1 $$. 表示多項式的集合 $ \mathcal{I} $ 學位 $ s $ 或低於 $ \mathcal{I}{\leq s} $ 和同樣的 $ \mathbb{F}q[\mathbf{x}]{\leq s} $ . 希爾伯特函式 $ HF\mathcal{I} : \mathbb{N} \rightarrow \mathbb{N} $ 一個理想的 $ \mathcal{I} $ 定義為 $ HF_\mathcal{I}(s) = \mathsf{dim} , \mathbb{F}q[\mathbf{x}]{\leq s} / \mathcal{I}{\leq s} $ 緊接著就是 $ HF\mathcal{I}(s) = \mathsf{dim} , \mathbb{F}q[\mathbf{x}]{\leq s} - \mathsf{dim} , \mathcal{I}{\leq s} $ . 對於足夠大 $ s $ ，希爾伯特函式 $ \mathcal{I} $ 與多項式相同 $ HP\mathcal{I}(s) = \sum_{i=0}^d b_i \binom{s}{d-i} $ 對於一些 $ b_i \in \mathbb{Z} $ 和 $ b_0 \in \mathbb{N} \backslash {0} $ . 該多項式稱為希爾伯特多項式。規律性指數最小 $ s_0 $ 這樣對於所有人 $ s \geq s_0 $ , $ HF_\mathcal{I}(s) = HP_\mathcal{I}(s) $ ; 該值也稱為希爾伯特正則$$ 2 $$. 半正則度。 多項式序列 $ (p_1(\mathbf{x}), \ldots, p_m(\mathbf{x})) $ 是正常的，如果 $ g \cdot p_i \in \langle p_1, \ldots, p_{i-1}\rangle \implies g \in \langle p_1, \ldots, p_{i-1}\rangle $ . 正常系統擷取多項式系統的最壞情況。理想的希爾伯特級數 $ \mathcal{I} $ 被定義為正式的冪級數 $ HS_\mathcal{I}(t) = \sum_{s=0}^\infty HF_\mathcal{I}(s) t^s $ 理想的希爾伯特級數 $ \mathcal{I} = \langle p_1, \ldots, p_m\rangle $ 由齊次多項式的規則序列跨越 $ (p_1, \ldots, p_m) $ 是（誰）給的 $ HS_\mathcal{I}(t) = \frac{\prod_{j=1}^m (1-t^{\mathsf{deg} , p_j})}{(1-t)^n} $ . 我們都知道
$$ 3 $$度反向詞典 Gröbner 基礎中最高度元素的度受麥考利界的限制（直至變數的線性變化）： $ \sum_{i=1}^m (\mathsf{deg}(p_i) - 1) + 1 $ . 該界限可用於估計正常（即最壞情況）系統的 Gröbner 基算法的複雜性。如果 $ m = n $ , 序列是規則的當且僅當 $ HS_\mathcal{I} $ 是多項式$$ 4 $$. 這意味著對於某些界限 $ s_0 $ 和所有 $ s \geq s_0 $ , $ HF_\mathcal{I}(s) = 0 $ 所以 $ HP_\mathcal{I}(s) = 0 $ . 在這種情況下， $ s_0 = \mathsf{deg}(HS_\mathcal{I}) + 1 $ 正是規律性的指標。 不幸的是，正常系統在以下情況下不存在 $ m $ 大於 $ n $ . 在這種情況下，必須假設理想具有零維變體，並且鑑於這種情況，我們可以如下調整規則序列的定義。多項式序列 $ (p_1, \ldots, p_m) $ 是 $ d $ - 如果對所有人來說都是正常的 $ g \in \mathbb{F}q[\mathbf{x}] $ 和 $ \mathsf{deg}(g) < d - \mathsf{deg}(p_i) $ , $ g \cdot p_i \in \langle p_1, \ldots, p{i-1} \rangle \implies g \in \langle p_1, \ldots, p_{i-1} \rangle $ . 序列 $ (p_1, \ldots, p_m) $ 是半正則當且僅當它是 $ s_0 $ -正常，在哪裡 $ s_0 $ 是規律性指標
$$ 3 $$. 對於半正則係統，希爾伯特級數 $ HS_\mathcal{I}(t) $ 不會是多項式，但它可以寫成形式冪級數（即具有無限項數的多項式）。在這種情況下 $ s_0 $ 是這個正式冪級數中第一項的次數，其係數為零或負數。我喜歡將其稱為半規則度，但實際上它與假設系統是半規則的規則度相同。將二次多項式方程的隨機系統視為半正則似乎在經驗上是合理的，但沒有證據表明隨機系統確實是半正則的。 **第一秋季學位。**第一個秋季學位由 Dubois 和 Gama 率先推出
$$ 5 $$試圖解釋為什麼 HFE 系統似乎比相同維度的隨機系統更容易解決。它回收了“規則度”應該是系統開始不規則行為的最低程度的直覺，在這種情況下，這被解釋為表現出多項式的非平凡組合導致度數下降。 具體來說，讓 $ R = \mathbb{F}[x_1, \ldots, x_n] / \langle x_1^q-x_1, \ldots, x_n^q - x_n\rangle $ ，即，函式環來自 $ \mathbb{F}_q^n $ 至 $ \mathbb{F}_q $ . （其實我們不妨使用 $ R = \mathbb{F}_q[x_1, \ldots, x_n] / \langle x_1^q, \ldots, x_n^q\rangle $ 因為我們只關心函式的多項式的齊次最高次數部分。）考慮代數組合映射 $ \psi : R \rightarrow \mathbb{F}q[x_1, \ldots, x_n] $ 被定義為 $ (c_1, \ldots, c_m) \mapsto \sum{i=1}^m c_i \cdot p_i $ . 我們對不平凡的元素感興趣 $ R $ 發送到 $ 0 $ 在下面 $ \psi $ ; 這些代表多項式的組合（以多項式作為係數） $ p_1, \ldots, p_m $ 那消失了 — 這種類型的取消的一個特殊詞是 syzygy，儘管該術語更普遍地適用於導致任何類型的取消並且不一定映射到零的代數組合。事實上，我們感興趣的 syzygies 本身不必映射到零。足夠的形象 $ \psi $ 學位低於 $ \mathsf{max}_i , \mathsf{deg}(p_i) + \mathsf{max}_i , \mathsf{deg}(c_i) $ . 此外，我們對盡可能低程度的 syzygies 感興趣。為簡單起見，讓 $ \mathsf{deg}(p_1) = \cdots = \mathsf{deg}(p_m) = 2 $ . 讓 $ R_k $ 是的子集 $ R $ 齊次多項式的次數 $ k $ 並定義 $ \psi_k : R_k \rightarrow \mathbb{F}q[x_1, \ldots, x_n] $ 因此作為發送 $ (c_1, \ldots, c_m) \mapsto \sum{i=1}^m c_i \cdot p_i $ 在這種情況下，核心 $ \psi_k $ 恰好由我們感興趣的 syzygies 組成。定義瑣碎 syzygies 的空間 $ T_k(p_1, \ldots, p_m) \subset R $ 由表單的所有基本元素跨越
- $ c \cdot (0, \ldots, 0, p_j, 0, \ldots, 0, p_i, 0, \ldots, 0) $ 在哪裡 $ p_j $ 在裡面 $ i $ 位置和 $ p_i $ 在裡面 $ j $ 位置，以及在哪裡 $ c \in R_{k-2} $ ;
- $ c \cdot (0, \ldots, 0, p_i^{q-1} - 1, 0, \ldots, 0) $ 在哪裡 $ p_i $ 在裡面 $ i $ 位置和位置 $ c \in R_{k-2(q-1)} $ .
之所以 $ T_k $ 可以用瑣碎的 syzygies 來辨識的是，它的基本元素可以在不查看內容的情況下推導出來 $ p_i $ ; 它們可以描述為 $ p_i $ 不替換符號 $ p_i $ 由它表示的多項式。這留下了非平凡的 syzygies 空間，可以表徵為商空間 $ \mathsf{ker} , \psi_k / T_k $ . 粗略地說，這是 syzygies 的空間，不能歸結為瑣碎 syzygies 的巧妙組合。
多項式列表的第一個下降度 $ p_1, \ldots, p_m $ 定義為 $ \mathsf{min}k { \mathsf{ker} , \psi{k-2}(p_1, \ldots, p_m) / T_{k-2}(p_1, \ldots, p_m) \neq {0} } $ . 粗略地說，這是多項式的代數組合導致非平凡程度下降的最低程度。第一個下降度很有用，因為它更容易界定。見丁等人。
$$ 7 $$$$ 8 $$$$ 9 $$對於從 HFE 構造導出的多元二次系統的第一下降度的一系列上限。但是，這些界限並不嚴格，尤其是對於大場序 $ q $ . 雖然規律性指數總是至少與第一次跌倒程度一樣高，但它可以更高。因此，較低的第一次跌倒度並不一定意味著一個易於解決的系統，儘管它肯定表明正在發生一些可疑的事情。 **求解度。**求解度由丁和施密特介紹
$$ 6 $$作為與第一個秋季學位的對比概念。它被定義為代數係統求解器中涉及的最大擴展麥考利矩陣中多項式的次數。該矩陣上的線性代數支配了求解器的複雜度，因此該度數很好地表徵了這種複雜度。但是，綁定要困難得多。Ding 和 Schmidt 實驗表明，求解度接近於第一個下降度。然而，可以建構差異很大的人工系統。 $$ 1 $$：大衛考克斯和約翰利特爾和唐納德奧謝。理想、品種和算法。第 2 版。第 9 章第 3 節。 $$ 2 $$: 維基百科。https://en.wikipedia.org/wiki/Hilbert_series_and_Hilbert_polynomial $$ 3 $$: Magali Bardet 和 Jean-Charles Faugère 和 Bruno Salvy。關於半正則超定代數方程的 Gröbner 基計算的複雜性。https://www-polsys.lip6.fr/~jcf/Papers/43BF.pdf $$ 4 $$: Magali Bardet 和 Jean-Charles Faugère 和 Bruno Salvy。關於 F5 Gröbner 基算法的複雜性。https://arxiv.org/pdf/1312.1655.pdf $$ 5 $$. 維維安·杜布瓦和尼古拉斯·伽馬。HFE 系統的規律性程度。https://link.springer.com/chapter/10.1007/978-3-642-17373-8_32 $$ 6 $$: Jintai Ding 和 Dieter Schmidt。求解有限域上多項式系統的度和正則度。https://link.springer.com/chapter/10.1007/978-3-642-42001-6_4 $$ 7 $$: Jintai Ding 和 Timothy Hodges。反相 HFE 系統是所有領域的準多項式。https://link.springer.com/chapter/10.1007/978-3-642-22792-9_41 $$ 8 $$: Jintai Ding 和 Thorsten Kleinjung。HFE-的規律性程度。https://eprint.iacr.org/2011/570 $$ 9 $$: Jintai Ding 和 Bo-Yin Yang。HFEv 和 HFEv- 的規則度。https://link.springer.com/chapter/10.1007/978-3-642-38616-9_4