构造排列缩略通用环的三种高效算法及其在密码学与通信系统中的应用价值分析

《Discrete Applied Mathematics》：Efficient methods of constructing shorthand universal cycles for permutations

本文推荐研究“构造排列缩略通用环的高效方法”（Efficient methods of constructing shorthand universal cycles for permutations）。文章聚焦于一类特殊的通用环（Universal cycles， UC），即排列的缩略通用环（shorthand universal cycles for permutations）。作者提出了三种简洁高效的构造方法，这些方法基于巧妙设计后续规则（successor rules），尤其第三种方法能生成∏t=2n-2t!个移位不等价的序列。所有方法均实现了O(1)的均摊时间复杂度和O(n)的空间复杂度。研究对于其在密码学（如流密码密钥序列）和CDMA（码分多址）系统中的潜在应用具有重要意义。

　　

亮点

令π = a₁a₂...a_n为一个n元集合{1,2,...,n}上的n阶排列。排列π的缩略排列（shorthand permutation）由a₁a₂...a_n-1给出，其中缺失符号（the missing symbol）a_n可以轻松确定。用SP(n)表示所有n!个来自n元集合{1,2,...,n}的缩略排列的集合。一个排列的缩略通用环（shorthand universal cycle for permutations）是SP(n)的一个通用环，它是一个长度为n!的周期序列，其中SP(n)的每个元素在每个周期内恰好出现一次。例如，SP(4) = {123, 231, 312, 124, 241, 412, 132, 321, 213, 134, 341, 413, ...}。

两种构造排列缩略通用环的高效方法

在本节中，我们将给出两种构造排列缩略通用环的高效方法。为了更简单地描述这些方法，我们首先在下面的引理中给出一个后续规则，该规则将[SP(n)]中的一些循环连接成一个更大的循环。以下结果稍微修改了Gabric等人研究的一个缩略排列后续规则，我们提供了一个更简单的证明。

引理 3.1

令α = a₁a₂...a_n-1∈ SP(n) 并令a_n为缺失符号。那么后续规则

ρ₀(α) = ( a_n, 如果 |a₁- a_n| = 1;

a^{(这里原文公式显示不完整，根据上下文应为返回a₁或其他符号，但文档内公式显示异常)})

一种构造排列缩略通用环的高效新方法

在本节中，我们将给出另一种构造排列缩略通用环的高效方法，该方法无需对循环进行排序，并能一步完成所有循环的连接过程。

以下定理给出了一个后续规则，用于将[SP(n)]中的所有循环连接成一个排列的缩略通用环。

定理 4.1

令α = a₁a₂...a_n-1∈ SP(n) 并且a_n为缺失符号，令t = min{a₁, a_n}。那么后续规则

ρ₃(α) = ( a_n, 如果 t = 1;

a_n, 如果 1 < t < n-1, |a₁- a_n| ≠ 1 并且 a₂a₃...a_t= (t-1)(t-2)...1;

a₁, )

结论

本文提供了三种简单高效的后续规则来生成排列的缩略通用环，并且这第三种后续规则可以转化为∏_t=2^n-2t!种不同的后续规则。每种后续规则都可以在O(1)的均摊时间内使用O(n)的空间，生成排列的缩略通用环的每个符号。