不同基底表示会导致有限域逆运算的布尔结构差异，影响模型学习难度。
Representation Redundancy and Structural Complexity in Finite-Field Inversion
- 基于伽罗瓦轨道分析基底与逆运算映射的对应关系
- 三种布尔表示的代数度分别为n-1、2(n-1)、≤3(n-1)
- 相同轨道基底虽等价但学习难度不同，适合密码学与神经密码研究
数学运算的表示方式会影响其代数形式和实际学习难度。本文研究在 \\(\mathbb F_{2^n}\\) 上的逆运算，当域元素以不同有序 \\(\mathbb F_2\\) 基表示时，发现两个有序基诱导相同的坐标逆映射当且仅当它们属于同一伽罗瓦轨道。由于每个轨道大小为 \\(n\\)，基与不同逆映射的对应关系恰好是 \\(n\\)-对一。进一步分析了三种布尔形式：参考形式代数度为 \\(n-1\\)，联合ANF跃迁为1；混合表示形式度为 \\(2(n-1)\\)，跃迁为2；完整原始形式度不超过 \\(3(n-1)\\)，跃迁至少为 \\(n\\)。穷举计算验证了理论结果与界限。多层感知机的受控实验显示学习难度排序一致，而伽罗瓦轨道冗余在测试条件下仅带来有限泛化收益。结果表明，表示间的精确冗余可与布尔结构及学习行为变化共存，当表示作为输入暴露时尤为显著。
原文摘要 · Abstract (English)
The representation chosen for a mathematical operation can affect both its algebraic form and its empirical learning difficulty. We study this phenomenon for inversion over \(\mathbb F_{2^n}\), with field elements expressed in varying ordered \(\mathbb F_2\)-bases. We prove that two ordered bases induce the same coordinate inversion map if and only if they belong to the same Galois orbit. Since every orbit has size \(n\), the correspondence between ordered bases and distinct inversion maps is exactly \(n\)-to-one. We then analyze three Boolean formulations of inversion. The reference formulation has algebraic degree \(n-1\) and joint ANF leap \(1\), the mixed representation formulation has degree \(2(n-1)\) and joint ANF leap \(2\), and the complete raw formulation has degree at most \(3(n-1)\) and joint ANF leap at least \(n\). Exhaustive computations agree with the theoretical results and bounds in the cases considered. Controlled experiments with multilayer perceptrons show the same ordering in learning difficulty, while Galois orbit redundancy provides only a limited generalization benefit under the tested conditions. These results show that exact redundancy among representations can coexist with changes in Boolean structure and learning behavior when the representation is exposed as part of the input.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。